队列存储结构

队列

队列和顺序表、链表相比，队列的特殊性体现在以下两个方面：

1. 元素只能从队列的一端进入，从另一端出去，如下图所示：
   

通常，我们将元素进入队列的一端称为“队尾”，进入队列的过程称为“入队”；将元素从队列中出去的一端称为“队头”，出队列的过程称为“出队”。

2. 队列中各个元素的进出必须遵循“先进先出(FIFO)”的原则，即最先入队的元素必须最先出队。

🎈强调：栈和队列不要混淆，栈是一端开口、另一端封口，元素入栈和出栈遵循“先进后出”原则；队列是两端都开口，但元素只能从一端进，从另一端出，且进出队列遵循“先进先出”的原则。

顺序队列的具体实现

通常情况下，我们采用 C 语言中的数组实现顺序表。既然用顺序表模拟实现队列，必然要先定义一个足够大的数组。不仅如此，为了遵守队列中数据从 “队尾进，队头出” 且 “先进先出” 的规则，还需要定义两个变量（top 和 rear）分别记录队头和队尾的具体位置，如图 1 所示：

初始状态下，顺序队列中没有任何元素，因此 top 和 rear 重合，都位于 a[0] 处。
实现入队
在图 1 的基础上，当有新元素入队时，依次执行以下两步操作：
将新元素存储在 rear 记录的位置；
更新 rear 的值（rear+1），记录下一个空闲空间的位置，为下一个新元素入队做好准备。

例如，在图 1 基础上将 {1,2,3,4} 用顺序队列存储的实现操作如图 2 所示：

int enQueue(int* a, int rear, int data) {
    //如果 rear 超出数组下标范围，队列将无法继续添加元素
    if (rear == MAX_LEN) {
        printf("队列已满，添加元素失败\n");
        return rear;
    }
    a[rear] = data;
    rear++;
    return rear;
}
1
2
3
4
5
6
7
8
9
10

实现出队

当有元素出队时，根据“先进先出”的原则，目标元素以及在它之前入队的元素要依次从队头出队。

出队操作的实现方法很简单，就是更新 top 的值（top+1）。例如，在图 2 基础上，顺序队列中元素逐个队列的过程如图 3 所示：

注意，虽然数组中仍保存着 1、2、3、4 这些元素，但队列中的元素是依靠 top 和 rear 来判别的，因此图 3b) 显示的队列中确实不存在任何元素。

int deQueue(int* a, int top, int rear) {
    //如果 top==rear，表示队列为空
    if (top== rear) {
        printf("队列已空，出队执行失败\n");
        return top;
    }
    printf("出队元素：%d\n", a[top]);
    top++;
    return top;
}
1
2
3
4
5
6
7
8
9
10

顺序队列的完整实现代码

使用顺序表模拟实现顺序队列的 C 语言代码为：

#include 
#define MAX_LEN 100 //规定数组的长度
//实现入队操作
int enQueue(int* a, int rear, int data) {
    //如果 rear 超出数组下标范围，队列将无法继续添加元素
    if (rear == MAX_LEN) {
        printf("队列已满，添加元素失败\n");
        return rear;
    }
    a[rear] = data;
    rear++;
    return rear;
}
//实现出队操作
int deQueue(int* a, int top, int rear) {
    //如果 top==rear，表示队列为空
    if (top == rear) {
        printf("队列已空，出队执行失败\n");
        return top;
    }
    printf("出队元素：%d\n", a[top]);
    top++;
    return top;
}
int main() {
    int a[MAX_LEN];
    int top, rear;
    //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址
    top = rear = 0;
    //入队
    rear = enQueue(a, rear, 1);
    rear = enQueue(a, rear, 2);
    rear = enQueue(a, rear, 3);
    rear = enQueue(a, rear, 4);
    //出队
    top = deQueue(a, top, rear);
    top = deQueue(a, top, rear);
    top = deQueue(a, top, rear);
    top = deQueue(a, top, rear);
    top = deQueue(a, top, rear);
    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

出队元素：1
出队元素：2
出队元素：3
出队元素：4
队列已空，出队执行失败
1
2
3
4
5

顺序队列的缺陷

在元素不断入队、出队的过程中，顺序队列会整体向顺序表的尾部移动。整个实现方案存在的缺陷是：

• 顺序队列前面的空闲空间无法再被使用，会造成空间浪费；
• 当顺序队列移动至顺序表尾部时，即便顺序表中有空闲空间，新元素也无法成功入队，我们习惯将这种现象称为“假溢出”。

链式队列

链式队列，简称"链队列"，即使用链表实现的队列存储结构。

链式队列的实现思想同顺序队列类似，创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素。

//链表中的节点结构
typedef struct qnode{
    int data;
    struct qnode * next;
}QNode;
//创建链式队列的函数
QNode * initQueue(){
    //创建一个头节点
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next=NULL;
    return queue;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

链式队列数据入队

链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

1. 将该数据元素用节点包裹，例如新节点名称为 elem；
2. 与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
3. 最后移动 rear 指针指向该新节点，即 rear=elem；

e.g.: 将 {1,2,3} 依次入队

我们将链表的头部作为队列的队头，将链表的尾部作为队列的队尾。当然，也可以反过来，将链表的头部（尾部）作为队列的队尾（队头），两种存储方式都可以。

QNode* enQueue(QNode * rear,int data){
    //1、用节点包裹入队元素
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next=enElem;
    //3、rear指向新节点
    rear=enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}
1
2
3
4
5
6
7
8
9
10
11
12

链式队列数据出队

当链式队列中有元素需要出队时，按照 “先进先出” 的原则，需要先将在它之前入队的元素依次出队，然后该目标元素才能出队。

我们知道，队列中的元素只能从队头出队。在图 2 中，队列的队头位于链表的头部。因此队列中元素出队的过程，其实是链表中摘除首元结点的过程，需要做以下 3 步操作：

1. 通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
2. 将 top 所指结点的 next 指针，指向 p 结点的直接后继结点；
3. 释放节点 p 占用的内存空间；

例如，在图 2b) 的基础上，我们将元素 1 和 2 出队，则操作过程如图 3 所示：

QNode* DeQueue(QNode* top, QNode* rear) {
    QNode* p = NULL;
    if (top->next == NULL) {
        printf("\n队列为空\n");
        return rear;
    }
    // 1、创建新指针 p 指向目标结点
    p = top->next;
    printf("%d ", p->data);
    //2、将目标结点从链表上摘除
    top->next = p->next;
    if (rear == p) {
        rear = top;
    }
    //3、释放结点 p 占用的内存
    free(p);
    return rear;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意，将队头元素做出队操作时，需提前判断队列中是否还有元素，如果没有，要提示用户无法做出队操作，保证程序的健壮性。此外，程序中要判断被摘除的目标结点是否是 rear 队头队尾，如果是的话，要及时更新 rear 指针的指向。

总结

通过学习链式队列最基本的数据入队和出队操作，我们可以就实际问题，对以上代码做适当的修改。

前面在学习顺序队列时，由于顺序表的局限性，我们在顺序队列中实现数据入队和出队的基础上，又对实现代码做了改进，令其能够充分利用数组中的空间。链式队列就不需要考虑空间利用的问题，因为链式队列本身就是实时申请空间。因此，这可以算作是链式队列相比顺序队列的一个优势。

这里给出链式队列入队和出队的完整 C 语言代码为：

#include 
#include 
//链表中的节点结构
typedef struct qnode {
    int data;
    struct qnode* next;
}QNode;
//创建链式队列的函数
QNode* initQueue() {
    //创建一个头节点
    QNode* queue = (QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next = NULL;
    return queue;
}
QNode* enQueue(QNode* rear, int data) {
    //1、用节点包裹入队元素
    QNode* enElem = (QNode*)malloc(sizeof(QNode));
    enElem->data = data;
    enElem->next = NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next = enElem;
    //3、rear指向新节点
    rear = enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}
QNode* deQueue(QNode* top, QNode* rear) {
    QNode* p = NULL;
    if (top->next == NULL) {
        printf("\n队列为空\n");
        return rear;
    }
    // 1、创建新指针 p 指向目标结点
    p = top->next;
    printf("%d ", p->data);
    //2、将目标结点从链表上摘除
    top->next = p->next;
    if (rear == p) {
        rear = top;
    }
    //3、释放结点 p 占用的内存
    free(p);
    return rear;
}
int main() {
    QNode* queue = NULL, * top = NULL, * rear = NULL;
    queue = top = rear = initQueue();//创建头结点
    //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    rear = enQueue(rear, 1);
    rear = enQueue(rear, 2);
    rear = enQueue(rear, 3);
    rear = enQueue(rear, 4);
    //入队完成，所有数据元素开始出队列
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    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

运行结果：

1 2 3 4
队列为空