尧图网站建设 
简介本资源面向学习数据结构与算法的高校学生及头歌平台刷题者聚焦循环队列与链队列的基本操作实现帮助读者掌握“先进先出”结构的核心原理与代码落地。压缩包内共1个docx文件约15KB内容以C源码与文字讲解为主涵盖循环队列的初始化、销毁、清空、判空、求长度、取队头、入队、出队、遍历共9个基本操作以及链队列的对应实现并配有main函数测试用例与运行结果说明。资源按“第1关循环队列的基本操作”“第2关链队列的基本操作”两关组织代码中标注了Begin/End填空区域便于对照补全与调试。目前已有10150人学习下载适合需要快速通过头歌实训、理解队列假溢出与动态链式存储差异的读者参考也可作为课程实验与期末复习的实操素材。1. 循环队列与链队列从头歌两个关卡拆开看队列的底层实现头歌数据结构实训里循环队列和链队列这两关是很多人第一次真正动手写队列的地方。题目给的框架很完整InitQueue、EnQueue、DeQueue这些函数签名都摆好了中间留一段Begin到End的空档让你填。看着简单但真上手写的时候循环队列的取模边界、链队列的尾指针回退都是容易翻车的地方。这份资源就是两关的完整参考实现C 写的循环队列用动态数组加front/rear双指针链队列用带头结点的单链表。适合正在刷头歌数据结构实训、或者想拿 C 把队列九种基本操作一次性跑通的人。下面我按自己的理解把两关拆开讲代码可以直接对照着填。2. 循环队列九个操作里最容易写错的三个边界2.1 为什么用取模而不是简单加一循环队列的核心思路是让front和rear在数组里绕圈走。普通队列出队后front往后移前面的空间就浪费了数组再大也扛不住反复入队出队。循环队列把base当成一个环rear (rear 1) % MAX_QSIZE走到末尾就回到下标 0空间利用率直接拉满。这里有个约定要先说清楚front指向队头元素rear指向队尾元素的下一个位置。所以队列为空的条件是front rear而队列满的条件是(rear 1) % MAX_QSIZE front。注意满的判断里rear和front之间始终隔一个空位这是为了和空队列区分开。代价是数组里永远有一个位置用不上MAX_QSIZE定义为 5实际最多存 4 个元素。这个设计不是 bug是循环队列的经典取舍。初始化的时候malloc分配MAX_QSIZE * sizeof(QElemType)的空间然后把front和rear都置 0。销毁时free(Q.base)之后要把Q.base置NULL不然就是悬空指针。清空队列只重置front和rear不释放内存因为队列结构还要继续用。2.2 入队、出队、求长度三行代码里的取模逻辑先看入队的实现int EnQueue(SqQueue Q, QElemType e) { // 队列满的判断rear 再走一步就撞上 front if ((Q.rear 1) % MAX_QSIZE Q.front) return ERROR; Q.base[Q.rear] e; // 元素放在 rear 当前位置 Q.rear (Q.rear 1) % MAX_QSIZE; // rear 环形后移 return OK; }入队前先判满满了直接返回ERROR不覆盖已有元素。写入位置是Q.base[Q.rear]写完之后rear才后移。顺序不能反反了就会把新元素写到错误的位置。出队的逻辑对称int DeQueue(SqQueue Q, QElemType e) { if (Q.front Q.rear) // 空队列 return ERROR; e Q.base[Q.front]; // 取出队头元素 Q.front (Q.front 1) % MAX_QSIZE; // front 环形后移 return OK; }先判空空队列出队没有意义。取出Q.base[Q.front]赋给e然后front后移。注意e是引用传递调用方的变量会被直接修改。求队列长度用的是(Q.rear - Q.front MAX_QSIZE) % MAX_QSIZE。加MAX_QSIZE是为了防止rear小于front时出现负数。比如front 3、rear 1、MAX_QSIZE 5直接减是 -2加 5 再取模得到 3正好是队列里实际的元素个数。这个公式在循环队列里是固定写法记住就行。2.3 遍历和取队头循环终止条件别写错遍历队列不能简单用for (i front; i rear; i)因为rear可能比front小。正确做法是从front开始每次i (i 1) % MAX_QSIZE直到i rear停止void QueueTraverse(SqQueue Q, void(*vi)(QElemType)) { int i Q.front; while (i ! Q.rear) { vi(Q.base[i]); // 对每个元素调用 vi i (i 1) % MAX_QSIZE; // 环形前进 } printf(\n); }vi是函数指针main里传的是print每个元素打印后跟一个空格。遍历结束后统一换行。这个模式在头歌的评测里很常见输出格式对不上就是零分所以printf(\n)的位置要放在循环外面。取队头元素GetHead相对简单判空之后直接e Q.base[Q.front]就行不需要移动指针。它和DeQueue的区别是只读不删front不动。提示头歌评测对输出格式敏感QueueTraverse里每个元素后面的空格和最后的换行都要和题目要求一致建议先在本地跑一遍看输出。3. 链队列带头结点单链表的尾指针维护3.1 头结点存在的意义与初始化链队列用带头结点的单链表实现。头结点不存数据Q.front指向它Q.rear指向最后一个数据结点。空队列时Q.front Q.rear都指向头结点头结点的next为NULL。初始化就是创建一个头结点void InitQueue(LinkQueue Q) { if (!(Q.front Q.rear (QueuePtr)malloc(sizeof(QNode)))) exit(OVERFLOW); Q.front-next NULL; }Q.front和Q.rear同时指向新分配的结点然后把这个结点的next置空。头结点的存在让入队和出队的代码统一了不需要单独处理空队列插入第一个元素的情况。如果没有头结点入队时要判断队列是否为空出队时也要判断是不是最后一个元素代码会多出好几个分支。销毁队列要遍历整个链表逐个freevoid DestroyQueue(LinkQueue Q) { while (Q.front) { Q.rear Q.front-next; // 先保存下一个结点 free(Q.front); // 释放当前结点 Q.front Q.rear; // 移动到下一个 } }这里用Q.rear当临时指针保存next因为Q.front释放后就不能再访问它的next了。循环条件是Q.front非空当头结点也被释放后循环结束。3.2 入队与出队尾指针什么时候需要回退入队操作在rear后面接一个新结点int EnQueue(LinkQueue Q, QElemType e) { QueuePtr p; if (!(p (QueuePtr)malloc(sizeof(QNode)))) exit(OVERFLOW); p-data e; p-next NULL; Q.rear-next p; // 原尾结点的 next 指向新结点 Q.rear p; // rear 更新为新结点 return OK; }新结点的next必须置NULL因为它是新的尾结点。然后Q.rear-next p把新结点挂到链表末尾最后Q.rear p更新尾指针。链队列不需要判满内存够就能一直入队。出队稍微复杂一点因为要考虑删除的是不是最后一个结点int DeQueue(LinkQueue Q, QElemType e) { QueuePtr p; if (Q.front Q.rear) // 空队列 return ERROR; p Q.front-next; // p 指向队头数据结点 e p-data; Q.front-next p-next; // 头结点跳过 p if (Q.rear p) // 如果删除的是最后一个结点 Q.rear Q.front; // rear 回退到头结点 free(p); return OK; }关键在if (Q.rear p)这个判断。如果队列里只有一个数据结点删除之后队列变空rear必须回退到Q.front否则rear就指向了一块已经释放的内存下次入队时Q.rear-next就是非法访问。这是链队列最容易翻车的地方很多人第一次写会漏掉这个判断。3.3 求长度与清空遍历方式与循环队列的差异链队列求长度需要从头遍历到尾int QueueLength(LinkQueue Q) { int i 0; QueuePtr p Q.front; while (Q.rear ! p) { // 从头结点走到尾结点 i; p p-next; } return i; }循环条件是Q.rear ! p因为p从Q.front出发走到Q.rear时正好经过所有数据结点。注意这里p初始指向头结点头结点不计入长度所以第一次循环i加的是第一个数据结点。清空队列保留头结点释放所有数据结点void ClearQueue(LinkQueue Q) { QueuePtr p, q; Q.rear Q.front; // rear 先回到头结点 p Q.front-next; // p 指向第一个数据结点 Q.front-next NULL; // 头结点断开 while (p) { q p; p p-next; free(q); } }先把Q.rear拉回头结点再把头结点的next置空然后逐个释放数据结点。顺序很重要如果先释放再改rearrear就可能变成悬空指针。注意链队列的QueueEmpty判断的是Q.front-next NULL不是Q.front Q.rear。虽然空队列时两者都成立但用front-next更直观也避免了rear维护出错时判断失效。4. 避坑排查头歌评测里最常见的五类翻车4.1 循环队列满判断写成rear front现象入队时明明还有空位却返回ERROR或者队列满了还能继续插入覆盖数据。原因循环队列区分空和满靠的是rear和front之间隔一个空位。空的条件是front rear满的条件是(rear 1) % MAX_QSIZE front。如果满也写成front rear那队列永远无法判断满rear会追上front并覆盖数据。解决满判断必须用(Q.rear 1) % MAX_QSIZE Q.front同时记住MAX_QSIZE是最大长度加一实际容量是MAX_QSIZE - 1。4.2 链队列出队后尾指针没回退现象队列里只有一个元素出队后再入队程序崩溃或者新元素接不上。原因删除最后一个结点后Q.rear还指向被free的结点下次EnQueue执行Q.rear-next p时访问了已释放内存。解决出队时加if (Q.rear p) Q.rear Q.front;确保队列变空时rear回到头结点。4.3 循环队列求长度出现负数现象QueueLength返回负值导致后续逻辑判断出错。原因rear绕回数组前面后比front小直接相减得到负数。解决用(Q.rear - Q.front MAX_QSIZE) % MAX_QSIZE加MAX_QSIZE保证结果非负。4.4 遍历时用i rear导致漏元素现象循环队列遍历时只打印了一部分元素rear绕回前面后后面的元素没输出。原因rear可能小于fronti rear的循环条件不成立。解决用while (i ! Q.rear)配合i (i 1) % MAX_QSIZE保证从front走到rear经过所有有效元素。4.5 销毁队列后没有置空指针现象DestroyQueue之后再调用其他操作程序行为异常。原因free之后Q.base或Q.front还保留着原地址成了悬空指针。解决循环队列销毁后Q.base NULL; Q.front Q.rear 0;链队列销毁后Q.front Q.rear NULL;。头歌评测虽然不一定检查这个但养成习惯能避免很多玄学问题。5. 本地验证与调试把两关代码跑通再提交头歌的评测环境是黑匣子提交前最好在本地把两关代码完整跑一遍。我一般用 g 编译把main函数里的输入按题目要求模拟一遍。循环队列的测试输入是 5 个整数但实际只能存 4 个第 5 个入队会失败。题目里for (i 0; i MAX_QSIZE; i)循环 5 次第 5 次EnQueue返回ERROR但main没有检查返回值所以第 5 个元素被丢弃了。这是题目设计如此不是代码问题。跑的时候输入1 2 3 4 5输出应该是队列长度为: 4 现在队列中元素: 1 2 3 4 删除的元素是1 删除的元素是2然后输入一个新元素比如6再入队此时队列长度还是 4元素变成3 4 6。最后GetHead返回3。链队列的测试输入是 5 个整数全部能入队。输入1 2 3 4 5输出队列长度为: 5 现在队列中元素: 1 2 3 4 5 删除的元素是1 删除的元素是2再输入6入队队列长度变成 4元素是3 4 5 6队头是3。本地编译命令g -o circle_queue circle_queue.cpp g -o link_queue link_queue.cpp如果编译报错exit未声明加#include stdlib.h。头歌的代码框架里已经包含了本地跑的时候注意别漏。调试的时候可以在EnQueue和DeQueue里加临时printf打印front、rear和返回值确认每一步的状态符合预期。特别是循环队列的取模运算手动算一遍front和rear的变化比盯着代码看有效得多。提示头歌每关的评测用例不止一组除了题目里展示的输入可能还有空队列出队、满队列入队等边界测试。本地验证时把这些情况都覆盖到提交前心里才有底。从那以后我每次写循环队列都会先在纸上画一圈下标把front和rear的初始位置、入队出队后的移动方向标清楚再动手写代码。链队列则是在出队函数里先写if (Q.rear p) Q.rear Q.front;这一行再补其他逻辑。这两个习惯帮我省了很多次提交失败后的重新调试。希望帮到你。本文还有配套的精品资源点击获取 头歌数据结构实训：循环队列与链队列C++实现及避坑指南
简介本资源面向学习数据结构与算法的高校学生及头歌平台刷题者聚焦循环队列与链队列的基本操作实现帮助读者掌握“先进先出”结构的核心原理与代码落地。压缩包内共1个docx文件约15KB内容以C源码与文字讲解为主涵盖循环队列的初始化、销毁、清空、判空、求长度、取队头、入队、出队、遍历共9个基本操作以及链队列的对应实现并配有main函数测试用例与运行结果说明。资源按“第1关循环队列的基本操作”“第2关链队列的基本操作”两关组织代码中标注了Begin/End填空区域便于对照补全与调试。目前已有10150人学习下载适合需要快速通过头歌实训、理解队列假溢出与动态链式存储差异的读者参考也可作为课程实验与期末复习的实操素材。1. 循环队列与链队列从头歌两个关卡拆开看队列的底层实现头歌数据结构实训里循环队列和链队列这两关是很多人第一次真正动手写队列的地方。题目给的框架很完整InitQueue、EnQueue、DeQueue这些函数签名都摆好了中间留一段Begin到End的空档让你填。看着简单但真上手写的时候循环队列的取模边界、链队列的尾指针回退都是容易翻车的地方。这份资源就是两关的完整参考实现C 写的循环队列用动态数组加front/rear双指针链队列用带头结点的单链表。适合正在刷头歌数据结构实训、或者想拿 C 把队列九种基本操作一次性跑通的人。下面我按自己的理解把两关拆开讲代码可以直接对照着填。2. 循环队列九个操作里最容易写错的三个边界2.1 为什么用取模而不是简单加一循环队列的核心思路是让front和rear在数组里绕圈走。普通队列出队后front往后移前面的空间就浪费了数组再大也扛不住反复入队出队。循环队列把base当成一个环rear (rear 1) % MAX_QSIZE走到末尾就回到下标 0空间利用率直接拉满。这里有个约定要先说清楚front指向队头元素rear指向队尾元素的下一个位置。所以队列为空的条件是front rear而队列满的条件是(rear 1) % MAX_QSIZE front。注意满的判断里rear和front之间始终隔一个空位这是为了和空队列区分开。代价是数组里永远有一个位置用不上MAX_QSIZE定义为 5实际最多存 4 个元素。这个设计不是 bug是循环队列的经典取舍。初始化的时候malloc分配MAX_QSIZE * sizeof(QElemType)的空间然后把front和rear都置 0。销毁时free(Q.base)之后要把Q.base置NULL不然就是悬空指针。清空队列只重置front和rear不释放内存因为队列结构还要继续用。2.2 入队、出队、求长度三行代码里的取模逻辑先看入队的实现int EnQueue(SqQueue Q, QElemType e) { // 队列满的判断rear 再走一步就撞上 front if ((Q.rear 1) % MAX_QSIZE Q.front) return ERROR; Q.base[Q.rear] e; // 元素放在 rear 当前位置 Q.rear (Q.rear 1) % MAX_QSIZE; // rear 环形后移 return OK; }入队前先判满满了直接返回ERROR不覆盖已有元素。写入位置是Q.base[Q.rear]写完之后rear才后移。顺序不能反反了就会把新元素写到错误的位置。出队的逻辑对称int DeQueue(SqQueue Q, QElemType e) { if (Q.front Q.rear) // 空队列 return ERROR; e Q.base[Q.front]; // 取出队头元素 Q.front (Q.front 1) % MAX_QSIZE; // front 环形后移 return OK; }先判空空队列出队没有意义。取出Q.base[Q.front]赋给e然后front后移。注意e是引用传递调用方的变量会被直接修改。求队列长度用的是(Q.rear - Q.front MAX_QSIZE) % MAX_QSIZE。加MAX_QSIZE是为了防止rear小于front时出现负数。比如front 3、rear 1、MAX_QSIZE 5直接减是 -2加 5 再取模得到 3正好是队列里实际的元素个数。这个公式在循环队列里是固定写法记住就行。2.3 遍历和取队头循环终止条件别写错遍历队列不能简单用for (i front; i rear; i)因为rear可能比front小。正确做法是从front开始每次i (i 1) % MAX_QSIZE直到i rear停止void QueueTraverse(SqQueue Q, void(*vi)(QElemType)) { int i Q.front; while (i ! Q.rear) { vi(Q.base[i]); // 对每个元素调用 vi i (i 1) % MAX_QSIZE; // 环形前进 } printf(\n); }vi是函数指针main里传的是print每个元素打印后跟一个空格。遍历结束后统一换行。这个模式在头歌的评测里很常见输出格式对不上就是零分所以printf(\n)的位置要放在循环外面。取队头元素GetHead相对简单判空之后直接e Q.base[Q.front]就行不需要移动指针。它和DeQueue的区别是只读不删front不动。提示头歌评测对输出格式敏感QueueTraverse里每个元素后面的空格和最后的换行都要和题目要求一致建议先在本地跑一遍看输出。3. 链队列带头结点单链表的尾指针维护3.1 头结点存在的意义与初始化链队列用带头结点的单链表实现。头结点不存数据Q.front指向它Q.rear指向最后一个数据结点。空队列时Q.front Q.rear都指向头结点头结点的next为NULL。初始化就是创建一个头结点void InitQueue(LinkQueue Q) { if (!(Q.front Q.rear (QueuePtr)malloc(sizeof(QNode)))) exit(OVERFLOW); Q.front-next NULL; }Q.front和Q.rear同时指向新分配的结点然后把这个结点的next置空。头结点的存在让入队和出队的代码统一了不需要单独处理空队列插入第一个元素的情况。如果没有头结点入队时要判断队列是否为空出队时也要判断是不是最后一个元素代码会多出好几个分支。销毁队列要遍历整个链表逐个freevoid DestroyQueue(LinkQueue Q) { while (Q.front) { Q.rear Q.front-next; // 先保存下一个结点 free(Q.front); // 释放当前结点 Q.front Q.rear; // 移动到下一个 } }这里用Q.rear当临时指针保存next因为Q.front释放后就不能再访问它的next了。循环条件是Q.front非空当头结点也被释放后循环结束。3.2 入队与出队尾指针什么时候需要回退入队操作在rear后面接一个新结点int EnQueue(LinkQueue Q, QElemType e) { QueuePtr p; if (!(p (QueuePtr)malloc(sizeof(QNode)))) exit(OVERFLOW); p-data e; p-next NULL; Q.rear-next p; // 原尾结点的 next 指向新结点 Q.rear p; // rear 更新为新结点 return OK; }新结点的next必须置NULL因为它是新的尾结点。然后Q.rear-next p把新结点挂到链表末尾最后Q.rear p更新尾指针。链队列不需要判满内存够就能一直入队。出队稍微复杂一点因为要考虑删除的是不是最后一个结点int DeQueue(LinkQueue Q, QElemType e) { QueuePtr p; if (Q.front Q.rear) // 空队列 return ERROR; p Q.front-next; // p 指向队头数据结点 e p-data; Q.front-next p-next; // 头结点跳过 p if (Q.rear p) // 如果删除的是最后一个结点 Q.rear Q.front; // rear 回退到头结点 free(p); return OK; }关键在if (Q.rear p)这个判断。如果队列里只有一个数据结点删除之后队列变空rear必须回退到Q.front否则rear就指向了一块已经释放的内存下次入队时Q.rear-next就是非法访问。这是链队列最容易翻车的地方很多人第一次写会漏掉这个判断。3.3 求长度与清空遍历方式与循环队列的差异链队列求长度需要从头遍历到尾int QueueLength(LinkQueue Q) { int i 0; QueuePtr p Q.front; while (Q.rear ! p) { // 从头结点走到尾结点 i; p p-next; } return i; }循环条件是Q.rear ! p因为p从Q.front出发走到Q.rear时正好经过所有数据结点。注意这里p初始指向头结点头结点不计入长度所以第一次循环i加的是第一个数据结点。清空队列保留头结点释放所有数据结点void ClearQueue(LinkQueue Q) { QueuePtr p, q; Q.rear Q.front; // rear 先回到头结点 p Q.front-next; // p 指向第一个数据结点 Q.front-next NULL; // 头结点断开 while (p) { q p; p p-next; free(q); } }先把Q.rear拉回头结点再把头结点的next置空然后逐个释放数据结点。顺序很重要如果先释放再改rearrear就可能变成悬空指针。注意链队列的QueueEmpty判断的是Q.front-next NULL不是Q.front Q.rear。虽然空队列时两者都成立但用front-next更直观也避免了rear维护出错时判断失效。4. 避坑排查头歌评测里最常见的五类翻车4.1 循环队列满判断写成rear front现象入队时明明还有空位却返回ERROR或者队列满了还能继续插入覆盖数据。原因循环队列区分空和满靠的是rear和front之间隔一个空位。空的条件是front rear满的条件是(rear 1) % MAX_QSIZE front。如果满也写成front rear那队列永远无法判断满rear会追上front并覆盖数据。解决满判断必须用(Q.rear 1) % MAX_QSIZE Q.front同时记住MAX_QSIZE是最大长度加一实际容量是MAX_QSIZE - 1。4.2 链队列出队后尾指针没回退现象队列里只有一个元素出队后再入队程序崩溃或者新元素接不上。原因删除最后一个结点后Q.rear还指向被free的结点下次EnQueue执行Q.rear-next p时访问了已释放内存。解决出队时加if (Q.rear p) Q.rear Q.front;确保队列变空时rear回到头结点。4.3 循环队列求长度出现负数现象QueueLength返回负值导致后续逻辑判断出错。原因rear绕回数组前面后比front小直接相减得到负数。解决用(Q.rear - Q.front MAX_QSIZE) % MAX_QSIZE加MAX_QSIZE保证结果非负。4.4 遍历时用i rear导致漏元素现象循环队列遍历时只打印了一部分元素rear绕回前面后后面的元素没输出。原因rear可能小于fronti rear的循环条件不成立。解决用while (i ! Q.rear)配合i (i 1) % MAX_QSIZE保证从front走到rear经过所有有效元素。4.5 销毁队列后没有置空指针现象DestroyQueue之后再调用其他操作程序行为异常。原因free之后Q.base或Q.front还保留着原地址成了悬空指针。解决循环队列销毁后Q.base NULL; Q.front Q.rear 0;链队列销毁后Q.front Q.rear NULL;。头歌评测虽然不一定检查这个但养成习惯能避免很多玄学问题。5. 本地验证与调试把两关代码跑通再提交头歌的评测环境是黑匣子提交前最好在本地把两关代码完整跑一遍。我一般用 g 编译把main函数里的输入按题目要求模拟一遍。循环队列的测试输入是 5 个整数但实际只能存 4 个第 5 个入队会失败。题目里for (i 0; i MAX_QSIZE; i)循环 5 次第 5 次EnQueue返回ERROR但main没有检查返回值所以第 5 个元素被丢弃了。这是题目设计如此不是代码问题。跑的时候输入1 2 3 4 5输出应该是队列长度为: 4 现在队列中元素: 1 2 3 4 删除的元素是1 删除的元素是2然后输入一个新元素比如6再入队此时队列长度还是 4元素变成3 4 6。最后GetHead返回3。链队列的测试输入是 5 个整数全部能入队。输入1 2 3 4 5输出队列长度为: 5 现在队列中元素: 1 2 3 4 5 删除的元素是1 删除的元素是2再输入6入队队列长度变成 4元素是3 4 5 6队头是3。本地编译命令g -o circle_queue circle_queue.cpp g -o link_queue link_queue.cpp如果编译报错exit未声明加#include stdlib.h。头歌的代码框架里已经包含了本地跑的时候注意别漏。调试的时候可以在EnQueue和DeQueue里加临时printf打印front、rear和返回值确认每一步的状态符合预期。特别是循环队列的取模运算手动算一遍front和rear的变化比盯着代码看有效得多。提示头歌每关的评测用例不止一组除了题目里展示的输入可能还有空队列出队、满队列入队等边界测试。本地验证时把这些情况都覆盖到提交前心里才有底。从那以后我每次写循环队列都会先在纸上画一圈下标把front和rear的初始位置、入队出队后的移动方向标清楚再动手写代码。链队列则是在出队函数里先写if (Q.rear p) Q.rear Q.front;这一行再补其他逻辑。这两个习惯帮我省了很多次提交失败后的重新调试。希望帮到你。本文还有配套的精品资源点击获取