【数据结构入坑指南（六）】--《从初始化到销毁：手把手教你打造健壮的队列实现》
🔥@晨非辰Tong：个人主页
👀专栏：《C语言》、《数据结构与算法》、《数据结构与算法刷题集》
💪学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”
引言：刚征服了“后进先出”的栈，现在让我们迎接一个全新的挑战——队列。这个“先进先出”的数据结构将带你体验截然不同的设计思维。本文将手把手带你用链表实现一个队列，为后续学习树形结构打下坚实基础。
目录
一、队列初探：核心概念与结构设计
1.1 深入理解“先进先出”（FIFO）
--概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有“先进先出”与栈截然不同的的特点。
- 入队列：进行插入操作的一端称为队尾；
- 出队列：进行删除操作的一端称为队头；
1.1.1 关键抉择：链表 vs 数组
--那么实现队，底层结构选择数组实现还是链表实现呢？
：那当然是都可以实现，此时—>二者的插入、删除算法操作总会有一个时间复杂度为O(1)。但是链表有补救操作（尾插为O(N)）——>定义一个指针始终指向尾节点，这就不会导致还要进行循环遍历找到尾节点来插入。
1.2 搭建队列的“骨架”
--结构，因为底层实现是链表，就要将节点结构、队列结构一同定义。
typedef int QDataType; //链表节点结构 typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; //队列结构 typedef struct Queue { QueueNode* phead; QueueNode* ptail; }Queue;二、核心功能实现：从零搭建完整队列
--下面也是实现一些擦插入、删除操作，先进行初始化
2.1 准备工作：搭建稳固的基础
2.1.1 队列初始化：一切从这里开始
--初始，头、尾指针均指向NULL。
//初始化 void QueueInit(Queue* pq) { assert(pq);//防止空指针 pq->phead = pq->ptail = NULL; }
2.1.2 判空检测：守护队列的“安全门”
--此操作，在出队列时，判断是否有节点。
bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }2.2 入队操作：在队尾优雅地添加数据
Queue.c #include "Queue.h" //入队（尾插） void QueuePush(Queue* pq, QDataType x) { assert(pq); //创建新节点 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("mallpc fail!"); exit (1); } newnode->data = x; newnode->next = NULL; //刚开始，链表为空，没有节点 if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode;//尾指针链接新节点 pq->ptail = pq->ptail->next;//尾指针移动到新节点 } } test.c #include "Queue.h" void test01() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); } int main() { test01(); return 0; }--插入节点就要先申请一份节点大小的空间，其中节点结构：Data存要求插入的数据，next指 NULL。
--刚开始，队列中没有节点，新插入的节点为第一节点，导致头指针、尾指针都指向新节点。
--以后直接是尾指针 next 指向新节点，然后尾指针移动到新节点。
2.3 出队操作：从队头安全地移除数据
Queue.c #include "Queue.h" //出队列 void QueuePop(Queue* pq) { assert(!QueueEmpty(pq));//队列是否有节点 //队列中只有一个节点 if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { //创建指针将下个节点保存 QueueNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } } void test01() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePop(&q); QueuePop(&q); QueuePop(&q); QueuePop(&q); } int main() { test01(); return 0; }--操作前，先判断队列是否有节点，有节点才能出队列。
--没有节点，头指针、尾指针都指向空。
--否则，创建新 next 指针将第二节点的地址先保存（也就是头指针指向的结构体中的 next 指针保存着地址），释放后，头指针指向新指针。
2.4 销毁队列：善始善终的内存管理
--销毁队列，需要遍历队列依次释放空间（注意提前保存下一节点的地址），最后将头指针、尾指针置空。
Queue.c #include "Queue.h" //销毁 void QueueDesTroy(Queue* pq) { assert(pq); QueueNode* pcur = pq->phead; while (pcur) { //保存下一节点的地址 QueueNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; }三、功能扩展：让队列更加强大
3.1 窥探队首：获取但不破坏
--因为事先已经定义了指向头节点的指针，且指向的结构体中存在存储当前节点数据的 data 变量，直接返回 data 即可。
Queue.c #include "Queue.h" //取队头数据 QDataType QueueFront(Queue* pq) { assert(!QueueEmpty(pq)); return pq->phead->data; } test.c #include "Queue.h" void test01() { //初始化 Queue q; QueueInit(&q); //入队 QueuePush(&q, 1); QueuePop(&q); QueuePush(&q, 2); QueuePop(&q); QueuePush(&q, 3); QueuePop(&q); QueuePush(&q, 4); //取队首 printf("%d\n", QueueFront(&q)); } int main() { test01(); return 0; } --随着phead指向的改变，其指向的结构体中访问到的的data、next也随之改变。
3.2 窥探队尾：快速访问末端元素
--与上面的取队首数据算法思路一样，也是事先定义了指向尾节点的指针，且指向的结构体中存在存储当前节点数据的 data 变量，直接返回 data 即可。
Queue.c #include "Queue.h" //取队尾数据 QDataType QueueBack(Queue* pq) { assert(!QueueEmpty(pq)); return pq->ptail->data; } test.c #include "Queue.h" void test01() { //初始化 Queue q; QueueInit(&q); //入队 QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); //取队尾 printf("%d->", QueueBack(&q)); } int main() { test01(); return 0; }
3.3 清点元素：高效统计队列大小
--这就需要进行循环内遍历到尾节点，统计个数
Queue.c #include "Queue.h" //队列有效元素个数 int QueueSize(Queue* pq) { assert(pq); QueueNode* pcur = pq->phead; int size = 0; while (pcur) { ++size; pcur = pcur->next; } return size; }四、完整代码展示：理论与实践的完美结合
4.1 Queue.h：队列的“蓝图”与接口
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; //链表节点结构 typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; //队列结构 typedef struct Queue { QueueNode* phead;//指向队头 QueueNode* ptail;//指向队尾 }Queue; //初始化 void QueueInit(Queue* pq); //判队列是否为空 bool QueueEmpty(Queue* pq); //入队（尾插） void QueuePush(Queue* pq, QDataType x); //出队列(队头) void QueuePop(Queue* pq); //取队头数据 QDataType QueueFront(Queue* pq); //取队尾数据 QDataType QueueBack(Queue* pq); //队列有效元素个数 int QueueSize(Queue* pq); 4.2 Queue.c：核心逻辑的完整实现
#include "Queue.h" //初始化 void QueueInit(Queue* pq) { assert(pq);//不能传空指针 pq->phead = pq->ptail = NULL; } //入队（尾插） void QueuePush(Queue* pq, QDataType x) { assert(pq); //创建新节点 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("mallpc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; //刚开始，链表为空，没有节点 if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode;//尾指针链接新节点 pq->ptail = pq->ptail->next;//尾指针移动到新节点 } } //判队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; } //出队列 void QueuePop(Queue* pq) { assert(!QueueEmpty(pq)); //队列中只有一个节点 if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { //创建指针将下个节点保存 QueueNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } } //取队头数据 QDataType QueueFront(Queue* pq) { assert(!QueueEmpty(pq)); return pq->phead->data; } //取队尾数据 QDataType QueueBack(Queue* pq) { assert(!QueueEmpty(pq)); return pq->ptail->data; } //队列有效元素个数 int QueueSize(Queue* pq) { assert(pq); QueueNode* pcur = pq->phead; int size = 0; while (pcur) { ++size; pcur = pcur->next; } return size; } //销毁 void QueueDesTroy(Queue* pq) { assert(pq); QueueNode* pcur = pq->phead; while (pcur) { //保存下一节点的地址 QueueNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; }4.3 test.c：功能验证与测试用例
#include "Queue.h" void test01() { //初始化 Queue q; QueueInit(&q); //入队 QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); //出队 /*QueuePop(&q); QueuePop(&q); QueuePop(&q); QueuePop(&q);*/ //取队首 /*printf("%d->", QueueFront(&q)); QueuePop(&q); printf("%d->", QueueFront(&q)); QueuePop(&q); printf("%d->", QueueFront(&q)); QueuePop(&q); printf("%d->", QueueFront(&q));*/ //取队尾 //printf("%d->", QueueBack(&q)); //有效数据 printf("size：%d\n", QueueSize(&q)); } int main() { test01(); return 0; }回顾：
【面试高频数据结构（五）】--《手把手实现栈结构：附带完整代码与注释，深度揭秘数组实现香在哪？》
【面试高频数据结构（四）】--《超越单链表的局限：双链表“哨兵位”设计模式，如何让边界处理代码既优雅又健壮？》
结语：队列的实现标志着你在线性数据结构领域已登堂入室。接下来，二叉树与堆的学习将带你进入非线性数据结构的新世界。有趣的是，队列正是基于堆实现的——现在打下的队列基础，将在下一章绽放新的光彩。
