看到PTA上这道《循环链队只有尾指针的循环单链表的算法设计》题目估计不少同学第一反应是队列不是已经有了顺序循环队列那套标准写法了吗为什么还非要搞一个循环单链表更让人摸不着头脑的是书上明明讲链队要设置front和rear两个指针这道题却只给了一个尾指针这能玩得转先说结论能玩转而且只需要一个尾指针入队、出队、判空、遍历全都O(1)。这个设计不仅是PTA喜欢考的点也是理解“循环链表”和“队列语义”的绝佳素材。我打算把这篇文章写成一份完整的算法设计笔记从数据结构定义、初始化、入队、出队到销毁和遍历外加我在实际调试中踩过的坑和总结的排查经验力求让刷题的同学和自学的读者都能直接照着复现。如果你是正在刷PTA数据结构题、备战天梯赛L2阶段、或者刚学到栈和队列这一章觉得链队实现比较绕的人这篇文章就是写给你们的。1. 从“为什么只留一个尾指针”说起1.1 普通链队为什么需要两个指针常规教材上的链队会用带头结点的链表维护两个指针front指向头结点rear指向队尾节点。入队操作挂在rear后面出队操作从front-next取下节点。头指针负责出队尾指针负责入队各司其职。如果把这个方案里的头结点去掉直接不带头结点就面临一个问题出队时要修改链表头但front指针存在可以方便更新入队时要快速找到尾部rear起着定位作用。所以普通链队里两个指针缺一不可这是很自然的。可这道题偏偏反着来用循环单链表只保留尾指针。它充分利用了单链表中“尾节点的next指向头节点”这个循环特性让一个指针同时承担两个角色——rear-next就是队头。这样一来队头不需要额外指针就能O(1)拿到队尾本身由rear直接指向入队出队都不需要遍历链表。1.2 尾指针循环链队的核心思维你可以把这种结构想象成一群人围成一个圈做击鼓传花的游戏每个人只记住下一个人的位置。rear指向最后一个传花的人也就是队尾rear-next指向第一个接花的人也就是队头。新成员加入时插在队尾后面然后rear往后移动一位有人离开时直接离开队伍最前面的那个人其余人自动补齐。这个设计的精妙之处在于循环链表天然消除了“尾节点next为空”的说法rear既标识了队尾也承包了定位队头的功能。你只需要维护好rear这一个变量整条队列的状态就完全可控。1.3 不带头结点的空队状态设计题目只给尾指针那么空队状态怎么表示直接让rear NULL。只要rear为空任何对队头、队尾的访问都没有意义入队时也要从这个状态开始重新构建环。有少部分教材会把空队表示为“存在一个头结点且rear指向头结点”但这道题刻意不带头结点所以判断条件必须依赖NULL。看懂这一点后面所有边界条件处理就顺了。2. 数据结构定义与基础操作设计2.1 结构体怎么定义链队节点本身就是一个单链表节点存储数据和一个next指针。队列这个“容器”可以用两种方式定义。一种是把rear直接定义为节点指针函数参数用二级指针或者一级指针的地址传递。代码如下typedef struct QNode { int data; struct QNode *next; } QNode; typedef QNode* LinkQueue;另一种我更喜欢用一个小的结构体包住rear语义更清晰以后想加队列长度计数也方便typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *rear; } LinkQueue;两种都能跑通PTA关键在于函数签名要和题目给的接口保持一致。如果是函数题题目说void InitQueue(LinkQueue *q)那就严格按题面来不要自己改签名。2.2 初始化和判空实现初始化就一句话让rear指向NULLvoid InitQueue(LinkQueue *Q) { Q-rear NULL; }判空也一样直白int IsEmpty(LinkQueue Q) { return Q.rear NULL; }注意这里的参数是结构体本身还是指针取决于上面选择了哪种定义方式。如果是typedef QNode* LinkQueue则队列变量本身就是指针判空写法就变成void QueueEmpty(LinkQueue Q)判断Q NULL。我看到有些同学会在初始化时先malloc一个节点、让节点自成环然后rear指向它这属于带头结点的循环链队空队判定会变成Q-rear-next Q-rear。不能说错但与题面“只有尾指针的循环单链表”最干净的状态定义并不一致而且边界判断更多自找麻烦。2.3 入队时的两种状态入队操作要充分理解两个状态空队状态rear NULL此时新节点要自己形成循环链表即新节点-next 新节点然后让rear指向它。非空状态新节点插入到rear和rear-next之间本质是“在尾节点后面插入”然后让rear后移。代码实现int EnQueue(LinkQueue *Q, int e) { QNode *s (QNode*)malloc(sizeof(QNode)); if (s NULL) { return 0; } s-data e; s-next NULL; if (Q-rear NULL) { s-next s; Q-rear s; } else { s-next Q-rear-next; Q-rear-next s; Q-rear s; } return 1; }入队时最常犯的错误是忘了处理空队情况直接把新节点往Q-rear-next后面挂。空队时Q-rear是NULL访问Q-rear-next直接段错误PTA给出的错误信息往往是Segmentation fault查半天才发现是最普通的一个空指针问题。另外很多参考书里写的是“先断链、再接新节点”顺序错了会导致中间有一瞬间链表处于断裂状态。实际上这里只要记住新节点先指向rear-nextrear-next再指向新节点两步完成插入顺序不能反。3. 出队、遍历与销毁的边界细节3.1 出队时单节点问题出队操作是这道题最容易写错的地方。因为要删除的节点是rear-next即队头。但删除后要分两种情况队列中原本只有一个节点还是至少有两个节点。单个节点时rear-next rear它自己指向自己。此时删除它队列就会变成真正的空队rear必须被设置为NULL。如果此时还按“有多个节点”的逻辑去更新rear-next就会出现悬垂指针后面再判空、入队时全乱套。多个节点时删除队头后rear不变但rear-next要指向被删节点的下一个节点。int DeQueue(LinkQueue *Q, int *e) { if (Q-rear NULL) { return 0; } QNode *p Q-rear-next; *e p-data; if (Q-rear-next Q-rear) { Q-rear NULL; } else { Q-rear-next p-next; } free(p); return 1; }重点提醒free(p)一定要放在更新指针关系之后不要先释放再更新因为释放之后p的地址还留着但内容已无意义再去访问p-next属于用了野指针。实际操作时我会先画图再写代码尤其是“删除前先把队头的后继节点被谁接管这件事想清楚”。3.2 遍历打印的循环终止条件打印队列时不能用普通的while (p ! NULL)因为循环链表里根本没有NULL节点遍历要回到起点才结束。一种容易理解的做法是把队尾单独打印队头到倒数第二个节点用循环处理void PrintQueue(LinkQueue Q) { if (Q.rear NULL) { printf(empty\n); return; } QNode *p Q.rear-next; while (p ! Q.rear) { printf(%d , p-data); p p-next; } printf(%d\n, Q.rear-data); }另一种是用do...while先打印再移动终止条件设为回到队头。这个写法的优势是逻辑对称但需要注意空队必须提前拦截否则do...while至少执行一次会访问空指针。如果PTA要求“元素之间用一个空格隔开且行末不留空格”上面第一种写法天然满足前面循环每次打印都带空格队尾单独打印正好没有尾随空格。这个细节看似琐碎但在判题平台里很容易因为输出格式错误而罚分。3.3 销毁队列别让内存泄漏PTA有些测试用例会跑多次操作如果只入队不出队并且程序结束时没有释放内存虽然平台不一定会特意检查内存泄漏但在自己本机调试时用valgrind扫一遍就能看到一堆泄漏。养成好习惯总没错。销毁队列本质上就是连续出队直到rear变为NULLvoid DestroyQueue(LinkQueue *Q) { while (Q-rear ! NULL) { QNode *p Q-rear-next; if (p Q-rear) { Q-rear NULL; } else { Q-rear-next p-next; } free(p); } }由于每次删的都是队头这个循环会在O(n)时间内完成且每次删除都会判断单节点情况思路与出队完全一致。写一遍等于把出队操作又复习了一遍。3.4 完整模块代码参考把上面这些函数汇总成一个可直接运行的C文件大概长这样#include stdio.h #include stdlib.h typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *rear; } LinkQueue; void InitQueue(LinkQueue *Q) { Q-rear NULL; } int EnQueue(LinkQueue *Q, int e) { QNode *s (QNode*)malloc(sizeof(QNode)); if (s NULL) return 0; s-data e; s-next NULL; if (Q-rear NULL) { s-next s; Q-rear s; } else { s-next Q-rear-next; Q-rear-next s; Q-rear s; } return 1; } int DeQueue(LinkQueue *Q, int *e) { if (Q-rear NULL) return 0; QNode *p Q-rear-next; *e p-data; if (p Q-rear) { Q-rear NULL; } else { Q-rear-next p-next; } free(p); return 1; } void PrintQueue(LinkQueue Q) { if (Q.rear NULL) { printf(empty\n); return; } QNode *p Q.rear-next; while (p ! Q.rear) { printf(%d , p-data); p p-next; } printf(%d\n, Q.rear-data); } void DestroyQueue(LinkQueue *Q) { while (Q-rear ! NULL) { QNode *p Q-rear-next; if (p Q-rear) { Q-rear NULL; } else { Q-rear-next p-next; } free(p); } } int main() { LinkQueue q; InitQueue(q); EnQueue(q, 10); EnQueue(q, 20); EnQueue(q, 30); PrintQueue(q); int v; DeQueue(q, v); printf(dequeue: %d\n, v); PrintQueue(q); DestroyQueue(q); return 0; }在主函数里跑一遍输出应该是10 20 30 dequeue: 10 20 30整个流程会非常直观。4. 与其他队列实现方案的对比4.1 顺序循环队列 vs 循环链队很多同学学队列时最先学的是顺序循环队列它是用数组加front、rear两个下标实现的靠取模运算让数组下标在末尾时绕回去。这个方案的问题是容量固定扩容时要整体搬迁数据而且为了让“队满”和“队空”区分开还得牺牲一个存储单元通常让rear 1 % maxsize front表示队满。循环链队则完全解决了这两个问题按需申请节点不用预留容量只要内存还能分得出空间队列就不会满。同时入队出队都是纯指针操作不需要计算%取模时间常数也更小。代价是每个节点多存一个next指针空间开销比数组大一点单个节点访问的缓存局部性也差些。但作为教学题目它的重点就是链式结构的动态性。对比项顺序循环队列仅尾指针循环链队容量固定需预先设定动态按需分配队满判断需要取模运算与判满条件理论上不存在队满入队操作移动下标取模改指针出队操作移动下标取模改指针内存连续性连续分散4.2 带头结点链队 vs 不带头结点链队链表实现队列时还有一个常见选择是否带头结点。带头结点的话空队状态是front rear且都指向头结点入队出队时头结点永远不删代码里永远有一个“哨兵”顶着边界情况稍少。不带头结点时空队状态就是NULL删除最后一个节点要额外置空rear代码分支多了一道。这道题选择不带头结点其实是在逼你理解循环链表的特殊性正是因为循环出队时即使删的是队头rear-next依然能找到新的队头也正是因为循环空队和非空队的状态切换更干净。如果带头结点循环链队的“环”始终存在反而体现不出NULL状态的处理价值。4.3 双指针链队 vs 单尾指针链队普通链队需要front和rear两个指针是因为如果不循环front唯一记录了队头的位置。而循环单链表通过“尾节点的next指向头节点”这一结构让尾指针直接携带了头节点的信息队头就是rear-next。空间上少一个指针变量时间上完全不损失这正是题目设计的巧妙所在。我们平时写工程代码时如果明确需要频繁取队头和队尾也可以参考这个思路去优化存储结构。不过需要注意如果链表从尾部断开或发生损坏“只有尾指针”的循环结构就会失去队头定位能力属于典型的时间换空间、结构耦合度更高的设计。刷题阶段理解就好真正写业务系统时还是要综合考虑容错。5. 常见问题与调试实录5.1 段错误十有八九是空队问题我见过最多的情况是入队时没判rear NULL一上来就访问Q-rear-next。空队时Q-rear是NULL这一步直接就崩。还有一种情况是出队时只判断了队列是否为空但忽略“删除后只剩空队”的置NULL逻辑。删掉最后一个节点后rear还指着一块已经free掉的内存下一次判空时Q-rear ! NULL成立程序误以为队列还有数据接着访问已经释放的节点段错误当场复发。排查段错误时我的习惯是三步走第一步在可疑函数入口打印队列状态确认rear是否为NULL第二步打印关键节点的地址比如rear、rear-next、要删除节点的地址看谁出了问题第三步配合gdb查看调用栈能直接看到崩溃发生在哪一行。多数情况下崩溃点就在那几个边界分支之间。5.2 死循环遍历和销毁都容易中招打印队列时如果把终止条件写成while (p ! NULL)在循环链表里就是一个永不停止的循环因为最后一个节点的next指回队头永远不会为NULL。这个错误很难一眼看出来因为程序能跑结果却疯狂输出。销毁队列时如果忘了在删除节点后更新rear-next链表会在某个位置形成“回环断裂又接续”的状态表现为while循环时指针来回跳或者直接死循环。我的建议是销毁和出队共用同一套边界逻辑不要单独再写一套简化版代码越少出问题的地方越少。如果用do...while打印记得先判空。do...while至少会执行一次循环体这条规则决定了它天然不适合对空链表直接使用。5.3 PTA判题与接口适配的几个细节PTA题库里这类题有时候以函数题形式出现题目会先给出预定义好的结构体和函数声明要求你填空实现具体函数。这时候最忌讳的就是自己另起炉灶重新定义结构体导致和题目的头文件重名冲突。拿到题面先做三件事看清结构体类型名看清函数名看清参数类型。比如题目若定义typedef struct QNode *PtrToQNode那写函数时就要用这个类型名不要自作主张换名字。很多同学算法思路完全正确却因为函数签名不匹配拿不到分非常可惜。另外PTA的编译环境常常是C和C混合提交。纯C代码里如果用bool类型要包含stdbool.h用C提交则没有这个问题。如果不想纠结返回int用0/1表示成功失败可移植性最好。5.4 调试这类链表问题的独家技巧这里分享一个非常笨但异常有效的办法每次入队、出队之后打印一遍rear的地址、rear-next-data和rear-data。循环链队的核心约束就两条rear必须总是指向当前队尾rear-next必须总是指向当前队头。如果打印结果里这两条约束被破坏那么出问题的操作就是刚刚执行的那个函数。这样逐操作验证边界条件很快就能定位。我在刷这道题时就是用这个方法十几分钟就找齐了所有边界bug。6. 从“循环链队”延伸出去的思考6.1 循环链表在经典算法题中的应用循环单链表并不是PTA专属考点约瑟夫环问题就是它的经典应用。一轮一轮地数人、出队本质上恰好吻合循环链表的特性——到了末尾自动回到开头。如果你能熟练写出只有尾指针的循环链队约瑟夫环的实现就只剩下“数到第几个人就删除哪个节点”这一步逻辑。天梯赛的不少L2题目也喜欢考链式结构比如链表逆转、链表去重这类问题。它们的共性在于链表题要画图分析指针变化别空想。把每个节点标上地址每一步操作后把指向关系重新画一遍基本上不会错。6.2 真实系统里队列长什么样数据结构课上学到的队列在实际工程里演化出了很多形态。Kafka、RabbitMQ这些消息队列中间件虽然和“数组队列”不是一回事但底层都遵循FIFO的消费语义操作系统里的阻塞队列、线程池的任务队列则会在队列基础上增加并发控制和阻塞唤醒机制。很多热词讨论的“消息队列重复消费问题”“阻塞队列怎么选”追根溯源还是要先理解队列的模型和边界行为。我觉得刷数据结构题最大的意义就在这儿先把抽象的队列模型和边界条件吃透后面去看任何框架的消息机制都会轻松很多。循环链队虽小但它浓缩了“链表维护循环结构边界处理”三个核心能力值得好好写一遍、调一遍、总结一遍。根据我教过不少同学的实际体会这道题最容易出bug的地方就是“单节点删除后没把rear置NULL”而最容易困惑的地方是“为什么遍历时不能用NULL作为终止条件”。这两个坑踩完之后循环链队这章才算真正过关。建议你写代码时用手在草稿纸上模拟三遍空队入队、单节点出队、多节点连续出队到空。三遍走完基本上闭着眼睛都能把接口写对。