队列---链队列：队列的链式存储结构

1、链队列的基本结构ios

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，咱们把它简称为链队列。web

为了操做上的方便，咱们将队头指针指向链队列的头结点，而队尾指针指向终端结点。链队列示意图：算法

当队列为空时，front和rear都指向头结点。svg

2、链队列结构体定义ui

链队列结构体的定义，须要两个步骤：
（1）链队列节点的定义spa

/* QElemType类型根据实际状况而定，这里假设为int */
typedef int QElemType;

typedef struct QNode            /* 结点结构 */
{
    QElemType data;
    struct QNode *next;
} QNode;

（2） LinkQueue 的结构体定义。只要定义队头和队尾指针便可。指针

typedef struct          /* 队列的链表结构 */
{
    QNode *front; /* 队头、队尾指针 */
    QNode *rear;
} LinkQueue;

3、实现要点code

一、初始化。xml

链队列的初始化能够依据单链表的初始化，单链表的初始化是这样的：blog

（1）首先产生头结点（分配内存空间），并使L指向此头结点：

L=(LinkList*)malloc(sizeof(Node));

（2）再将指针域置空：L->next=NULL;

所以，链队列的初始化以下：

（1）产生头结点 (LinkQueue)malloc(sizeof(LinkQueue))，而后让队头指针（头指
针）与队尾指针都指向头结点。
（2）置空头结点 Q->front 的指针域 Q->front->next=NULL;

代码以下：

/* 构造一个空队列q */
LinkQueue *InitQueue(LinkQueue *q)
{
    q->front = q->next =(QNode*)malloc(sizeof(QNode));
    q->front->next = NULL;
    return q;
}

二、入队。入队操做就是在链队列的尾部插入结点。

如上图，入队操做步骤大体如（1）（2）所示。实现算法为：

（1）建立结点s，QNode *p=(QNode*)malloc(sizeof(QNode));
（2）给s的data域赋值e，指针域next赋值null。p->data=e;p->next=NULL; 目的
是让它成为新的队尾元素。
（3）前任队尾元素呢？直接让它的指针域指向p。Q->rear->next=p;
（4）把队尾指针从新指向新任队尾s。Q->rear=p;

三、出队。出队操做时，就是头结点的后继结点（队头）出队，将头结点的后继改成它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。

通常状况下，链队列的出队图示：

若是链队列只剩下一个元素的时候，出队则以下图：

具体步骤：
（1）如图中，要删除掉a1结点，思路很简单，就是让头结点Q->front的后继next直接指向a2。可是a2如何标识呢？
（2）假设a1结点为p结点，那么a2就是p->next了。如何让a1结点存到p呢？
（3）直接让头结点的后继指向p就行，p=Q->front->next;
（4）假如队尾已是p结点的话（Q->rear==p），队尾指针须要指向头结点Q->rear=Q->front;
（5）最后把p free掉。

4、链队列代码实现

#include <iostream>
#include<stdlib.h>
using namespace std;

typedef int QElemType;

typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode;
typedef struct
{
    QNode *front;
    QNode *rear;
}LinkQueue;

// 构造一个空队列q
LinkQueue *InitQueue(LinkQueue *q)
{
    q->front = q->rear =(QNode*)malloc(sizeof(QNode));
    q->front->next = NULL;
    return q;
}

// 元素入队
LinkQueue *EnQueue(LinkQueue *q, QElemType e)
{
    QNode *p = (QNode*)malloc(sizeof(QNode));//为插入节点分配空间
    if(!p)
    {//分配空间失败
        cout<<"插入节点内存分配失败！"<<endl;
    }
    else
    {   //建节点
        p->data = e; //为插入节点数据域赋值
        p->next = NULL;//为插入节点指针域赋值
        //实现插入
        q->rear->next = p;//插入到队尾
        q->rear = p;//队尾指针从新指向新任队尾
    }
    return q;
}
//元素出队
LinkQueue *DeQueue(LinkQueue *q)
{
    QNode *p;
    if(q->front == q->rear)
    {
        cout<<"链队列已空，不可再执行删除操做！"<<endl;
    }
    else
    {
        p = q->front->next;//将欲删除的队头结点暂存给p
        QElemType e = p->data;//把队头数据赋给e
        cout<<"delete: "<<e<<endl;
        q->front->next = p->next;//删除,将原队头结点的后继p->next赋值给头结点后继
        if(q->rear == p)
        {//若队头就是队尾，则删除后将rear指向头结点
            cout<<"链队列数据所有删除完毕！"<<endl;
            q->rear = q->front;
        }
        free(p);
    }
    return q;
}
//返回队头元素
void GetQHead(LinkQueue *q)
{
    QNode *p;
    if(q->front == q->rear)
    {
        cout<<"链队列为空，没法返回队头数据"<<endl;
    }
    else
    {
        p = q->front->next;//队头
        cout<<"队头元素："<<p->data<<endl;
    }
}
//求队列长度
void QueueLength(LinkQueue *q)
{
    int length = 0;
    QNode *p;
    p = q->front->next;//队头
    while(p)
    {
        length++;
        p = p->next;
    }
    cout<<"队列长度："<<length<<endl;
}
//打印。带头结点，真正存储元素的位置从头结点下一位置（队头）开始！！！
void PrintQueue(LinkQueue *q)
{
    QNode *p;//队头
    p = q->front->next;//头结点的下一节点，即为队头！！！
    while(p)
    {//从队头开始，依次日后遍历
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}
int main()
{
    LinkQueue *q = InitQueue(q);

    EnQueue(q, 1);
    PrintQueue(q);
    EnQueue(q, 2);
    PrintQueue(q);
    EnQueue(q, 3);
    PrintQueue(q);
    EnQueue(q, 4);
    PrintQueue(q);

    GetQHead(q);

    QueueLength(q);
    cout<<"***************"<<endl;
    DeQueue(q);
    PrintQueue(q);
    GetQHead(q);

    DeQueue(q);
    PrintQueue(q);
    GetQHead(q);

    DeQueue(q);
    PrintQueue(q);

    DeQueue(q);
    PrintQueue(q);

    QueueLength(q);

    cout<<"***************"<<endl;
    DeQueue(q);
    cout<<"***************"<<endl;

    return 0;
}

结果：

1
1 2
1 2 3
1 2 3 4
队头元素：1
队列长度：4
***************
delete: 1
2 3 4
队头元素：2
delete: 2
3 4
队头元素：3
delete: 3
4
delete: 4
链队列数据所有删除完毕！

队列长度：0
***************
链队列已空，不可再执行删除操做！
***************

Process returned 0 (0x0)   execution time : 0.053 s
Press any key to continue.