_{王道C++班级参考资料}
——
C语言部分^卷5数据结构
^_节3队列

最新版本`V3.0`
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有

王道C++班级参考资料 —— C语言部分卷5数据结构 节3队列 最新版本V3.0 王道C++团队 COPYRIGHT ⓒ 2021-2024. 王道版权所有概述数组队列的实现数组队列的实现方式设计头文件实现创建和销毁队列实现判空和判满实现入队操作实现出队操作实现访问队首元素扩展: 链式队列扩展: 动态数组队列队列的应用场景The End

概述

_Gn!
队列是另一种操作受限的线性结构。但它的受限和栈是不同的：
队列只能在一端添加元素（队尾）
在另一端访问、删除元素（队头）
队列就不用想象了，它就是我们生活中排队的场景，你只能在队尾插入一个元素，在队头删除一个元素。
在队列中，最先添加到队尾的元素总是最先在队头删除，遵循先进先出（FIFO，First In First Out）的原则。
如下图所示：
队列这种数据结构的基本操作主要包括以下几种：
入队：在队尾添加一个元素，新元素成为新的队尾元素。
出队：在队头删除一个元素，第二个元素称为新的队头元素。
访问队头元素
判空
判满

数组队列的实现

_Gn!
队列在实现时同样可以选择基于数组或者链表，其中数组实现是更常用的选择，链表实现则交给大家自行做作业完成。

数组队列的实现方式

_Gn!
基于数组来实现队列（使用普通数组，假设数组的长度是N），有以下几种方案：
注意：这里使用的都是索引，而不是指针。数组可以使用索引模拟指针，而不需要直接使用指针！！
第一种方案：
这种实现方案，基本操作的时间复杂度是：
入队：在rear索引位置插入一个元素，rear索引加1。时间复杂度是O(1)
出队：删除数组首元素，但后续所有元素必须向前移动一位，rear索引减1。时间复杂度是O(n)
访问队头元素：也就是访问数组首元素，时间复杂度是O(1)
这种方案队列判空的条件是：
rear == 0
判满的条件是：
rear == N
显然这种方案链出入队的效率都无法保证，不是一个可用的解决方案。
第二种方案：
队列的出入队是最基本操作，O(n)的时间复杂度是不可取的。所以我们优化一下得到方案二：
这种实现方案，基本操作的时间复杂度是：
入队：在rear索引位置插入一个元素，rear索引加1。时间复杂度是O(1)
出队：删除front位置元素，然后front索引加1。时间复杂度是O(1)
访问队头元素：也就是访问front索引位置的元素，时间复杂度是O(1)
这种方案队列判空的条件是：
front == rear
判满的条件是：
rear == N
这样的设计使得出入队的操作效率都得到了保障，但是也有一个明显的缺点：
随着不断地出队操作，数组前面的空间会变得闲置，而且不可以被重新利用，这显然也是不可取的。
第三种方案：
基于方案二的问题，我们实现一个循环队列，以解决空间浪费的问题。如下图所示：
这种方案，最核心的问题就是：如何移动两个索引，使得它们能够在数组内部循环移动呢？
使用取余运算符"%"即可：
rear = (rear + 1) % N
front = (front + 1) % N
解释：
对于数组的下标运算，几乎都是要涉及对数组长度N的取余运算，现在我们希望往后移动索引，而且希望从最后一个索引向后移动是第一个索引，所以就这样计算。
方案三的设计就实现了对数组前面空间的利用，避免了空间浪费，同时出入队的效率也很高。下面我们思考一个问题：
这种设计方案，如何进行队列判空和判满呢？
实际上如果就单纯按照上述方案设计循环队列，那么它们的判空和判满条件是一样的：
rear == front
所以对于这两个操作我们还需要进行一点小优化，有两个选择：
牺牲一个存储单元不存储元素，只要rear指向front的前一个位置就表示队列满了。如下图所示：
在这种情况下：
队列满了的条件是：(rear + 1) % N == front
队列为空的条件是：rear == front
这种办法是教科书中讲数据结构经常使用的方案，在实际开发中我们可以用一个更简单粗暴，更易于实现和使用的方式——计数器。
使用一个额外的计数器变量来统计数组中元素的个数，这样判空和判满都十分简洁了。具体而言可以参考下图的实现：
基于上述图中的模型，实现一个固定长度的数组队列，需要注意的是：
front用于记录队头元素，出队时就将该元素出队。
rear用于指示下一个元素入队的索引，也就是说入队操作时直接将元素插入rear索引位置就可以了。
规定front(包含)和rear(不包含)索引之间的元素就是队列元素，出队操作时，直接向后移动索引front就可以了，不需要任何赋值操作。
front向后移动的方式是：(front + 1) % N
rear向后移动的方式是：(rear + 1) % N

设计头文件

_Gn!

我们可以创建一个头文件"my_queue.h"，参考代码如下：

头文件-参考代码


1
#ifndef ARRAY_QUEUE_H
2
#define ARRAY_QUEUE_H
3

4
#include <stdbool.h>
5
#include <stdlib.h>
6
#include <stdio.h>
7
#define QUEUE_CAPACITY 10
8
typedef int ElementType;
9

10
typedef struct {
11
 // 由于是固长数组队列，所以直接把数组作为结构体对象的一个成员
12
 ElementType elements[QUEUE_CAPACITY];
13
 int front; // 队头元素的索引
14
 int rear;  // 队尾元素下一个位置的索引
15
 int size;  // 队列数组中实际存储元素的个数
16
} ArrayQueue;
17

18
// 初始化一个空队列
19
ArrayQueue *queue_create();
20
// 销毁一个队列
21
void queue_destroy(ArrayQueue *q);
22
// 判满
23
bool is_full(ArrayQueue *q);
24
// 判空
25
bool is_empty(ArrayQueue *q);
26
// 入队
27
bool enqueue(ArrayQueue *q, ElementType element);
28
// 出队
29
ElementType dequeue(ArrayQueue *q);
30
// 访问队首元素
31
ElementType peek(ArrayQueue *q);
32

33
#endif // !ARRAY_QUEUE_H

下面就可以基于该头文件，从而实现这个循环队列。

实现创建和销毁队列

_Gn!

先来实现两个比较简单的，创建和销毁操作。这两个操作基本就是直接，分配内存和释放内存。参考代码如下：

创建和销毁队列-参考代码


xxxxxxxxxx
8
1
// 初始化一个空队列
2
ArrayQueue *queue_create() {
3
 return calloc(1, sizeof(ArrayQueue));
4
}
5
// 销毁一个队列
6
void queue_destroy(ArrayQueue *q) {
7
 free(q);
8
}

注意用calloc函数是最合适的，省去了手动初始化0值的麻烦，错误处理则由函数调用者来完成。

实现判空和判满

_Gn!
判空和判满在入队和出队操作时，都会用到，所以我们先来实现这两个操作。
由于我们在结构体对象中维护了一个size成员用于记录队列的元素数量，所以判断和判满的实现就非常容易了。
参考代码如下：
判空和判满-参考代码
xxxxxxxxxx
8
1
// 判满
2
bool is_full(ArrayQueue *q) {
3
   return q->size == QUEUE_CAPACITY;
4
}
5
// 判空
6
bool is_empty(ArrayQueue *q) {
7
 return q->size == 0;
8
}

实现入队操作

_Gn!

入队的具体逻辑是：

首先判断队列是否已满，若队列已满则无法执行入队操作。
若队列未满，则在rear索引处新增一个元素，并将rear索引移到下一个位置。
更新size。

参考代码如下：

入队-参考代码


1
// 入队
2
bool enqueue(ArrayQueue *q, ElementType element) {
3
    // 1.判满
4
    if (is_full(q)) {
5
        printf("error: queue is full.\n");
6
        return false;
7
    }
8
    // 2.队列没满时才入队
9
    q->elements[q->rear] = element;
10
    // 3.更新rear索引
11
    q->rear = (q->rear + 1) % QUEUE_CAPACITY;
12
    // 4.更新size
13
    q->size++;
14
    return true;    // 入队成功
15
}

稍微需要注意的就是更新rear索引的逻辑，由于它向后移动1位，且数组长度为CAPACITY，所以rear索引更新的逻辑就是：

q->rear = (q->rear + 1) % CAPACITY;

实现出队操作

_Gn!

出队的具体逻辑是：

首先判断队列是否为空，若队列为空则无法实现出队操作。
若队列不为空，则将front索引移到下一个位置，并返回此前的队首元素。
更新size。

参考代码如下：

出队操作-参考代码


1
/*
2
* 出队就是将front索引的元素返回，然后将front索引后移
3
* 注意：不需要对front位置的元素做任何修改
4
* 因为front和rear之间的元素才是队列元素，其它位置即便有值也不算队列元素
5
* 其他位置的垃圾值，会随着队列出入队操作逐渐被覆盖
6
*/
7
ElementType dequeue(ArrayQueue *q) {
8
    // 1.判空
9
    if (is_empty(q)) {
10
        printf("error: queue is empty.\n");
11
        exit(1);
12
    }
13
    // 2.队列非空，记录队首元素以用于返回
14
    ElementType ret = q->elements[q->front];
15

16
    // 3.更新front索引
17
    q->front = (q->front + 1) % QUEUE_CAPACITY;
18

19
    // 4.不要忘记更新size
20
    q->size--;
21
    return ret;
22
}

这里同样有一个更新front索引的逻辑，和上面更新rear的逻辑是一致的。

实现访问队首元素

_Gn!

这个操作就太简单了，判空处理一下，然后返回队首元素即可。参考代码如下：

访问队首元素-参考代码


1
// 访问队首元素
2
ElementType peek(ArrayQueue *q) {
3
    // 1.判断队列是否是空的
4
    if (is_empty(q)) {
5
        printf("error: queue is empty.\n");
6
        exit(1);
7
    }
8
    // 2.队列非空返回队首元素
9
    return q->elements[q->front];
10
}

扩展: 链式队列

_Gn!

基于链表来实现队列也是可以的，但不如使用数组常见，因为数组来实现队列的访问效率会更高。

但链表实现的队列往往会更加灵活，且不会像数组那样存在较多的内存空间没有被利用，空间利用率高，没有闲置空间。所以链式队列也有它的可取之处。

注意：链式队列就没有队列满的概念了，它的基本操作中可以把判满去掉。

下面基于一个头文件，我们实现一下链式队列：

链式队列头文件-参考代码


x
1
#ifndef LIST_QUEUE_H
2
#define LIST_QUEUE_H
3

4
#include <stdbool.h>
5
#include <stdio.h>
6
#include <stdlib.h>
7

8
// 定义队列中的元素类型
9
typedef int ElementType;
10

11
// 队列节点的结构
12
typedef struct node_s {
13
    ElementType data;
14
    struct node_s *next;
15
} QueueNode;
16

17
// 队列的结构
18
typedef struct {
19
    QueueNode *front;  // 队头结点指针
20
    QueueNode *rear;   // 队尾结点指针
21
} LinkedListQueue;
22

23
// 函数声明
24
// 创建链式队列
25
LinkedListQueue *create_queue();
26
// 销毁链式队列
27
void destroy_queue(LinkedListQueue *q);
28
// 入队列
29
bool enqueue(LinkedListQueue *q, ElementType element);
30
// 出队列并返回队头元素
31
ElementType dequeue(LinkedListQueue *q);
32
// 访问队头元素
33
ElementType peek_queue(LinkedListQueue *q);
34
// 判空
35
bool is_empty(LinkedListQueue *q);
36

37
#endif // !LIST_QUEUE_H

下面是它的实现参考代码：

链式队列实现-参考代码


x
1
#include "list_queue.h"
2

3
// 函数声明
4
LinkedListQueue *create_queue() {
5
    return calloc(1, sizeof(LinkedListQueue));
6
}
7

8
void destroy_queue(LinkedListQueue *q) {
9
    // 从队头开始遍历链表，销毁每一个结点
10
    QueueNode *current = q->front;
11
    while (current != NULL) {
12
        QueueNode *temp = current->next;
13
        free(current);
14
        current = temp;
15
    }
16
    // 销毁队列结构体
17
    free(q);
18
}
19

20
bool is_empty(LinkedListQueue *q) {
21
    // 队头指针是空指针，即表示空队列
22
    return q->front == NULL;
23
}
24

25
// 入队操作: 只能在队尾插入一个结点
26
// 由于已存在尾指针，所以这里的操作就是链表尾插
27
bool enqueue(LinkedListQueue *q, ElementType element) {
28
    QueueNode *new_node = malloc(sizeof(QueueNode));
29
    if (new_node == NULL) {
30
        printf("Error: malloc failed in enqueue.\n");
31
        return false;
32
    }
33
    // 初始化新结点
34
    new_node->data = element;
35
    new_node->next = NULL;
36

37
    // 开始进行尾插法插入一个结点
38
    // 分两种情况：如果尾插插入的是第一个结点需要同步更新头指针，否则仅需要更新尾指针
39
    if (q->front == NULL) {
40
        // 插入的是第一个结点
41
        q->front = new_node;
42
        q->rear = new_node;
43
    }
44
    else {
45
        // 插入的不是第一个结点
46
        q->rear->next = new_node;
47
        q->rear = new_node;
48
    }
49
    return true;
50
}
51

52
// 出队，在队头删除一个结点。也就是在删除链表的第一个结点
53
ElementType dequeue(LinkedListQueue *q) {
54
    if (is_empty(q)) {
55
        printf("Error: queue is empty.\n");
56
        exit(1);
57
    }
58

59
    QueueNode *tmp = q->front;
60
    // 将出队的结点数据保存
61
    ElementType remove_data = tmp->data;
62

63
    // 更新队头指针
64
    q->front = tmp->next;
65
    if (q->front == NULL) {
66
        // 如果队头更新后,队列为空,说明出队的就是最后一个元素
67
        // 于是同步更新队尾指针
68
        q->rear = NULL;
69
    }
70

71
    free(tmp);
72
    return remove_data;
73
}
74

75
// 访问队头元素但不出队
76
ElementType peek_queue(LinkedListQueue *q) {
77
    if (is_empty(q)) {
78
        printf("Error: queue is empty.\n");
79
        exit(1);
80
    }
81
    return q->front->data;
82
}

最后给出一段测试代码：

链式队列测试用例-参考代码


x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include "list_queue.h"
3
#include <stdio.h>
4

5
int main(void) {
6
    LinkedListQueue *q = create_queue();
7
    // 逐一入队列
8
    enqueue(q, 1);
9
    enqueue(q, 2);
10
    enqueue(q, 3);
11
    enqueue(q, 4);
12
    enqueue(q, 5);
13
    enqueue(q, 6);
14
    // 先进先出，出队列全部元素直到队列为空
15
    while (!is_empty(q)) {
16
        int val = peek_queue(q);
17
        printf("%d ", val);
18
        dequeue(q);
19
    }
20
    printf("\n");
21
    return 0;
22
}

最终出队列的结果应该是：

1 2 3 4 5 6

扩展: 动态数组队列

_Gn!

既然可以实现固定长度的队列，那么基于动态数组，就可以实现一个动态数组队列。

基于以下头文件"dynamic_queue.h"来实现：

扩展: 动态数组队列-演示代码1


x
1
#ifndef DYNAMIC_QUEUE_H
2
#define DYNAMIC_QUEUE_H
3

4
#include <stdbool.h>
5
#include <stdlib.h>
6
#include <stdio.h>
7

8
typedef int ElementType;    // 该队列当前存储int元素
9
#define DEFAULT_CAPACITY 10 // 数组队列的初始长度是10
10
#define THRESHOLD 1000  // 超过阈值每次扩容1.5倍扩，否则2倍的扩
11

12
// 定义队列结构体
13
typedef struct {
14
    ElementType *data;   // 动态数组存储队列元素
15
    int front;           // 标记队头元素的索引
16
    int rear;            // 标记队尾元素下一个位置的索引
17
    int size;            // 当前队列中元素数量
18
    int capacity;        // 队列容量
19
} DynamicQueue;
20

21
// 队列基本操作函数声明
22
// 创建动态数组队列
23
DynamicQueue *create_queue();
24
// 销毁动态数组队列
25
void destroy_queue(DynamicQueue *q);
26
// 判空
27
bool is_empty(DynamicQueue *q);
28
// 判满
29
bool is_full(DynamicQueue *q);
30
// 入队列
31
bool enqueue(DynamicQueue *q, ElementType data);
32
// 出队列并且返回队头元素
33
ElementType dequeue(DynamicQueue *q);
34

35
#endif // DYNAMIC_QUEUE_H

下面是它的实现参考代码：

扩展: 动态数组队列-演示代码2


x
1
#include "dynamic_queue.h"
2

3
// 创建并初始化队列
4
DynamicQueue *create_queue() {
5
    DynamicQueue *q = calloc(1, sizeof(DynamicQueue));
6
    if (q == NULL) {
7
        printf("error: calloc failed in create_queue.\n");
8
        return NULL;
9
    }
10
    // front、rear、size自动初始化0值，无需再手动初始化了
11
    q->data = calloc(DEFAULT_CAPACITY, sizeof(ElementType));    // 使用calloc避免随机值
12
    if (q->data == NULL) {
13
        printf("error: calloc failed in create_queue.\n");
14
        free(q);
15
        return NULL;
16
    }
17
    q->capacity = DEFAULT_CAPACITY;
18
    return q;
19
}
20

21
// 销毁队列
22
void destroy_queue(DynamicQueue *q) {
23
    free(q->data);
24
    free(q);
25
}
26

27
// 检查队列是否为空
28
bool is_empty(DynamicQueue *q) {
29
    return q->size == 0;
30
}
31

32
// 检查队列是否已满
33
bool is_full(DynamicQueue *q) {
34
    return q->size == q->capacity;
35
}
36

37
/*
38
    这里采用一种简单粗暴的扩容手段:
39
    直接分配新容量的内存块
40
    然后遍历旧内存块中的队列元素,将这些元素全部从头开始复制到新内存块中
41
    这样的操作在完成后,需要更新front索引和rear索引
42
*/
43
static bool resize_queue(DynamicQueue *q) {
44
    int old_capacity = q->capacity;
45
    int new_capacity = (old_capacity < THRESHOLD) ?
46
        (old_capacity << 1) :
47
    (old_capacity + (old_capacity >> 1));
48

49
    // 重新分配一个新的,更长的动态数组
50
    ElementType *new_data = malloc(new_capacity * sizeof(ElementType));
51
    if (new_data == NULL) {
52
        printf("error: realloc failed in resize_queue.\n");
53
        return false;
54
    }
55

56
    int curr = q->front;    // curr索引用于遍历整个队列中的元素
57
    int index = 0;
58
    while (index < q->size) {
59
        new_data[index] = q->data[curr];
60
        curr = (curr + 1) % q->capacity;
61
        index++;
62
    } // while循环结束时,new_data就从头开始包含了队列的所有元素 
63
    free(q->data);
64
    q->data = new_data;
65
    q->front = 0;
66
    q->rear = q->size;
67
    q->capacity = new_capacity;
68
    return true;
69
}
70

71
// 入队操作
72
bool enqueue(DynamicQueue *q, ElementType data) {
73
    if (is_full(q)) {
74
        if (!resize_queue(q)) {
75
            printf("error: 扩容失败.\n");
76
            return false; // 队列扩容失败,入队也同步失败
77
        }
78
    }
79
    q->data[q->rear] = data;
80
    q->rear = (q->rear + 1) % q->capacity;  // 循环队列
81
    q->size++;
82
    return true;
83
}
84

85
// 出队操作
86
ElementType dequeue(DynamicQueue *q) {
87
    if (is_empty(q)) {
88
        printf("error: 队列为空，无法出队。\n");
89
        exit(1);
90
    }
91
    ElementType item = q->data[q->front];
92
    q->front = (q->front + 1) % q->capacity; // 循环队列
93
    q->size--;
94
    return item;
95
}

最后仍然是给出一个测试用例，代码如下：

扩展: 动态数组队列-演示代码3


x
1
#include "dynamic_queue.h"
2
#include <stdio.h>
3

4
int main(void) {
5
    // 创建队列
6
    DynamicQueue *queue = create_queue();
7
    if (queue == NULL) {
8
        printf("创建队列失败。\n");
9
        return 1;
10
    }
11

12
    // 入队测试
13
    for (int i = 0; i < 15; i++) {
14
        if (enqueue(queue, i)) {
15
            printf("已入队: %d\n", i);
16
        }
17
        else {
18
            printf("入队失败: %d\n", i);
19
        }
20
    }
21

22
    // 打印队列容量和大小
23
    printf("队列容量: %d, 队列大小: %d\n", queue->capacity, queue->size);
24

25
    // 出队测试
26
    printf("正在出队...\n");
27
    while (!is_empty(queue)) {
28
        printf("已出队: %d\n", dequeue(queue));
29
    }
30

31
    // 销毁队列
32
    destroy_queue(queue);
33

34
    return 0;
35
}

以上。

队列的应用场景

_Gn!
队列是一种非常实用的数据结构，由于其先进先出（FIFO）的特性，队列特别适用于那些需要按顺序处理元素的场景。
这种场景就太多了：
操作系统的任务调度，进程/线程按照到达顺序来排队等待CPU执行权。
各种数据处理系统中的缓冲区/缓存机制。比如stdin/stdout缓冲区，先输入缓冲区的数据，总是先从缓冲区输出。
打印机的任务管理，当多个打印任务同时到达时，它们在队列中排队，按照提交的顺序进行打印。
后端应用系统中的消息队列。
广度优先搜索(比如二叉搜索树的层次遍历)
...
消息队列的机制
在这里，我们不妨扩展讲解一下消息队列的机制。
首先消息队列是后端应用系统中，特别重要且几乎必然要使用的一种中间件。常用的消息队列有：Kafka、RabbitMQ、RocketMQ...
这些消息队列，消息中间件，它们的实现往往都非常复杂，但核心的概念都是基于数据结构中的队列的，也就是满足"先进先出"的特点。
这些消息中间件的作为是在多台服务器之间进行消息传递，发送消息，接收消息等。这些消息就会按照发送的顺序排队，形成队列，然后按照"先进先出"的顺序进行处理。
当用户量、并发水平达到一定程度，应用往往都要进行服务化，将不同的服务运行在不同的服务器上，由于这些服务本身就是一条流水线上的业务，所以常规的处理方式就是"同步处理"：
A机器处理完A业务，告诉B机器
B机器处理完B业务，告诉C机器
C机器处理完C业务
...
这种同步的处理方式，使得应用整体抗风险能力很差，某台机器出问题就意味着整体完蛋，并且由于"木桶效应"，某台机器处理某业务的效率如果偏低，那么它将拖累整个业务流程的处理性能。
这时我们就可以通过引入一个中间层"消息中间件"，让原本需要同步处理耦合严重的业务实现了分离解耦，从而就可以实现业务逻辑的异步处理，提高性能，也增强了抗风险性。
这里我们以一个订单处理的逻辑来举例说明为什么消息中间件这么重要：

王道C++班级参考资料——C语言部分卷5数据结构节3队列最新版本V3.0王道C++团队COPYRIGHT ⓒ 2021-2024. 王道版权所有

概述

数组队列的实现

数组队列的实现方式

设计头文件

头文件-参考代码

实现创建和销毁队列

创建和销毁队列-参考代码

实现判空和判满

判空和判满-参考代码

实现入队操作

入队-参考代码

实现出队操作

出队操作-参考代码

实现访问队首元素

访问队首元素-参考代码

扩展: 链式队列

链式队列头文件-参考代码

链式队列实现-参考代码

链式队列测试用例-参考代码

扩展: 动态数组队列

扩展: 动态数组队列-演示代码1

扩展: 动态数组队列-演示代码2

扩展: 动态数组队列-演示代码3

队列的应用场景

The End

_{王道C++班级参考资料}
——
C语言部分^卷5数据结构
^_节3队列

最新版本`V3.0`
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有