链式队列：高效实现O(1)入队出队

引言在之前的文章中我们系统学习了栈结构顺序栈和链栈。栈是后进先出LIFO的结构而今天要讲解的队列Queue则是先进先出FIFOFirst In First Out的结构。队列在计算机科学中应用极为广泛操作系统的任务调度、消息队列、打印队列、网络数据包缓冲……几乎所有需要排队处理的场景都离不开队列。本文将详细讲解链式队列的完整实现。链式队列使用链表节点动态存储元素配合头尾指针实现 O(1) 的入队和出队操作。第一部分链式队列的设计原理一、核心数据结构链式队列由两个结构体组成// 1. 节点结构体 typedef struct Queuenode { ElempType val; // 数据域 struct Queuenode* next; // 指针域指向下一个节点 } Queuenode, *PQueuenode; // 2. 队列管理结构体带头结点 typedef struct LinkQueue { PQueuenode front; // 队头指针指向头结点 PQueuenode rear; // 队尾指针指向最后一个节点 } LinkQueue, *PLinkQueue;二、关键设计头结点 双指针三、队列状态判断状态frontrear条件空队列指向头结点指向头结点front rear有元素指向头结点指向最后一个节点front ! rear一个元素指向头结点指向唯一节点front-next rear已销毁NULLNULLfront NULL rear NULL四、为什么需要头结点和尾指针设计要素作用头结点统一空队列和非空队列的插入/删除操作避免判空特殊处理front 指针始终指向头结点方便出队操作O(1)rear 指针始终指向最后一个节点方便入队操作O(1)第二部分初始化与销毁一、创建节点PQueuenode buynode(ElempType val) { PQueuenode p (PQueuenode)malloc(sizeof(Queuenode)); if (p NULL) return NULL; p-next NULL; p-val val; return p; }二、初始化带头结点void InitLinkQueue(PLinkQueue ps) { assert(ps ! NULL); // 创建头结点 PQueuenode p buynode(0); if (p NULL) return; // 空队列front 和 rear 都指向头结点 ps-rear p; ps-front p; }初始化后的状态三、销毁void Destroy(PLinkQueue ps) { assert(ps ! NULL); if (Isempty(ps)) return; // 逐个释放所有节点包括头结点 while (ps-front ! NULL) { PQueuenode p ps-front; ps-front p-next; free(p); } // 指针置空 ps-rear NULL; }清空 vs 销毁// 清空保留头结点只释放数据节点 void Clear(PLinkQueue ps) { assert(ps ! NULL); if (Isempty(ps)) return; while (ps-front-next ! NULL) { PQueuenode p ps-front-next; ps-front-next p-next; free(p); } ps-rear ps-front; // rear 回到头结点 } // 销毁释放所有节点包括头结点 void Destroy(PLinkQueue ps) { // 释放所有节点指针置 NULL }操作头结点frontrear后续使用清空保留指向头结点指向头结点可继续使用销毁释放NULLNULL需重新初始化第三部分核心操作实现一、入队Pushbool Push(PLinkQueue ps, ElempType val) { assert(ps ! NULL); // 1. 创建新节点 PQueuenode p buynode(val); if (p NULL) return false; // 2. 插入到队尾 ps-rear-next p; // 当前最后一个节点的 next 指向新节点 ps-rear p; // rear 后移 return true; }入队过程图解入队的特殊情况// 空队列入队// 入队前front rear 头结点// 入队后front 头结点, rear 新节点// 代码逻辑完全适用无需特殊处理二、出队Popbool Pop(PLinkQueue ps, ElempType* pval) { assert(ps ! NULL pval ! NULL); if (Isempty(ps)) return false; // 1. 获取队头节点头结点后的第一个节点 PQueuenode p ps-front-next; // 2. 获取数据 *pval p-val; // 3. 跳过被删除的节点 ps-front-next p-next; // 4. 特殊处理如果删除的是最后一个节点rear 要回退 if (p ps-rear) { ps-rear ps-front; } // 5. 释放节点 free(p); return true; }注意原代码中缺少了rear回退的特殊处理。当队列只有一个元素时出队后rear应该指向头结点。修正后的代码bool Pop(PLinkQueue ps, ElempType* pval) { assert(ps ! NULL pval ! NULL); if (Isempty(ps)) return false; PQueuenode p ps-front-next; *pval p-val; ps-front-next p-next; // ★ 关键删除的是最后一个节点时更新 rear if (p ps-rear) { ps-rear ps-front; } free(p); return true; }三、获取队头和队尾// 获取队头元素 bool Getfront(PLinkQueue ps, ElempType* pval) { assert(ps ! NULL); if (Isempty(ps)) return false; *pval ps-front-next-val; // 头结点后的第一个节点 return true; } // 获取队尾元素 bool Getrear(PLinkQueue ps, ElempType* pval) { assert(ps ! NULL); if (Isempty(ps)) return false; *pval ps-rear-val; // 直接通过 rear 指针获取 return true; }四、判空bool Isempty(const PLinkQueue ps) { assert(ps ! NULL); return ps-front ps-rear; }五、获取元素个数int Getsize(const PLinkQueue ps) { assert(ps ! NULL); int n 0; for (Queuenode* p ps-front-next; p ! NULL; p p-next) { n; } return n; }注意这里的获取大小是 O(n) 遍历。如果想 O(1)可以在LinkQueue结构体中添加cursize成员。第四部分完整操作一览时间复杂度分析操作时间复杂度说明初始化O(1)创建头结点判空O(1)比较 front 和 rear入队 (Push)O(1)直接在 rear 后插入出队 (Pop)O(1)删除 front-next获取队头O(1)读取 front-next-val获取队尾O(1)读取 rear-val获取大小O(n)需要遍历可优化为 O(1)清空/销毁O(n)逐个释放节点操作要点速查第六部分链式队列 vs 顺序队列对比项链式队列顺序队列循环队列存储方式离散节点连续数组容量限制无内存足够即可有预分配或扩容入队/出队O(1)O(1)内存开销每节点多一个指针仅数据空间缓存友好差内存不连续好内存连续实现复杂度稍复杂需要处理循环下标适用场景元素数量不可预估元素数量可预估总结一、链式队列的核心原理二、操作复杂度速查操作时间复杂度关键步骤入队O(1)rear-next p; rear p;出队O(1)p front-next; front-next p-next; free(p);获取队头O(1)front-next-val获取队尾O(1)rear-val判空O(1)front rear三、一句话记忆链式队列用 front 和 rear 两个指针分别指向头结点和尾节点入队时在 rear 后面插入并更新 rear出队时删除 front 后面的节点实现 O(1) 的入队和出队操作。出队时如果删除了最后一个节点必须将 rear 回退到头结点。