队列---链队列：队列的链式存储结构_链式队列保存的是指针而不是节点本身

一、链队列的基本结构

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

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

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

二、链队列结构体定义

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

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

typedef struct QNode            /* 结点结构 */
{
    QElemType data;
    struct QNode *next;
} QNode;
1
2
3
4
5
6
7
8

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

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

三、实现要点

1、初始化。

链队列的初始化可以依据单链表的初始化，单链表的初始化是这样的：

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

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

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

因此，链队列的初始化如下：

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

代码如下：

/* 构造一个空队列q */
LinkQueue *InitQueue(LinkQueue *q)
{
    q->front = q->next =(QNode*)malloc(sizeof(QNode));
    q->front->next = NULL;
    return q;
}
1
2
3
4
5
6
7

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

如上图，入队操作步骤大致如（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;
1
2
3
4
5

3、出队。出队操作时，就是头结点的后继结点（队头）出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将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掉。

四、链队列代码实现

#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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

结果：

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25