循环链队：只用尾指针实现O(1)入队出队的队列设计

队列的 FIFO 大家都会背但真让你在 PTA 上把一个队列用链表实现出来很多人会卡在同一个地方链队到底是带头指针还是带尾指针要不要头结点如果只给一个尾指针能不能把入队和出队都做到 O(1)今天聊的这道“循环链队只有尾指针的循环单链表”就是把队列和循环链表两个知识点叠在一起考专门检验你对“指针到底在指向谁”这件事是不是真的理解透了。这个结构非常讨巧普通链队一般用 front rear 两个指针一个负责出队一个负责入队逻辑清楚但代码里多一个变量多一套维护逻辑。而循环单链表里队尾节点的 next 指针不再指向 NULL而是回头指向队头。这就意味着只要握着尾指针 rear就能通过rear-next摸到队头。一个指针同时掌握头尾两端入队、出队都是 O(1)空间上也只多一个节点的开销。这篇文章我会从设计思路讲起把结构体定义、初始化、判空、入队、出队、取队头、完整测试代码全部拆开最后把我自己调试时踩过的坑一步一步复盘给你。适合正在刷 PTA 数据结构题、复习考研数据结构或者想彻底搞懂链式队列底层逻辑的读者。1. 设计思路为什么只有尾指针也能实现队列1.1 关键洞察尾巴上带着队头的地址先回顾一下队列最基本的规则队尾进队头出先进先出。如果你用单链表存队列最直接的想法是设置两个指针front 指向队头rear 指向队尾。入队时在 rear 后面挂新节点出队时把 front 指向的节点摘下来。这个方案没有任何问题但它不是唯一解。循环链表给了一种“偷懒”的可能既然 rear 是队尾节点只要把整个链表做成环让队尾节点的 next 重新指向队头那么rear-next就天然是队头地址。这种情况下 front 指针完全没有存在的必要我只要搞清楚 rear 是谁就等于同时知道了队头和队尾。你可以想象一个环形跑道站在终点回头看起点就在你身后不需要另一个人专门站在起点帮你喊位置。这个设计的本质是用“循环”这一个约束条件替代了“额外一个指针”这个实现成本。数据结构里很多精巧的优化都是这么来的不是增加信息而是改变信息的组织方式让已有的信息能被复用。1.2 这样设计到底赢在哪第一个赢的点是操作复杂度。如果用普通单链表只保留头指针入队时必须从头遍历到尾时间复杂度 O(n)如果只保留尾指针但不做循环出队时无法快速找到队尾前驱难以维护尾指针。而循环链队的尾指针设计让入队在 rear 后插入O(1)出队直接操作 rear-nextO(1)两头都是常数时间。第二个赢的点是代码量。维护一个指针比维护两个指针少了很多分支判断也不容易出现“front 和 rear 一个变了另一个没跟上”这类状态不一致的 bug。第三个赢的点是空间利用。链式存储本身是动态分配的不像顺序存储的循环队列需要提前规定容量也不会出现“假溢出”这种明明有空间却无法入队的情况。只要内存还能分配队列就能继续生长。当然这个设计也有它难的地方空队列怎么表示队列里只有一个节点的时候这个节点要自己指向自己形成一个自环这个状态非常容易写错。后面我会专门讲这三个边界情况。1.3 三种链队实现方案对比实现方式入队出队所需指针主要问题普通单链表 头指针O(n)O(1)1 个入队要遍历到尾效率差普通单链表 头尾双指针O(1)O(1)2 个指针多维护逻辑稍重循环单链表 尾指针O(1)O(1)1 个空表和单节点场景要单独处理从表格能看出来循环链队 尾指针在时间复杂度和空间开销上都很理想唯一的代价是需要你谨慎处理边界情况。这也正是 PTA 这类题目喜欢考它的原因代码不多但每处都藏着细节。2. 基本操作的落地初始化、判空、入队2.1 结构体与二级指针先给出结构体定义typedef int ElemType; typedef struct QNode { ElemType data; struct QNode *next; } QNode;这个结构体和普通单链表节点一模一样唯一的差别体现在使用方式上。队列本身不需要单独定义结构体来存 front 和 rear因为只有一个 rear 指针直接用QNode *rear就能代表整个队列。接下来的重点来了很多初学者写链队函数时把参数写成QNode *rear结果入队后队列没变化或者出队后队列没变短就是因为这个参数写错了。原因很简单C 语言函数参数默认按值传递。如果函数内部给rear赋了新值比如rear s这只会修改形参外部实参依然指向旧节点修改不会传出去。所以要修改调用者手里的那个指针值必须传递指针的地址也就是二级指针QNode **rear。凡是需要改变 rear 这个变量的函数比如入队、出队、初始化、销毁都要用二级指针只是读取状态的函数比如判空、取队头用一级指针就够了。2.2 初始化和判空void InitQueue(QNode **rear) { *rear NULL; } int IsEmpty(QNode *rear) { return rear NULL; }初始化的动作非常简单让 rear 指向空。但这里有一个值得琢磨的点为什么不创建一个头结点让空队的 rear 指向头结点如果你带头结点空队状态就变成rear head判断起来也不算麻烦。但题目明确说的是“只有尾指针的循环单链表”无头结点版本最贴合字面意思也最考验细节。空队的判断条件是rear NULL不是rear-next rear——因为空队时根本不存在任何节点去访问rear-next已经是空指针解引用了直接崩溃。我见过有人试图用“rear 指向一个自己形成的环”来表示空队也就是创建一个节点让它的 next 指向自己。这种做法不是不行但它额外引入了一个“哨兵节点”在无头结点语境下反而把问题搞复杂了。这里我们就坚持没有节点rear 就是 NULL。2.3 入队两句赋值一个更新入队函数要处理的场景有两个空队插入第一个节点和非空队插入。这两种情况的代码差别很微妙但一步都不能错。int EnQueue(QNode **rear, ElemType x) { QNode *s (QNode *)malloc(sizeof(QNode)); if (s NULL) { return 0; // 内存分配失败 } s-data x; if (*rear NULL) { // 空队新节点自己指向自己形成自环 s-next s; *rear s; } else { // 非空队新节点指向原队头 s-next (*rear)-next; // 原队尾节点不再指向队头改为指向新节点 (*rear)-next s; // 新节点成为新的队尾 *rear s; } return 1; }空队分支里s-next s是必须的。如果不做这一步新节点的 next 就是个悬空的野指针后面打印队列或者再次入队时遍历就会变成访问非法地址。一个节点的循环链表也是循环链表它的循环点就是它自己。非空分支的三步顺序也不能乱s-next (*rear)-next先让新节点接上原来的队头保证新节点入列后整个环不会断。(*rear)-next s把旧队尾的 next 从“指向队头”改成“指向新节点”。*rear s更新尾指针让新节点成为新的队尾。如果把第二步和第三步交换先改*rear s再执行(*rear)-next s那实际上就是在对新节点自身的 next 赋值原来队头信息就丢了。这类指针操作顺序就是生命。3. 出队与取队头最考验边界意识的两段代码3.1 出队的三种情况出队是整个循环链队里最容易出 bug 的地方。因为删除操作会遇到三种不同情况而且每种情况的处理逻辑都不一样。int DeQueue(QNode **rear, ElemType *x) { if (*rear NULL) { return 0; // 队空出队失败 } QNode *front (*rear)-next; // 队头节点 *x front-data; // 取出队头元素值 if (front *rear) { // 情况一队列只有一个节点 // 此时 front 就是 rear删除后队列为空 free(front); *rear NULL; } else { // 情况二队列有至少两个节点 // 让队尾节点的 next 跳过原队头直接指向新队头 (*rear)-next front-next; free(front); } return 1; }为什么单节点要单独处理因为删除这个节点后原来的循环链表就一个节点都不剩了rear 必须变成 NULL。如果你不把*rear置空rear 就还指着已经被 free 掉的节点地址后面一旦执行IsEmpty它以为队列非空一旦执行PrintQueue它就拿着一块已经释放的内存开始读数据轻则乱码重则段错误。多节点的情况就轻松很多。front 是队头rear 是队尾删除队头后只要让 rear 的 next 跳过被删除的节点就行。rear 自己不用动因为队尾还是原来的队尾。3.2 取队头和销毁队列取队头比出队少了一个删除动作逻辑上更简单但同样要先判空。int GetHead(QNode *rear, ElemType *x) { if (rear NULL) { return 0; } *x rear-next-data; return 1; }前面的rear是一级指针因为这里不需要改变输出参数之外的任何状态。rear-next-data就是队头元素的值这一点再次呼应了设计核心队头就藏在尾指针的 next 里。再写一个销毁函数防止实验结束后内存泄漏void DestroyQueue(QNode **rear) { if (*rear NULL) { return; } QNode *p (*rear)-next; // 从队头开始 QNode *tmp; do { tmp p; p p-next; free(tmp); } while (p ! (*rear)-next); // 绕回队头时结束 *rear NULL; }销毁时先在 free 之前把p-next存好避免释放节点后还去访问它的成员。这条经验同样适用于出队和任何涉及删除节点的操作先保住后路再拆桥。4. 完整可运行程序与测试推演4.1 完整代码把上面的函数拼起来加上一个打印队列的辅助函数就是一段可以直接复制编译的完整程序。#include stdio.h #include stdlib.h typedef int ElemType; typedef struct QNode { ElemType data; struct QNode *next; } QNode; void InitQueue(QNode **rear) { *rear NULL; } int IsEmpty(QNode *rear) { return rear NULL; } int EnQueue(QNode **rear, ElemType x) { QNode *s (QNode *)malloc(sizeof(QNode)); if (s NULL) { return 0; } s-data x; if (*rear NULL) { s-next s; *rear s; } else { s-next (*rear)-next; (*rear)-next s; *rear s; } return 1; } int DeQueue(QNode **rear, ElemType *x) { if (*rear NULL) { return 0; } QNode *front (*rear)-next; *x front-data; if (front *rear) { free(front); *rear NULL; } else { (*rear)-next front-next; free(front); } return 1; } int GetHead(QNode *rear, ElemType *x) { if (rear NULL) { return 0; } *x rear-next-data; return 1; } void PrintQueue(QNode *rear) { if (rear NULL) { printf(空队列\n); return; } QNode *front rear-next; QNode *p front; do { printf(%d , p-data); p p-next; } while (p ! front); printf(\n); } void DestroyQueue(QNode **rear) { if (*rear NULL) { return; } QNode *p (*rear)-next; QNode *tmp; do { tmp p; p p-next; free(tmp); } while (p ! (*rear)-next); *rear NULL; } int main() { QNode *queue NULL; int x; InitQueue(queue); printf(初始化后判空结果%d\n, IsEmpty(queue)); EnQueue(queue, 1); EnQueue(queue, 2); EnQueue(queue, 3); printf(入队 1, 2, 3 后队列内容); PrintQueue(queue); if (DeQueue(queue, x)) { printf(出队元素%d\n, x); } printf(出队后队列内容); PrintQueue(queue); if (GetHead(queue, x)) { printf(当前队头元素%d\n, x); } if (DeQueue(queue, x)) { printf(再次出队元素%d\n, x); } printf(再出队后队列内容); PrintQueue(queue); if (DeQueue(queue, x)) { printf(第三次出队元素%d\n, x); } printf(第三次出队后队列内容); PrintQueue(queue); if (!DeQueue(queue, x)) { printf(空队出队失败符合预期\n); } DestroyQueue(queue); return 0; }注意到打印函数用的是do...while而不是while。原因在于只要队列非空队头节点就必须被打印一次哪怕它同时是队尾节点。如果写成while (p ! front)单节点队列时 p 一开始就等于 front循环体一次都不会执行打印结果为空很容易误导调试。4.2 逐步推演输出按照 main 函数的执行流程操作序列和队列状态如下顺序操作队列内容队头 → 队尾入队后 rear 指向1初始化空NULL2判空返回 1NULL3入队 111 的 next 指向自己节点 14入队 21, 22 的 next 指向 1节点 25入队 31, 2, 33 的 next 指向 1节点 36出队得到 12, 33 的 next 指向 2节点 3不变7取队头得到 22, 3节点 38出队得到 233 的 next 指向自己节点 39出队得到 3空NULL10再出队失败返回 0NULL重点看第 8 步到第 9 步之间发生了什么队列里只剩节点 3 时它是一个自环front 和 rear 是同一个节点。此时执行出队代码走进front *rear分支释放节点后把*rear NULL队列重新回到空状态。这一步就是循环链队最容易漏掉的边界处理。实际运行这段代码终端输出会是这样初始化后判空结果1 入队 1, 2, 3 后队列内容1 2 3 出队元素1 出队后队列内容2 3 当前队头元素2 再次出队元素2 再出队后队列内容3 第三次出队元素3 第三次出队后队列内容空队列 空队出队失败符合预期我建议你自己跑一遍然后把每次操作后的队列内容打印出来对照这张表。指针题光在脑子里推演是不够的尤其是循环链表亲手打印一轮节点地址变化比反复看十遍代码都管用。5. 实测遇到的四个坑5.1 出队最后一个节点后没置空这是我最早调试时卡得最久的问题。现象是这样的队列里还剩一个节点时出队返回的数据是正确的但后续再执行IsEmpty返回值是 0程序以为队列还有数据继续调用PrintQueue然后就在一个已经释放的节点上读取 next直接打印出乱码或者崩溃。原因就是出队函数只释放了节点没有把rear改成 NULL。在单节点出队情况下rear指向的节点已经被 free 了但它仍然保存着那段地址。C 语言里 free 不会自动把指针置空所以你必须手动处理。解决方式我在代码里已经写了出队函数的参数必须是QNode **rear在单节点分支里执行*rear NULL。这类问题的排查思路也很简单在每次出队后打印rear的地址看它是否还指向已释放的内存。5.2 打印队列时死循环如果你没有用上面那种do...while (p ! front)的写法而是写成了while (p ! rear)当队列有多个节点时程序就会陷入死循环。逐步分析一下原因p 从队头开始往后移动会依次经过队头、中间节点、队尾。当 p 移动到队尾时它等于 rear循环条件p ! rear成立吗不成立循环应该停。但问题是队尾节点的数据还没有被打印出来。如果循环写得不好p 在队尾时跳出循环队尾数据就被漏掉了如果为了补打印队尾数据循环条件改成别的写法比如while (p ! rear-next)但由于每次进循环都要先取 p-next就可能在到达队尾后又绕回队头永远停不下来。这个坑的最佳解就是先存下队头地址再用 do while 遍历以“重新碰到队头”作为终止条件。遍历循环链表时找“起点”比找“终点”更可靠。5.3 二级指针写成一级指针典型场景是入队完成后外面打印队列发现最后一个元素根本没进队。比如入队 1、2、3打印结果却只有 1、2。原因是入队函数里*rear s这步没生效。函数声明的参数是QNode *rear而不是QNode **rear时函数内部对 rear 的赋值只改变了形参实参还是原来的队尾节点。新节点虽然被挂到了链表上但 rear 没有跟上打印时从队尾的 next 开始绕圈自然看不到新节点。怎么判断该用一级指针还是二级指针核心标准就一条函数的操作会不会改变“调用者持有的 rear 指针变量本身的值”。初始化、入队、出队、销毁都会改必须用二级指针判空、取队头不改用一级指针。5.4 指针解引用和内存释放的细节写(*rear)-next的时候括号不能省。C 语言里-的优先级比*高如果写成*rear-next实际解析成的是*(rear-next)因为 rear 本身不是结构体指针这是编译错误或者运行时崩溃。内存释放的问题也一样隐蔽。删除节点时要先把 next 保存下来再 free否则 free 之后再读front-next是未定义行为。虽然很多机器上碰巧还能读出正确值但这属于纯运气不应该是你依赖的行为。我自己的习惯是涉及删除节点的操作一律先做“记路”再释放QNode *next p-next; // 先记路 free(p); // 再释放 p next; // 最后移动指针这个习惯在销毁队列这种要连续释放多个节点的函数里尤其重要。6. 扩展与个人总结6.1 带头结点的方案怎么写既然上面提到过空队可以用哨兵节点表示这里就顺手给出一个带头结点的循环链队版本。核心思想是额外创建一个头结点 head让它的 next 一开始指向自己。rear 初始指向 head。空队条件简化为rear head。入队时在 rear 后面插入新节点然后更新 rear。出队时删除 head-next如果删除的是唯一的数据节点把 rear 恢复为 head。关键代码片段如下// 带头结点版本初始化 void InitQueue(QNode **rear) { *rear (QNode *)malloc(sizeof(QNode)); (*rear)-next *rear; // 头结点自环 } // 带头结点版本出队 int DeQueue(QNode **rear, ElemType *x) { if (*rear NULL || (*rear)-next *rear) { return 0; // 空队判断只有一个头结点自环 } QNode *head (*rear)-next; // 头结点 QNode *front head-next; // 真正的队头节点 *x front-data; if (front *rear) { // 这是最后一个数据节点 head-next head; // 恢复为只有头结点 *rear head; } else { head-next front-next; } free(front); return 1; }带头结点方案的好处是空队状态更容易识别不用判断 NULL。代价是多一个节点、多一层间接访问。PTA 题目如果明确要求不带头结点你就用前面无头结点版本如果只说了“循环链队”两种方案理论上都能跑通但提交前最好按照题目给定的函数接口来调整参数类型。这类题通常会在接口里写明到底让你传QNode *还是QNode **别想当然。6.2 这套代码万变不离其宗循环链队的核心考点无非三句话空队看 NULL、单节点看自环、多节点看 rear 的 next。无论 PTA 题目怎么变比如让你只补一个入队函数、只删队头返回元素、判断两个循环链队是否相等底层都是这三点。我刷题时习惯在草稿纸上先画三种状态下的链表图空、单节点、多节点。每写一个函数就对照三张图过一遍确认每个分支都处理到了。这个习惯让我少踩了非常多坑。链表类题目图比代码先动笔往往能救你一命。6.3 最后说点个人体会我第一次调这个题的时候卡在单节点出队那个分支整整两个小时。代码逻辑看着都对入队 3 个元素出队 2 个后队列打印就乱套。后来在每次出队后加了一句打印 rear 地址的调试语句才发现第三次出队时 rear 没有置空程序拿着一个悬空指针当队列在用。数据结构这种课很多时候不是思路想不明白而是边界状态没被认真对待。循环链队是我个人很喜欢的一道基础题因为代码量不大但把指针、循环链表、队列三个知识点全部串在了一起。你把它彻底调通了后面再学约瑟夫环、双向循环链表、链式存储的其他变体都会有“这我见过”的底气。如果有条件建议你分别用无头结点和带头结点各写一遍再对比一下两者的代码量和调试体验这种对比会让你对“哨兵节点到底解决了什么问题”有更直观的认识。