简介本资源面向学习数据结构与算法的高校学生及头歌平台实训者聚焦循环队列与链队列两类先进先出结构的代码实现与操作练习。内容按关卡组织第1关为循环队列基本操作第2关为链队列基本操作覆盖初始化、销毁、清空、判空、求长度、取队头、入队、出队与遍历等核心函数并配有可直接运行的C源码与main函数测试流程帮助读者理解头尾指针移动、假溢出处理及动态链表节点管理等关键细节。资源包共1个docx文件约15KB以文档形式整理代码与说明便于对照实训题目逐关调试与提交。目前已有10150人学习下载适合需要快速通过头歌关卡、巩固队列实现思路的初学者参考也可作为课程实验与期末复习的辅助材料。1. 头歌数据结构循环队列及链队列的基本操作从判空判满到出队入队的完整落地在头歌实践教学平台做数据结构实训循环队列和链队列这两关是很多人卡住的地方。题目通常给一个数组q[m]存放循环队列元素用rear和length分别指示队尾位置和当前元素个数要求实现入队、出队、判空、判满、取队头这一整套基本操作。看起来就是几个 if-else但真上手写指针绕一圈就乱判满条件写错、rear回绕没取模、链队列出队忘了释放节点都是高频翻车点。这篇笔记把循环队列和链队列的基本操作拆开讲清楚顺序存储的循环队列怎么用length绕开「队空队满都是 rearfront」的玄学链式存储的链队列怎么在 O(1) 时间完成入队出队以及头歌判题时那些不报错但结果不对的坑在哪。适合正在做头歌数据结构实训、准备考研数据结构、或者想把这套基本操作真正写对的人。2. 循环队列用 length 把队空队满彻底分开2.1 为什么循环队列需要 length 这个变量普通顺序队列有个致命问题出队后front往后移前面的空间就废了rear一路涨到数组末尾就溢出哪怕前面空着一大片。循环队列的思路是让rear和front走到数组末尾后回到下标 0把数组当成一个环来用空间利用率直接拉满。但环形一绕队空和队满的判断就撞车了。如果只用front和rear两个指针队空是front rear队满在「少用一个存储单元」的经典方案里也是front rear因为rear的下一个位置是front时就算满。两个状态长得一模一样判题时你根本分不清该返回空还是满。头歌这道题给的方案很干脆额外维护一个length记录当前元素个数。这样队空就是length 0队满就是length m两个条件彻底分开不用再玩「牺牲一个单元」的花活。代价是多存一个整型变量换来的是逻辑清晰、边界不容易错这笔账在实训和考试里都划算。用length之后rear的含义也变了它指向「下一个要插入的位置」而不是最后一个元素。入队时先写q[rear] x再rear (rear 1) % m最后length。出队时先取q[front]再front (front 1) % m最后length--。取模运算是整个循环队列的灵魂少了它rear就会越界。2.2 循环队列入队出队的完整代码实现下面这份实现按头歌常见的 C 语言风格写结构体里放数组、front、rear、length和容量m。核心操作全部围绕length和取模展开。#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; // 队头下标指向当前队头元素 int rear; // 队尾下标指向下一个可插入位置 int length; // 当前元素个数判空判满的关键 int m; // 队列容量 } CircularQueue; // 初始化front 和 rear 都归零length 清零 void InitQueue(CircularQueue *q, int m) { q-front 0; q-rear 0; q-length 0; q-m m; } // 判空length 为 0 即空 int QueueEmpty(CircularQueue *q) { return q-length 0; } // 判满length 等于容量即满 int QueueFull(CircularQueue *q) { return q-length q-m; } // 入队先写值再移动 rear最后 length 加一 int EnQueue(CircularQueue *q, int x) { if (QueueFull(q)) { return 0; // 队满入队失败 } q-data[q-rear] x; q-rear (q-rear 1) % q-m; // 取模实现环形回绕 q-length; return 1; } // 出队先取值再移动 front最后 length 减一 int DeQueue(CircularQueue *q, int *x) { if (QueueEmpty(q)) { return 0; // 队空出队失败 } *x q-data[q-front]; q-front (q-front 1) % q-m; // 同样取模回绕 q-length--; return 1; } // 取队头只读不删front 不动 int GetHead(CircularQueue *q, int *x) { if (QueueEmpty(q)) { return 0; } *x q-data[q-front]; return 1; }逻辑说明入队和出队的顺序不能乱。入队必须「先写数据、再移rear、最后加length」如果你先移rear再写数据写进去的位置就错了。出队必须「先取数据、再移front、最后减length」先移front会把队头元素直接丢掉。取模% q-m是保证rear和front在0到m-1之间循环的关键m是实际容量不是MAXSIZE。参数说明m由题目给定头歌里常见是 100 或具体测试用例的容量。length的取值范围是0到m等于m时判满等于0时判空。front和rear的初始值都是 0每次移动都取模所以永远不会越界。注意QueueFull用的是length m不是(rear 1) % m front这是用length方案和传统方案最大的区别。2.3 头歌判题时循环队列最容易错的三个边界第一个边界是初始状态。有些同学初始化时把rear设成m-1觉得这样第一个元素入队时rear1刚好到 0。但用length方案时rear指向的是「下一个插入位置」初始应该是 0第一个元素直接放在data[0]。设成m-1会导致第一次入队写到data[0]但rear从m-1绕回 0逻辑上没错但可读性差而且和length的配合容易让人绕晕。第二个边界是连续出队到空再入队。比如容量 5入队 5 个满出队 5 个空此时front和rear都回到了初始位置length为 0。再入队时rear从当前位置继续走取模保证正确。如果你在出队时忘了length--判空就会失效后续入队会覆盖还没出队的元素。第三个边界是取队头不改变队列状态。GetHead只读data[front]绝对不能动front或length。头歌有些测试用例会连续调用取队头再出队如果你在取队头时把front移了出队拿到的就是第二个元素结果全错。3. 链队列带头结点让入队出队都变成 O(1)3.1 链队列为什么必须带一个头结点链队列用单链表实现入队在队尾插出队在队头删。如果不带头结点队头指针front直接指向第一个数据节点出队时要把front移到下一个节点并释放原节点这没问题。但入队时如果队列为空front和rear都是NULL你需要特殊处理「第一个节点入队」的情况把front和rear都指向新节点。这个分支一多代码就容易漏。带头结点之后front永远指向头结点一个不存数据的哨兵rear指向最后一个数据节点。队空的条件变成front rear因为此时rear也指向头结点。入队时不管队列空不空都是「在rear后面接一个新节点然后rear移到新节点」不需要任何特殊分支。出队时如果队列不空删的是front-next删完如果front-next变成NULL说明队列空了要把rear拉回头结点。这套逻辑统一、干净是链队列的标准写法。头歌的链队列题目基本都要求带头结点因为判题时初始化后front和rear都指向同一个头结点队空判断就是front rear。如果你不带头结点初始化时front rear NULL判空也是front NULL但入队第一个元素的分支就得多写几行容易出错。3.2 链队列入队出队的代码与指针操作细节#include stdio.h #include stdlib.h typedef struct QNode { int data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; // 指向头结点 QueuePtr rear; // 指向最后一个数据节点 } LinkQueue; // 初始化创建头结点front 和 rear 都指向它 void InitQueue(LinkQueue *q) { q-front q-rear (QueuePtr)malloc(sizeof(QNode)); q-front-next NULL; } // 判空front 和 rear 指向同一节点头结点即空 int QueueEmpty(LinkQueue *q) { return q-front q-rear; } // 入队在 rear 后面接新节点rear 后移 int EnQueue(LinkQueue *q, int x) { QueuePtr p (QueuePtr)malloc(sizeof(QNode)); if (p NULL) return 0; p-data x; p-next NULL; q-rear-next p; // 原队尾节点的 next 指向新节点 q-rear p; // rear 移到新节点 return 1; } // 出队删 front-next注意队列变空时 rear 要回头结点 int DeQueue(LinkQueue *q, int *x) { if (QueueEmpty(q)) return 0; QueuePtr p q-front-next; // p 指向要删除的队头节点 *x p-data; q-front-next p-next; // 头结点跳过 p if (q-rear p) { // 如果删的是最后一个节点 q-rear q-front; // rear 拉回头结点恢复队空状态 } free(p); // 释放被删节点 return 1; } // 取队头读 front-next 的数据不删除 int GetHead(LinkQueue *q, int *x) { if (QueueEmpty(q)) return 0; *x q-front-next-data; return 1; }逻辑说明入队时q-rear-next p把新节点挂到队尾q-rear p更新队尾指针两步顺序不能反。出队时p q-front-next先记住要删的节点q-front-next p-next让头结点跳过它然后判断q-rear p——如果删的正好是最后一个数据节点rear就悬空了必须拉回front否则下次入队会往一个已释放的节点后面接直接段错误。最后free(p)释放内存这一步在头歌判题里不检查内存泄漏但养成习惯很重要。参数说明front始终指向头结点不存数据所以取队头是front-next-data。rear指向最后一个数据节点队空时和front指向同一个头结点。malloc失败返回NULL的判断在实训里可以省略但工程代码里建议保留。free(p)之后不要再访问p头歌有些测试用例会连续出队如果你在free后还用了p行为不可预测。3.3 链队列和循环队列的选型对比对比项循环队列链队列存储方式数组容量固定链表容量动态判空条件length 0front rear判满条件length m不存在满除非内存耗尽入队时间O(1)O(1)出队时间O(1)O(1)空间开销预分配 m 个单元每个节点多一个指针域适用场景容量可预估、追求缓存友好容量不确定、频繁增删循环队列的优势是内存连续、缓存命中率高适合容量固定的场景比如嵌入式里的串口缓冲区。链队列的优势是不需要预估容量入队永远不会「满」适合元素个数波动大的场景。头歌把这两个放在一起练就是想让你理解「同样的 FIFO 语义两种存储结构怎么各自实现」。4. 避坑排查头歌循环队列与链队列的 5 个高频翻车点4.1 现象循环队列入队后取队头拿到的是旧值原因入队时先移动了rear再写数据或者length加在了取模之前导致下标错位。更隐蔽的一种是rear初始值设成了m-1第一个元素写到了data[0]但front还是 0取队头时data[front]恰好是未初始化的旧值。解决严格按「写数据 → 移rear→ 加length」的顺序rear初始值设为 0。初始化后可以手动入队一个元素再取队头验证确认拿到的是刚入队的值。4.2 现象循环队列判满失效入队覆盖了未出队元素原因判满条件写成了(rear 1) % m front但代码用的是length方案rear和front的关系不满足传统方案的约束。或者length在出队时忘了减导致length虚高判满提前触发或永远不触发。解决用length方案就统一用length m判满、length 0判空不要混用指针关系判断。每次入队length、出队length--成对出现可以在出队后打印length确认。4.3 现象链队列出队到空后再入队程序崩溃或数据错乱原因出队删掉最后一个数据节点时rear还指向那个被free的节点。下次入队执行q-rear-next p时访问了已释放内存轻则数据错乱重则段错误。解决出队时判断if (q-rear p) q-rear q-front;把rear拉回头结点。这个判断是链队列出队的必备步骤漏了必崩。4.4 现象链队列取队头返回的是头结点的数据原因GetHead写成了*x q-front-data但front指向的是头结点里面的data是未初始化的垃圾值。正确应该取q-front-next-data。解决记住front是哨兵不存有效数据所有取数据的操作都从front-next开始。初始化时可以把头结点的data设成 0 或 -1方便调试时一眼看出是不是取错了节点。4.5 现象头歌判题提示「答案错误」但本地运行正常原因头歌的测试用例可能包含多次初始化、连续入队出队交替、容量为 1 的边界情况。容量为 1 时循环队列入队一个就满出队一个就空front和rear始终相等如果你的判空判满依赖指针关系而不是length就会误判。解决本地测试时补上容量为 1、连续入队出队交替、出队到空再入队这几组用例。循环队列重点验证length在 0 和m两个极值时的行为链队列重点验证出队到空后rear是否正确回头结点。5. 把基本操作串成一个可验证的测试流程学完单个操作真正要确认自己写对了得把入队、出队、判空、判满、取队头串起来跑一遍。我一般会写一个小的测试main按「空队取队头 → 入队到满 → 满队再入队 → 取队头 → 出队到空 → 空队再出队」的顺序走一遍每一步打印front、rear、length和返回值。这样哪个环节出问题一目了然比在头歌上反复提交猜错误强得多。int main() { CircularQueue q; InitQueue(q, 3); // 容量设为 3方便快速到满 int x; // 空队取队头应返回 0 printf(空队取队头: %d\n, GetHead(q, x)); // 入队 1、2、3 到满 EnQueue(q, 1); EnQueue(q, 2); EnQueue(q, 3); printf(满队状态: front%d rear%d length%d\n, q.front, q.rear, q.length); // 满队再入队应返回 0 printf(满队入队: %d\n, EnQueue(q, 4)); // 取队头应为 1 GetHead(q, x); printf(队头: %d\n, x); // 出队到空 while (DeQueue(q, x)) { printf(出队: %d\n, x); } printf(空队状态: front%d rear%d length%d\n, q.front, q.rear, q.length); // 空队再出队应返回 0 printf(空队出队: %d\n, DeQueue(q, x)); return 0; }这段测试代码的关键在于每一步都有明确的预期输出。容量设成 3 是为了快速触发判满front和rear的打印能让你看到取模回绕的实际效果——入队 3 个后rear应该回到 0和front相等但length是 3判满成立。出队到空后front和rear再次相等length归零判空成立。这两个「指针相等但状态相反」的时刻正是length方案的价值所在。链队列的测试类似但重点看出队到空后rear是否等于front以及再入队时新节点是否正确挂在头结点后面。我习惯在DeQueue里加一行临时打印rear和front的地址确认删最后一个节点时rear确实被拉回来了。这个习惯帮我省过好几次「本地跑通、头歌报错」的来回折腾。最后说个我自己的教训刚学循环队列时总觉得length是多余的想用(rear 1) % m front省掉这个变量结果在容量为 1 的用例上反复翻车折腾了一晚上才明白「少用一个单元」的方案在容量为 1 时根本没法用。后来老老实实加length所有边界一次过。基本操作这东西别想着取巧把每个变量的含义和每一步的顺序钉死比什么技巧都管用。希望帮到你。本文还有配套的精品资源点击获取