前言：
本章我们将学习 "队列" ，首先介绍队列的概念和结构，然后我们将着重讲解栈的实现。我们从零开始写队列的接口，并从零开始步步解读。本章将继续巩固画思路草图的能力，只要思路草图画好了，就可以很轻松地将其转换成代码。
一、队列（Queue）
0x00 队列的概念
📚 概念：
① 队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。
② 入队列，进行插入操作的一端称为 队尾。出队列，进行删除操作的一端称为 队头。
③ 队列中的元素遵循先进先出的原则，即 FIFO 原则（First In First Out）
0x01 队列的结构
🔍 结构：
二、队列的定义
0x00 链式队列
typedef int QueueDataType; //队列类型
typedef struct QueueNode {
struct QueueNode* next; //指向下一个节点
QueueDataType data; //数据
} QueueNode;
typedef struct Queue {
QueueNode* pHead; //头指针
QueueNode* pTail; //尾指针
} Queue;❓ 为什么不使用单链表？
💡 单链表我们只定义了一个指针指向头，没有定义尾指针。因为定义尾指针解决不了问题，比如尾插尾删。所以我们没有必要定义一个结构体把他们封到一起。这里我们再定义一个头指针 head 一个尾指针 tail ，这两个指针才有意义。因为根据队列的性质，我们只会在队尾插，不会再队尾删。所以这个尾指针的价值就得到了完美的体现，实际中定义几个指针是看你的需求确定的。
0x02 接口函数
📚 这是需要实现几个接口函数：
void QueueInit(Queue* pQ); //队列初始化
void QueueDestroy(Queue* pQ); //销毁队列
bool QueueIfEmpty(Queue* pQ); //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x); //入队
void QueuePop(Queue* pQ); //出队
QueueDataType QueueFront(Queue* pQ); //返回队头数据
QueueDataType QueueBack(Queue* pQ); //返回队尾数据
int QueueSize(Queue* pQ); //求队列大小
三、队列的实现
0x00 队列初始化（QueueInit）
💬 Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QueueDataType; //队列类型
typedef struct QueueNode {
struct QueueNode* next; //指向下一个节点
QueueDataType data; //数据
} QueueNode;
typedef struct Queue {
QueueNode* pHead; //头指针
QueueNode* pTail; //尾指针
} Queue;
void QueueInit(Queue* pQ); //队列初始化💬 Queue.c
/* 队列初始化：将头尾指针置为NULL */
void QueueInit(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
pQ->pHead = pQ->pTail = NULL; //将头尾指针置空
}🔑 解析：首先使用断言防止传入的pQ为空。初始化只需要把头指针和尾指针都置成空即可。
0x01 销毁队列（QueueDestroy）
/* 销毁队列：free掉所有队列元素并将头尾置空 */
void QueueDestroy(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
QueueNode* cur = pQ; //创建遍历指针cur
while(cur != NULL) { //cur不为空就进入循环
QueueNode* curNext = cur->next; //信标指针curNext
free(cur); //释放cur当前指向的节点
cur = curNext; //移动指针cur
}
pQ->pHead = pQ->pTail = NULL; //置空干掉野指针
}🔑 解读：
① 首先断言防止传入的pQ为空。
② 销毁要把所有节点都释放掉，我们创建遍历指针 cur 遍历整个队列。既然要释放 cur 指向的节点，为了防止释放 cur 之后找不到其下一个节点导致无法移动，我们这里创建一个类似于信标性质的指针 curNext 来记录一下 cur 的下一个节点，之后再 free 掉 cur，这样就可以移动 cur 了。
③ 最后为了防止野指针，还需要把头指针和尾指针都置为空。
0x02 判断队列是否为空
💬 Queue.h
bool QueueIfEmpty(Queue* pQ); //判断队列是否为空🔑 解读：布尔值，返回 true 或 false
💬 Queue.c
/* 判断队列是否为空 */
bool QueueIfEmpty(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
return pQ->pHead == NULL; //如果成立则为True，不成立则为False
}
🔑 解读：
① 首先断言防止传入的pQ为空。
② 判断队列是否为空，可以直接返回，巧妙地利用布尔类型的特性。如果 pQ->pHead == NULL 成立则为真，会返回 true；不成立则为假，会返回 false。
0x03 入队（QueuePush）
💬 Queue.h
void QueuePush(Queue* pQ, QueueDataType x); //入队💬 Queue.c
/* 入队：队尾入数据，对头出数据。如果是第一个入队的则既要当头又当尾 */
void QueuePush(Queue* pQ, QueueDataType x) {
assert(pQ); //防止传入的pQ为空
/* 创建新节点：创建一个大小为QueueNode的空间 */
QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
/* 检查malloc */
if(new_node == NULL) {
printf("malloc failed!\n");
exit(EXIT_FAILURE);
}
/* 放置 */
new_node->data = x; //待插入的数据
new_node->next = NULL; //默认为空
/* 入队：
*【思路草图】
* 情况1：队列为空：既当头又当尾
* [new_node]
* ↑ ↑
* pHead pTail
*
* 情况2：队列不为空：队尾入数据
* [] -> [] -> [] -> [] -> [new_node]
* pHead pTail pTail->next
* ↓ ↑
* ----------→ pTail（更新尾指针）
*/
if(pQ->pHead == NULL) { //情况1: 队列为空
pQ->pHead = pQ->pTail = new_node; // 既当头又当尾
} else { //情况2: 队列不为空
pQ->pTail->next = new_node; // 在现有尾的后一个节点放置new_node
pQ->pTail = new_node; // 更新pTail，使它指向新的尾
}
}
🔑 解读：
① 首先断言防止传入的pQ为空。
② 我们首先要创建新节点。通过 malloc 动态内存开辟一块 QueueNode 大小的空间，都学到这里了大家想必都养成了检查 malloc 的好习惯了吧？。最后放置数据吗，将待插入的数据 x 交给 data，next 默认置空，和之前学链表一样，这里就不过多赘述了。
③ 新节点创建好后，我们可以开始写入队的操作了。首先要理解队列的性质：队尾入数据，队头出数据。这里既然是入队，就要在对尾后面进行插入。这里我们还要考虑到如果队列为空的情况，这时我们要把头指针和尾指针都交付给 new_node 。为了理清思路，我们可以画一个思路草图来帮助我们更好地理解：
有了这个图，我们就可以清楚地实现了：
if(pQ->pHead == NULL) { //情况1: 队列为空
pQ->pHead = pQ->pTail = new_node; // 既当头又当尾
}
else { //情况2: 队列不为空
pQ->pTail->next = new_node; // 在现有尾的后一个节点放置new_node
pQ->pTail = new_node; // 更新pTail，使它指向新的尾
}当队列为空时，令头指针和尾指针都指向 new_node ，当队列不为空时，再尾部地下一个节点放置 new_node ，随后再更新尾指针让其指向新的尾（new_node 的位置）。
0x04 出队（QueuePop）
💬 Queue.h
void QueuePop(Queue* pQ); //出队💬 Queue.c
/* 出队：队尾入数据，对头出数据 */
void QueuePop(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
assert(!QueueIfEmpty(pQ)); //防止队列为空
/* 出队:
*【思路草图】
* [free] -> [] -> [] -> []
* pHead headNext
* ↓ ↑
* -------→ pHead（更新头指针）
*/
QueueNode* headNext = pQ->pHead->next; //信标指针HeadNext
free(pQ->pHead);
pQ->pHead = headNext; //更新头
/* 如果队内都被删完了，不处理pTail就会带来野指针的隐患
* 【思路草图】
* NULL 已经被free掉的内存！
* ↑ ↑ （野指针警告）
* pHead(因为HeadNext是NULL) pTail
*/
if(pQ->pHead == NULL) //如果pHead为空
pQ->pTail = NULL; //处理一下尾指针，将尾指针置空
}🔑 解读：
① 首先断言防止传入的 pQ 为空，这里还要放置队列为空，如果队列为空还要求出队的话会出问题的，所以这里要断言一下 QueueIfEmpty 为假。
② 思路草图如下：
出数据需要释放，和销毁一样，这里使用一个类似于信标性质的指针来记录 pHead 的下一个节点，之后我们就可以大胆地释放 pHead 而不用担心找不到了。free 掉之后更新头即可，令头指针指向 headNext 即可。
📌 注意：这里还要考虑一个问题，如果队内都被删完了，pHead 往后走指向空，但是 pTail 仍然指向那块已经被 free 掉的空间。pTail 就是一个典型的野指针。
我们可以不用担心 pHead，因为后面没有数据他会自然指向 NULL，但是我们这里得关注 pTail ！我们需要手动处理一下它：
如果 pHead 为空，我们就把 pTail 也置为空即可。
if(pQ->pHead == NULL) //如果pHead为空
pQ->pTail = NULL; //处理一下尾指针，将尾指针置空
0x05 返回队头数据（QueueFront）
💬 Queue.h
QueueDataType QueueFront(Queue* pQ); //返回队头数据💬 Queue.c
/* 返回队头数据 */
QueueDataType QueueFront(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
assert(!QueueIfEmpty(pQ)); //防止队列为空
return pQ->pHead->data;
} 🔑 解读：
① 首先断言防止传入的 pQ 为空，这里我们还是要断言一下 QueueIfEmpty 为假，因为如果队内没有数据，还返回个锤子数据呢。
② 这里直接返回头的数据即可，特别简单没有什么好讲的。
0x06 返回队尾数据（QueueBack）
💬 Queue.h
QueueDataType QueueBack(Queue* pQ); //返回队尾数据💬 Queue.c
/* 返回队尾数据 */
QueueDataType QueueBack(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
assert(!QueueIfEmpty(pQ)); //防止队列为空
return pQ->pTail->data;
}
🔑 解读：
① 首先断言防止传入的 pQ 为空，断言一下 QueueIfEmpty 为假。
② 这里直接返回队尾的数据即可。
0x07 求队列大小（QueueSize）
💬 Queue.h
int QueueSize(Queue* pQ); //求队列大小💬 Queue.c
/* 求队列大小：计数器法 */
int QueueSize(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
int count = 0; //计数器
QueueNode* cur = pQ; //创建遍历指针cur
while(cur != NULL) {
++count; //计数+1
cur = cur->next; //移动指针cur
}
return count;
}
🔑 解读：这里我们采用计数器法来求大小即可，调用一次就是 O(N) ，也没什么不好的。
① 首先断言防止传入的 pQ 为空。
② 创建计数器变量和遍历指针 cur，遍历整个队列并计数，最后返回计数的结果即可。
0x08 完整代码
💬 Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QueueDataType; //队列类型
typedef struct QueueNode {
struct QueueNode* next; //指向下一个节点
QueueDataType data; //数据
} QueueNode;
typedef struct Queue {
QueueNode* pHead; //头指针
QueueNode* pTail; //尾指针
} Queue;
void QueueInit(Queue* pQ); //队列初始化
void QueueDestroy(Queue* pQ); //销毁队列
bool QueueIfEmpty(Queue* pQ); //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x); //入队
void QueuePop(Queue* pQ); //出队
QueueDataType QueueFront(Queue* pQ); //返回队头数据
QueueDataType QueueBack(Queue* pQ); //返回队尾数据
int QueueSize(Queue* pQ); //求队列大小
💬 Queue.c
#include "Queue.h"
/* 队列初始化：将头尾指针置为NULL */
void QueueInit(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
pQ->pHead = pQ->pTail = NULL; //将头尾指针置空
}
/* 销毁队列：free掉所有队列元素并将头尾置空 */
void QueueDestroy(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
QueueNode* cur = pQ; //创建遍历指针cur
while(cur != NULL) { //cur不为空就进入循环
QueueNode* curNext = cur->next; //信标指针curNext，防止释放cur后找不到其下一个节点
free(cur); //释放cur当前指向的节点
cur = curNext; //移动指针cur
}
pQ->pHead = pQ->pTail = NULL; //置空干掉野指针
}
/* 判断队列是否为空 */
bool QueueIfEmpty(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
return pQ->pHead == NULL; //如果成立则为True，不成立则为False
}
/* 入队：队尾入数据，对头出数据。如果是第一个入队的则既要当头又当尾 */
void QueuePush(Queue* pQ, QueueDataType x) {
assert(pQ); //防止传入的pQ为空
/* 创建新节点：创建一个大小为QueueNode的空间 */
QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
/* 检查malloc */
if(new_node == NULL) {
printf("malloc failed!\n");
exit(EXIT_FAILURE);
}
/* 放置 */
new_node->data = x; //待插入的数据
new_node->next = NULL; //默认为空
/* 入队：
*【思路草图】
* 情况1：队列为空：既当头又当尾
* [new_node]
* ↑ ↑
* pHead pTail
*
* 情况2：队列不为空：队尾入数据
* [] -> [] -> [] -> [] -> [new_node]
* pHead pTail pTail->next
* ↓ ↑
* ----------→ pTail（更新尾指针）
*/
if(pQ->pHead == NULL) { //情况1: 队列为空
pQ->pHead = pQ->pTail = new_node; // 既当头又当尾
} else { //情况2: 队列不为空
pQ->pTail->next = new_node; // 在现有尾的后一个节点放置new_node
pQ->pTail = new_node; // 更新pTail，使它指向新的尾
}
}
/* 出队：队尾入数据，对头出数据 */
void QueuePop(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
assert(!QueueIfEmpty(pQ)); //防止队列为空
/* 出队:
*【思路草图】
* [free] -> [] -> [] -> []
* pHead headNext
* ↓ ↑
* -------→ pHead（更新头指针）
*/
QueueNode* headNext = pQ->pHead->next; //信标指针HeadNext，防止释放pHead后找不到其下一个节点
free(pQ->pHead);
pQ->pHead = headNext; //更新头
/* 如果队内都被删完了，不处理pTail就会带来野指针的隐患
* 【思路草图】
* NULL 已经被free掉的空间！
* ↑ ↑ （野指针）
* pHead(因为HeadNext是NULL) pTail
*/
if(pQ->pHead == NULL) //如果pHead为空
pQ->pTail = NULL; //处理一下尾指针，将尾指针置空
}
/* 返回队头数据 */
QueueDataType QueueFront(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
assert(!QueueIfEmpty(pQ)); //防止队列为空
return pQ->pHead->data;
}
/* 返回队尾数据 */
QueueDataType QueueBack(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
assert(!QueueIfEmpty(pQ)); //防止队列为空
return pQ->pTail->data;
}
/* 求队列大小：计数器法 */
int QueueSize(Queue* pQ) {
assert(pQ); //防止传入的pQ为空
int count = 0; //计数器
QueueNode* cur = pQ; //创建遍历指针cur
while(cur != NULL) {
++count; //计数+1
cur = cur->next; //移动指针cur
}
return count;
}
💬 Test.c
#include "Queue.h"
void TestQueue1() {
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
//QueuePop(&q);
QueueDestroy(&q);
}
void TestQueue2() {
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//假设先入了1 2，让1出来，再继续入，它的顺序还是不会变。
// 永远保持先进先出的，无论是入了两个出两个，再入再出，还是全部入完了再出，都是不会变的。这就是队列的性质
while(!QueueIfEmpty(&q)) {
QueueDataType front = QueueFront(&q);
printf("%d ", front);
QueuePop(&q); //pop掉去下一个
}
printf("\n");
QueueDestroy(&q);
}
int main(void) {
TestQueue2();
return 0;
}
参考资料：
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
百度百科[EB/OL]. []. https://baike.baidu.com/.
📌 笔者：王亦优
📃 更新： 2021.11.17
❌ 勘误： 无
📜 声明： 由于作者水平有限，本文有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！
本篇完。