队列Queue队列像食堂排队打饭先来的人先打到饭走人后来的人只能站队尾先进先出FIFO绝对公平。核心思想队列是受限的线性表一端队尾只能进入队 Push另一端队头只能出出队 Pop中间不能动。和栈相反栈是 LIFO队列是 FIFO。我用带头尾指针的链式队列实现也可以用数组phead指向队头节点出队端。ptail指向队尾节点入队端。size节点数量。关键设计用size维护长度。如果没有size求队列长度要遍历 O(n)有了size入队出队时顺手/--判空和求长度都 O(1)。另外头尾双指针让入队尾插和出队头删都 O(1)——如果只有头指针尾插要遍历找尾就 O(n) 了。数据结构定义typedefstructQueueNode// 链队节点{QDatatype data;structQueueNode*next;}QNode;typedefstructQueue// 队列管理结构头尾指针 size{QNode*phead;// 队头QNode*ptail;// 队尾intsize;// 节点数}Que;内存模型入队了 1,2,3出队了 1 次剩 2,3phead ptail ↓ ↓ [2|next] - [3|next] - NULL 队头 队尾 出队从 phead 删 入队在 ptail 后插 size 2两段式设计QNode是链表节点Que是管理结构包住头尾指针和 size。外部只持有Que不直接碰QNode封装性好。关键操作实现初始化 QueInitvoidQueInit(Que*pq){assert(pq);pq-size0;pq-pheadpq-ptailNULL;// 头尾同时置空}逐行解释空队列没有节点头尾指针都置 NULL。必须同时置空如果只置phead不置ptailptail残留野指针第一次入队判ptailNULL会误判。入队 QuePushvoidQuePush(Que*pq,QDatatype x){assert(pq);QNode*newnode(QNode*)malloc(sizeof(QNode));if(newnodeNULL)// malloc 检查{perror(malloc fail);return;}newnode-nextNULL;newnode-datax;if(pq-ptailNULL)// 空队列{pq-pheadpq-ptailnewnode;// 头尾都指向新节点}else// 非空尾插{pq-ptail-nextnewnode;// 原尾的 next 指向新节点pq-ptailnewnode;// 更新尾指针}pq-size;}逐行解释入队 尾插。空队列时新节点既是队头也是队尾必须同时更新phead和ptail只更新一个会丢指针。非空时让原尾节点的next指向新节点再更新ptail指向新尾。size维护长度。陷阱空队列入队只更新ptail忘更新phead导致phead仍为 NULL出队时phead-data段错误。出队 QuePopvoidQuePop(Que*pq){assert(pq);assert(pq-size!0);// 空队列不能出if(pq-phead-nextNULL)// 只剩一个节点{free(pq-phead);pq-pheadpq-ptailNULL;// 头尾都置空变空队列}else{QNode*nextpq-phead-next;// 先存第二个节点free(pq-phead);// 再删队头pq-pheadnext;// 头指针后移}pq-size--;}逐行解释出队 头删。分两种情况只剩一个节点删完后队列变空必须把ptail也置 NULL否则ptail变悬空指针下次入队ptail-next段错误。多个节点用next先存住原队头的下一个防 free 后丢失再free队头头指针后移。陷阱最高频只剩一个节点出队时忘置空ptail→ 悬空指针。这是链式队列最经典的 bug。取队头 QueFront / 取队尾 QueBackQDatatypeQueFront(Que*pq){assert(pq);assert(pq-phead);// 队列不能空returnpq-phead-data;}QDatatypeQueBack(Que*pq){assert(pq);assert(pq-ptail);// 队列不能空returnpq-ptail-data;}逐行解释双指针的红利——队头队尾都 O(1) 可取。assert防止空队列取数据。注意QueBack是链式队列的优势数组循环队列取队尾稍麻烦。判空 QueEmptyboolQueEmpty(Que*pq){assert(pq);returnpq-size0;// 用 size 判空O(1)}逐行解释用size判空也可以用phead NULL等价。size维护后判空和求长都 O(1)。求长度 QuesizeintQuesize(Que*pq){assert(pq);returnpq-size;// 直接返回O(1)}逐行解释size的价值——不用遍历。命名问题这里叫Quesize小写 s但项目其他函数是QuePush/QuePop大写 P命名风格不统一应改成QueSize。销毁 QueDestroy已修复voidQueDestroy(Que*pq){assert(pq);QNode*curpq-phead;while(cur){QNode*nextcur-next;free(cur);// 先释放当前节点再移动到下一个否则会内存泄漏curnext;}pq-pheadpq-ptailNULL;pq-size0;}逐行解释逐个free节点。必须先存next再free(cur)否则free后cur-next读不到UAF。修复前的 bug原来写成cur NULL; cur next;——先cur NULL再cur next等于什么都没释放free调用根本没发生所有节点内存泄漏。正确是free(cur)再cur next。这是「想置空却忘了 free」的典型错误。复杂度分析操作时间复杂度说明入队 PushO(1)尾插ptail 直接定位出队 PopO(1)头删phead 直接定位取队头 / 队尾O(1)双指针判空 / 求长度O(1)维护 size销毁O(n)逐个释放对比数组队列数组队列出队要搬移所有元素 O(n)除非用循环队列链式队列头删 O(1)所以队列更适合用链表实现栈更适合用数组因为栈只在顶操作数组天然合适。常见陷阱清单只剩一个节点出队不置空ptail→ 悬空指针下次入队段错误最高频。空队列判ptailNULL入队时只更新一个指针→ 丢队头或队尾。销毁只置空不free修复前的 bug→ 内存泄漏。销毁先free后取next→ UAF。#include queue.h用尖括号自定义头文件应用双引号queue.h尖括号是给系统头文件的。命名不统一Quesize应改QueSize。我的实现 vs 教科书实现设计正确头尾双指针 size入队出队取头尾全 O(1)结构标准。已修复销毁泄漏free(cur)顺序正确。残留问题test.c用#include queue.h尖括号应用引号Quesize命名不统一。缺接口没有从队头遍历打印的接口测试代码直接在 main 里循环出队打印。vs 循环队列链式队列无限扩容但每节点有指针开销循环队列用定长数组 取模省空间但要处理判空判满。拓展知识点变体与进阶循环队列Circular Queue用定长数组实现front/rear指针取模复用空间。难点是判空判满——空是frontrear满也是frontrear冲突两种解法①牺牲一个单元rear1front为满②额外用size计数本项目链队的思路。双端队列 Deque两端都能入队出队std::deque底层是分块数组支持 O(1) 头尾操作 随机访问。优先队列Priority Queue出队按优先级而非时间底层用堆见 Binary_Tree 模块O(log n)。阻塞队列线程间通信的基础队空时取阻塞、队满时入阻塞。常见考点必刷用两个栈实现队列入队压栈 A出队时若栈 B 空把 A 全倒进 B 再弹出。循环队列判空判满牺牲单元法 vs size 计数法。BFS 层序遍历队列是 BFS 的核心数据结构见 Binary_Tree 的TreeLevelOrder。滑动窗口最大值单调队列O(n)。与其他结构的关系队列是 BFS、层序遍历、任务调度的基础。本项目Binary_Tree模块复用了一个queue存Treenode*来做层序遍历和完全二叉树判断——这是「数据结构组合使用」的典型。队列和栈是受限线性表的两兄弟可互相模拟。一句话记忆法队列先进先出FIFO尾入头出头尾双指针 size 让操作全 O(1)单节点出队别忘置空 ptail销毁先存 next 再 free。#DataStructure #CS #Queue #FIFO #受限线性表