循环队列和指针是数据结构笔试题里最容易被扣分的组合之一。尤其是“用 C 语言实现循环队列”“说明 front 和 rear 指针的含义”“写出判空和判满条件”这类题目很多人能默写出代码但遇到边界用例时会被问住为什么数组长度为 N 却只能存 N-1 个元素为什么 rear 在数组末尾时入队要回到头部如果 front 和 rear 真的声明成指针变量又该怎么回绕这篇文章围绕循环队列中的指针操作展开从数组下标、指针变量、链表节点三种形态讲清楚循环队列的建模方式再给出可在本地运行的 C 语言复习工程逐步解析高频题目的完整代码。同时把栈放在一起对比因为循环队列和栈经常在同一套数据结构题目里出现复习时把它们放在同一个“解题栈”里理解效率会高很多。学完之后你可以直接应对期末算法题、考研数据结构题以及面试里常见的“手写循环队列”问题。1. 循环队列题目到底在考什么指针、边界和判满策略1.1 循环队列解决的是一开始就被忽略的“假溢出”问题先用最直观的场景说明循环队列为什么存在。假设用一个普通数组实现顺序队列front 指向队头元素rear 指向队尾元素的下一个空位。入队时执行data[rear] x; rear;出队时执行x data[front]; front;。连续入队、出队几次之后front 和 rear 都会不断向后移动。问题是当 rear 移动到数组末尾时即使数组前部已经空出很多位置也无法再入队。这种“数组还有空位但 rear 已经到末尾”的现象就是假溢出。循环队列的解决办法是把数组看成环形。rear 到达末尾后通过取模运算回到数组头部实现空间复用。核心操作只有一个index (index 1) % capacity;这里的 capacity 是数组容量也就是最多能容纳的元素个数。这个取模表达式是循环队列所有题目的基础后面的判空、判满、求长度、遍历全部依赖它。1.2 题目里说的“指针”有三种完全不同的含义很多人在审题时没有做区分导致代码和题目要求对不上。循环队列题目里的“指针”通常指下面三种第一种是数组下标。front 和 rear 被定义成int本质上只是整数索引但教材里习惯叫“队头指针”“队尾指针”。这是最常见、考试最常考的形态。第二种是 C 语言指针变量。front 和 rear 是int *它们指向动态分配的连续数组中的某个位置。更新时要通过“指针是否到达数组末尾”来判断是否回绕。第三种是链表节点指针。循环队列用单链表实现front 指向队头节点rear 指向队尾节点入队时在 rear 后插入新节点出队时删除 front 指向的节点。这种形态下“循环”更多体现在逻辑循环上实际链表中并不需要让尾节点指向头节点。做题前先确认题目要求的是哪一种否则很容易用错思路。后续章节会分别给出数组下标版和指针变量版的完整代码。1.3 判空和判满为什么是循环队列的第一道坎循环队列的空和满有一个让人困惑的地方队列为空时 front rear队列为满时 front 也可能等于 rear。假设容量为 N 的数组front 指向队头元素rear 指向队尾元素的下一个空位。当队列装满 N 个元素时rear 绕一圈后又追上 front此时 front rear和空队列的判断条件完全一致。为了避免这种歧义常用的方案有三种第一种是牺牲一个存储单元。数组长度为 N 时最多存 N-1 个元素。判满条件是(rear 1) % capacity front这样满时 rear 的下一个位置是 front二者不会相等。这是教材和笔试题目中最常见的方案。第二种是增加 size 计数。结构体里多维护一个 int size入队加一出队减一。判空条件是 size 0判满条件是 size capacity。这种方案不牺牲存储单元但每次入队出队都要维护 size。第三种是增加 tag 标志位。用 tag 记录最后一次操作是入队还是出队入队后设置 tag1出队后设置 tag0。当 front rear 时如果 tag 1 说明是满否则是空。笔试中如果不特殊说明默认使用第一种方案。面试时如果要求“不浪费一个存储位置”再考虑 size 计数方案。1.4 与栈的关系同是线性结构考点却截然不同栈是 LIFO只允许在一端操作队列是 FIFO两端分别负责入队和出队。数组栈只需要一个 top 指针数组队列需要 front 和 rear 两个游标。这也是为什么循环队列题目更重视边界条件而栈题目更重视递归、表达式求值、括号匹配等应用。不过在实际刷题中栈和循环队列经常成对出现。比如用两个栈模拟队列。用两个队列模拟栈。BFS 用队列DFS 用栈。表达式求值里既用到栈也可能用到队列来保存后缀表达式。如果把所有线性结构题目整理到一个解题索引里栈、循环队列、链表是三个最核心的入口。“解题栈 Hub”可以理解成一套这样的复习索引不用按教材章节死记而是按题型把栈、队列、链表、树等题放在一起对照循环队列里 front/rear 的边界处理和栈里 top 的边界处理本质上都是同一套“游标移动 边界判断”思维。2. 先分清题目给的是数组下标、指针变量还是链表节点2.1 顺序表模型int 数组 int 下标这是最经典的结构体定义方式#define MAX_SIZE 6 typedef struct { int data[MAX_SIZE]; int front; int rear; } LoopQueue;在这个模型里front 和 rear 是整数下标。front 指向队头元素rear 指向队尾元素的下一个空位。初始化后 front rear 0。判空是front rear判满是(rear 1) % MAX_SIZE front。由于默认牺牲一个存储单元MAX_SIZE 为 6 时最多存储 5 个元素。这种模型的好处是便于调试取模逻辑直观代码运行时可以通过打印 front 和 rear 的值迅速定位问题。期末考试和笔试手写题绝大多数采用这种形式。2.2 动态数组模型int * 指针 指针算术题目如果要求“使用指针实现循环队列”结构体通常这样设计typedef struct { int *base; // 动态数组起始地址 int *front; // 指向队头元素 int *rear; // 指向队尾元素的下一个空位 int capacity; } LoopQueue;此时 front 和 rear 不是下标而是真正的指针。取模运算不能直接写在指针上需要转换为“是否到达数组末尾”的判断。比如入队时把元素写入*rear后执行rear如果rear base capacity就让rear base。指针回绕是这种模型的难点。2.3 链表模型Node 指针 front/reartypedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *front; Node *rear; } LinkedQueue;链表队列不需要考虑假溢出因为节点可以动态申请。但判断题里常见一个坑链式队列的 front 和 rear 指针在队列为空时都指向 NULL出队时需要额外判断 front 是否等于 rear如果相等删除节点后要把 rear 也置为 NULL。链表模型下真正需要重点处理的是内存释放而不是取模。2.4 三种模型对比模型front/rear 的形式判空条件判满条件典型题目数组 下标int 下标front rear(rear 1) % capacity front教材基础题、期末笔试动态数组 指针int * 指针front rear指针边界判断后与 front 比较面试手写题、内存操作题链表节点 指针Node * 指针front NULL无固定判满节点动态分配内存释放、队列销毁、实验报告做题时先看题目初始化语句。如果写的是q.front 0; q.rear 0;就是下标模型。如果写的是q.front q.base;就是指针模型。如果写的是q.front NULL;就是链表模型。3. 搭建一个本地可运行的 C 语言复习工程3.1 为什么建议用最小工程复习循环队列很多数据结构的题目在草稿纸上写一遍和在本机编译运行一遍效果完全不同。手写代码容易漏掉(rear 1) % capacity的括号或者漏掉队列为空时指针置空的分支。这些问题只有通过实际运行才能暴露。复习时不需要引入复杂框架一个单文件 C 程序加上几个测试函数就够了。工程目标有三个用最小代码跑通入队、出队、判空、判满。验证环形回绕逻辑。输出每一步 front、rear 和队列内容方便人工对照。3.2 目录结构和编译方式建议建立以下目录loop_queue_review/ ├── loop_queue_array.c ├── loop_queue_pointer.c ├── linked_queue.c └── test_main.c每个文件独立可编译。编译命令如下gcc -g -Wall loop_queue_array.c test_main.c -o test_array gcc -g -Wall loop_queue_pointer.c test_main.c -o test_pointer gcc -g -Wall linked_queue.c test_main.c -o test_linked-g用于生成调试信息-Wall会提示常见警告。如果使用 Visual Studio可以直接建立空项目把对应源文件加入项目后运行。3.3 一个简单的队列内容打印函数循环队列的遍历和普通数组不同不能从 0 遍历到 capacity-1需要从 front 开始按(i 1) % capacity前进直到 i 等于 rear 结束。打印函数如下void printQueue(LoopQueue *q) { printf(front%d, rear%d, elements: , q-front, q-rear); if (isEmpty(q)) { printf((empty)\n); return; } int i q-front; while (i ! q-rear) { printf(%d , q-data[i]); i (i 1) % MAX_SIZE; } printf(\n); }这段代码必须正确处理队列为空的情况。如果 isEmpty 判断有误循环会死循环。打印的结果要和手写推导一致才能确认后面代码逻辑正确。3.4 验证时的核心检查点完成一个函数后不要只看程序不崩溃需要检查空队列出队时是否会提示“队列为空”而不是返回错误数据。满队列入队时是否会被拒绝。front 移动到 capacity-1 后下一次出队是否回到 0。rear 移动到 capacity-1 后下一次入队是否回到 0。队列长度是否与手算结果一致。后续每一章都会围绕这些检查点写测试用例。4. 数组下标版循环队列一道高频题的完整解析4.1 题目描述设计一个循环队列支持以下操作initQueue初始化队列。enQueue入队成功返回 1失败返回 0。deQueue出队成功返回 1失败返回 0。isEmpty判断队列是否为空。isFull判断队列是否已满。getFront返回队头元素不删除。queueSize返回当前队列长度。约定front 指向队头元素rear 指向队尾元素的下一个空位循环队列容量为 MAX_SIZE最多存储 MAX_SIZE-1 个元素。4.2 完整代码#include stdio.h #include stdbool.h #define MAX_SIZE 6 typedef struct { int data[MAX_SIZE]; int front; int rear; } LoopQueue; void initQueue(LoopQueue *q) { q-front 0; q-rear 0; } bool isEmpty(LoopQueue *q) { return q-front q-rear; } bool isFull(LoopQueue *q) { return (q-rear 1) % MAX_SIZE q-front; } int enQueue(LoopQueue *q, int value) { if (isFull(q)) { printf(Queue is full, cannot enqueue %d\n, value); return 0; } q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; return 1; } int deQueue(LoopQueue *q, int *value) { if (isEmpty(q)) { printf(Queue is empty, cannot dequeue\n); return 0; } *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return 1; } int getFront(LoopQueue *q, int *value) { if (isEmpty(q)) { printf(Queue is empty\n); return 0; } *value q-data[q-front]; return 1; } int queueSize(LoopQueue *q) { return (q-rear - q-front MAX_SIZE) % MAX_SIZE; }4.3 关键点解释这段代码里有几个容易被忽略的地方。第一为什么是(q-rear 1) % MAX_SIZE而不是q-rear 1。当 rear 位于 MAX_SIZE-1 时rear1 等于 MAX_SIZE取模后变成 0正好回到数组头部。如果没有取模判满逻辑在 rear 未到数组末尾时可以工作但一旦 rear 到达末尾就会判断错误。第二入队时先写入元素再移动 rear。如果先移动 rearrear 指向的位置会变成下一个空位元素写入的位置就会错位。这是顺序队列和循环队列共有的基本约定。第三queueSize的公式是(rear - front capacity) % capacity。为什么需要加 capacity因为循环后可能 rear 小于 front此时rear - front是负数加上 capacity 保证结果为正再取模得到正确的元素个数。例如 capacity 为 6front 为 4rear 为 1实际元素是下标 4、5、0 三个元素公式计算为(1 - 4 6) % 6 3正确。4.4 测试用例与预期结果测试操作操作序列预期输出初始化initQueuefront0, rear0空队列出队deQueue返回 0提示队列为空入队 5 个元素enQueue 1-5第 6 次入队返回 0出队 2 个元素deQueue 两次先得到 1再得到 2继续入队 2 个元素enQueue 6, 7front2, rear1? 需要配合具体位置判断长度计算queueSize与剩余元素个数一致清空后判断出队到空isEmpty 返回 true建议在 main 函数中逐步打印 front、rear 和队列内容确认环形回绕发生的位置。5. 指针变量版循环队列连续数组加指针回绕5.1 题目描述题目如果要求“不通过下标使用指针实现循环队列”本质上是把上文的 int front 替换成 int * 指针。这里的关键不是写元素而是指针如何回绕。结构体定义如下typedef struct { int *base; // 动态数组起始地址 int *front; // 指向队头元素 int *rear; // 指向队尾元素的下一个空位 int capacity; // 数组容量 } PointerLoopQueue;初始化时动态分配 capacity 个 int 空间front 和 rear 都指向 base。5.2 完整代码#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *base; int *front; int *rear; int capacity; } PointerLoopQueue; void initPointerQueue(PointerLoopQueue *q, int capacity) { q-base (int *)malloc(sizeof(int) * capacity); if (q-base NULL) { printf(malloc failed\n); exit(1); } q-capacity capacity; q-front q-base; q-rear q-base; } bool isEmpty(PointerLoopQueue *q) { return q-front q-rear; } bool isFull(PointerLoopQueue *q) { if (q-rear 1 q-base q-capacity) { return q-front q-base; } return q-rear 1 q-front; } int enQueue(PointerLoopQueue *q, int value) { if (isFull(q)) { printf(Queue is full, cannot enqueue %d\n, value); return 0; } *(q-rear) value; if (q-rear 1 q-base q-capacity) { q-rear q-base; } else { q-rear; } return 1; } int deQueue(PointerLoopQueue *q, int *value) { if (isEmpty(q)) { printf(Queue is empty, cannot dequeue\n); return 0; } *value *(q-front); if (q-front 1 q-base q-capacity) { q-front q-base; } else { q-front; } return 1; } void destroyPointerQueue(PointerLoopQueue *q) { free(q-base); q-base NULL; q-front NULL; q-rear NULL; }5.3 指针版本最关键的三个易错点第一指针取模不能直接写。下标版本里(rear 1) % capacity一行代码解决问题指针版本必须判断rear 1是否越界。如果直接写rear当 rear 指向数组最后一个元素时rear 1会越过 base capacity成为野指针。回绕判断是这道题的核心考点。第二计算队列长度时不能直接用rear - front。在循环状态下如果 rear 已经回绕到 base而 front 还在数组后半段rear - front是负数。正确写法是int pointerQueueSize(PointerLoopQueue *q) { return (q-rear - q-front q-capacity) % q-capacity; }这里的底层逻辑和下标版本一致只是把下标差换成了指针差。指针差单位是元素个数正好对应队列长度。第三销毁队列的顺序不能错。必须先释放 base 指向的动态数组再把 front、rear、base 都置为 NULL。如果没有释放 base 就释放结构体会发生内存泄漏。如果释放后再调用 isEmpty又会因为访问野指针产生不可预知的错误。5.4 链表式循环队列与内存释放补充链表式循环队列没有数组回绕问题但多了一个内存释放的考点。释放时不能只 free 结构体要先把所有节点逐个释放。示例代码如下void clearLinkedQueue(LinkedQueue *q) { Node *cur q-front; while (cur ! NULL) { Node *tmp cur; cur cur-next; free(tmp); } q-front NULL; q-rear NULL; }如果队列只有一个节点出队删除节点后需要检查front rear并把 rear 置为 NULL。很多实现漏掉这一步导致删除最后一个节点后 rear 变成野指针后续入队操作直接崩溃。注意内存释放类题目最危险的不是入队出队逻辑而是“最后一个节点删除后 rear 是否置空”和“动态数组使用完后是否 free”。写链表队列时把这两个分支单独用测试用例覆盖。6. 循环队列与栈的配合考查如何在一套题里快速切换6.1 为什么复习时要把栈和队列放在同一个解题索引里很多复习资料把栈和队列分成两章但笔试题目经常把它们放在一起考。典型的组合有用两个栈实现队列。用两个队列实现栈。用栈做表达式求值用队列保存输出结果。BFS 使用队列DFS 使用栈二者解决同一类遍历问题。因此建议按“栈 队列”作为一组题目进行复习。栈的 top 指针指向栈顶元素队列的 front/rear 游标指向队头和队尾虽然结构不同但“移动游标 判断边界”的思维方式完全一致。复习时把两个结构的代码并排放在一起更容易看出它们的异同。6.2 用两个栈实现队列的解题思路题目要求只能使用栈的 push、pop、isEmpty 操作模拟队列的入队和出队。思路是维护两个栈inStack 负责入队outStack 负责出队。入队时直接 push 到 inStack。出队时如果 outStack 为空先把 inStack 中所有元素 pop 出来再 push 到 outStack然后从 outStack pop 一个元素。伪代码如下void enqueue(int x) { push(inStack, x); } int dequeue() { if (isEmpty(outStack)) { while (!isEmpty(inStack)) { int x top(inStack); pop(inStack); push(outStack, x); } } int result top(outStack); pop(outStack); return result; }这段代码的巧妙之处在于inStack 底部元素会先进入 outStack 的顶部从而实现了先进先出。复杂度上每个元素最多被移动两次均摊复杂度为 O(1)。6.3 用两个队列实现栈的解题思路题目要求只能使用队列的入队、出队、isEmpty 操作模拟栈的 push 和 pop。思路是始终保持一个队列为空另一个队列存元素。入栈时把元素放入非空队列。出栈时把非空队列中除最后一个元素外的所有元素移到空队列再出队最后一个元素这时两个队列的角色互换。关键判断是void push(int x) { if (!isEmpty(q1)) { enqueue(q1, x); } else { enqueue(q2, x); } } int pop() { if (isEmpty(q1) isEmpty(q2)) return -1; if (isEmpty(q1)) { while (queueSize(q2) 1) { enqueue(q1, dequeue(q2)); } return dequeue(q2); } else { while (queueSize(q1) 1) { enqueue(q2, dequeue(q1)); } return dequeue(q1); } }没有使用循环队列时普通队列也可以完成这道题。但使用循环队列时queueSize 公式是否写对会直接影响判断“是否还剩最后一个元素”。6.4 栈与循环队列的对比表维度栈循环队列数据访问顺序LIFO后进先出FIFO先进先出操作端一端操作top 指针两端操作front 和 rear数组实现的关键指针topfront、rear边界判断top -1 空top capacity-1 满front rear 空牺牲一个空间判满常见题目括号匹配、表达式求值、函数调用栈约瑟夫环、循环缓冲区、BFS与递归的关系递归调用依赖系统栈层级遍历依赖队列这张表适合在复习最后阶段作为自测清单。能在不看资料的情况下解释清楚每一项说明基础已经比较牢固。7. 典型边界题目与易错点7.1 计算循环队列长度的通用公式已知 front 和 rear容量为 capacity队列长度公式int length (rear - front capacity) % capacity;这个公式适用于 front 和 rear 都是下标或指针差的情况。容量必须取模前的最大值而不是 capacity-1。如果取成 capacity-1当一个元素都没有时公式会得到 capacity-1明显错误。7.2 环形遍历循环队列遍历循环队列要从 front 开始按取模方式向后移动直到回到 rear。常见的错误是写成for (i 0; i capacity; i)这样会输出空位上的垃圾数据。正确写法在 3.3 节已经给出核心是循环条件i ! rear和步进i (i 1) % capacity。7.3 题目陷阱容量为 6 的数组最多存放 5 个元素如果题目明确说明“不增加辅助变量必须牺牲一个存储单元”那么容量为 N 的数组最大元素个数是 N-1。这个结论经常出现在判断题和选择题中。举例MAX_SIZE 6依次入队 6 个数最后一个入队操作应该失败。如果代码允许 6 个数全部入队说明判满逻辑写错了。测试用例必须覆盖这一条。7.4 三个高频坑的完整排查第一个坑判满条件没有取模只有front rear 1。现象是 rear 在数组中间时判断正确rear 到达数组末尾后判满失效。解决办法是统一写成(rear 1) % capacity front。第二个坑指针版本中 front 和 rear 越界后没有回绕。现象是程序输出正常但数组尾部越界写入可能覆盖其他变量导致难以定位的诡异错误。解决办法是在入队、出队后都判断指针是否等于base capacity如果是则回到 base。第三个坑链表队列删除最后一个节点后没有将 rear 置空。现象是删除最后一个元素后再入队程序访问野指针崩溃。解决办法是出队时判断front rear如果相等删除节点后把 front 和 rear 都置为 NULL。第四个坑测试用例没有覆盖空队列和满队列。现象是代码能跑通正常入出队但一遇到空队列出队或满队列入队就返回错误结果。解决办法是设计专门测试函数把空、满、绕回三种边界全部覆盖。8. 复习和面试时的排查链路与清单8.1 遇到循环队列题先走的六步排查链路不管题目是笔试代码题还是面试手写题建议按以下顺序检查确认 front 和 rear 的语义。front 指向队头元素rear 指向队尾元素还是 rear 指向队尾元素的下一个空位两个约定不同判空判满逻辑完全不同。确认 front 和 rear 的类型。是 int 下标还是 int * 指针还是 Node *。确认数组长度与容量的关系。数组长度为 N 时最多存放 N-1 个元素还是 N 个。检查判空条件。初始状态、连续出队后状态是否都正确。检查判满条件。rear 在数组末尾时是否仍能正确判断。检查指针回绕。入队、出队、遍历时是否都在取模或回绕后继续操作。如果程序崩溃还要增加第 7 步检查动态内存是否越界、是否释放后被继续访问。8.2 空指针和野指针问题的排查方法如果程序运行时报段错误或者输出结果随机变化原因很可能出在指针操作上。常见的排查工具和命令如下# 使用 gdb 定位崩溃位置 gdb ./test_pointer run bt # 使用 valgrind 检测内存泄漏和非法访问 valgrind --leak-checkfull ./test_pointer手动排查时在 front 和 rear 每次变化的代码处打印它们的地址printf(after enqueue: front%p, rear%p, base%p, basecap%p\n, (void *)q-front, (void *)q-rear, (void *)q-base, (void *)(q-base q-capacity));观察 front 和 rear 是否超过 base capacity。如果超过说明回绕条件写错了如果没有超过但程序仍然崩溃说明访问的元素不在队列范围内。注意指针操作题的排查顺序应该是“先确认指针是否越界再确认是否访问了已释放内存最后确认是否初始化失败”。不要一开始就怀疑编译器或系统环境数据结构题目里绝大多数崩溃都来自自身指针逻辑错误。8.3 循环队列复习完成度检查清单检查项能否不看资料完成备注手写数组下标版循环队列是 / 否需要包含判空、判满、入队、出队、长度解释为什么牺牲一个存储单元是 / 否能说明 front rear 时无法区分空满写出 queueSize 公式是 / 否(rear - front capacity) % capacity手写指针变量版循环队列是 / 否需要包含指针回绕手写链表式循环队列是 / 否需要包含最后一个节点删除后的 rear 置空写出两个栈实现队列是 / 否需要理解 inStack 和 outStack 的角色转换写出两个队列实现栈是 / 否需要理解非空队列与空队列的角色互换说明 BFS 用队列、DFS 用栈的原因是 / 否体现对 FIFO 和 LIFO 语义的理解这个清单既可以作为期末复习的收尾自测也可以作为面试前一晚的速查表。8.4 下一步扩展方向循环队列的基本代码掌握之后可以往几个方向继续深入。第一个方向是环形缓冲区。操作系统、消息队列、音视频播放器里常见的 RingBuffer本质就是循环队列的生产者消费者版本。区别在于生产者和消费者各自维护一个写指针和读指针需要考虑并发访问。可以先从单线程版本开始再引入锁或无锁队列。第二个方向是 Redis 中的列表结构。Redis 的 List 在数据量较小时使用压缩列表数据量较大时使用 quicklist其中也涉及链表节点和连续内存块的组合。理解 C 语言的链表队列后再读 Redis 源码会容易很多。第三个方向是刷题整合。把栈、队列、链表、字符串相关的题目整理到一个自己的解法索引里每道题记录使用场景、边界条件和复杂度。这比按照教材顺序零散复习更有效。数据结构期末复习中循环队列的指针题是性价比很高的一类题代码量不大但边界条件密集只要把“牺牲一个存储单元”和“指针回绕”两个关键点掌握清楚就能拿分。建议今天就把第 4 章的数组版代码在本地跑一遍再用第 5 章的指针版做对比最后用第 8 章的检查清单自测一轮。 循环队列与指针详解：C语言实现及面试易错点全解析
循环队列和指针是数据结构笔试题里最容易被扣分的组合之一。尤其是“用 C 语言实现循环队列”“说明 front 和 rear 指针的含义”“写出判空和判满条件”这类题目很多人能默写出代码但遇到边界用例时会被问住为什么数组长度为 N 却只能存 N-1 个元素为什么 rear 在数组末尾时入队要回到头部如果 front 和 rear 真的声明成指针变量又该怎么回绕这篇文章围绕循环队列中的指针操作展开从数组下标、指针变量、链表节点三种形态讲清楚循环队列的建模方式再给出可在本地运行的 C 语言复习工程逐步解析高频题目的完整代码。同时把栈放在一起对比因为循环队列和栈经常在同一套数据结构题目里出现复习时把它们放在同一个“解题栈”里理解效率会高很多。学完之后你可以直接应对期末算法题、考研数据结构题以及面试里常见的“手写循环队列”问题。1. 循环队列题目到底在考什么指针、边界和判满策略1.1 循环队列解决的是一开始就被忽略的“假溢出”问题先用最直观的场景说明循环队列为什么存在。假设用一个普通数组实现顺序队列front 指向队头元素rear 指向队尾元素的下一个空位。入队时执行data[rear] x; rear;出队时执行x data[front]; front;。连续入队、出队几次之后front 和 rear 都会不断向后移动。问题是当 rear 移动到数组末尾时即使数组前部已经空出很多位置也无法再入队。这种“数组还有空位但 rear 已经到末尾”的现象就是假溢出。循环队列的解决办法是把数组看成环形。rear 到达末尾后通过取模运算回到数组头部实现空间复用。核心操作只有一个index (index 1) % capacity;这里的 capacity 是数组容量也就是最多能容纳的元素个数。这个取模表达式是循环队列所有题目的基础后面的判空、判满、求长度、遍历全部依赖它。1.2 题目里说的“指针”有三种完全不同的含义很多人在审题时没有做区分导致代码和题目要求对不上。循环队列题目里的“指针”通常指下面三种第一种是数组下标。front 和 rear 被定义成int本质上只是整数索引但教材里习惯叫“队头指针”“队尾指针”。这是最常见、考试最常考的形态。第二种是 C 语言指针变量。front 和 rear 是int *它们指向动态分配的连续数组中的某个位置。更新时要通过“指针是否到达数组末尾”来判断是否回绕。第三种是链表节点指针。循环队列用单链表实现front 指向队头节点rear 指向队尾节点入队时在 rear 后插入新节点出队时删除 front 指向的节点。这种形态下“循环”更多体现在逻辑循环上实际链表中并不需要让尾节点指向头节点。做题前先确认题目要求的是哪一种否则很容易用错思路。后续章节会分别给出数组下标版和指针变量版的完整代码。1.3 判空和判满为什么是循环队列的第一道坎循环队列的空和满有一个让人困惑的地方队列为空时 front rear队列为满时 front 也可能等于 rear。假设容量为 N 的数组front 指向队头元素rear 指向队尾元素的下一个空位。当队列装满 N 个元素时rear 绕一圈后又追上 front此时 front rear和空队列的判断条件完全一致。为了避免这种歧义常用的方案有三种第一种是牺牲一个存储单元。数组长度为 N 时最多存 N-1 个元素。判满条件是(rear 1) % capacity front这样满时 rear 的下一个位置是 front二者不会相等。这是教材和笔试题目中最常见的方案。第二种是增加 size 计数。结构体里多维护一个 int size入队加一出队减一。判空条件是 size 0判满条件是 size capacity。这种方案不牺牲存储单元但每次入队出队都要维护 size。第三种是增加 tag 标志位。用 tag 记录最后一次操作是入队还是出队入队后设置 tag1出队后设置 tag0。当 front rear 时如果 tag 1 说明是满否则是空。笔试中如果不特殊说明默认使用第一种方案。面试时如果要求“不浪费一个存储位置”再考虑 size 计数方案。1.4 与栈的关系同是线性结构考点却截然不同栈是 LIFO只允许在一端操作队列是 FIFO两端分别负责入队和出队。数组栈只需要一个 top 指针数组队列需要 front 和 rear 两个游标。这也是为什么循环队列题目更重视边界条件而栈题目更重视递归、表达式求值、括号匹配等应用。不过在实际刷题中栈和循环队列经常成对出现。比如用两个栈模拟队列。用两个队列模拟栈。BFS 用队列DFS 用栈。表达式求值里既用到栈也可能用到队列来保存后缀表达式。如果把所有线性结构题目整理到一个解题索引里栈、循环队列、链表是三个最核心的入口。“解题栈 Hub”可以理解成一套这样的复习索引不用按教材章节死记而是按题型把栈、队列、链表、树等题放在一起对照循环队列里 front/rear 的边界处理和栈里 top 的边界处理本质上都是同一套“游标移动 边界判断”思维。2. 先分清题目给的是数组下标、指针变量还是链表节点2.1 顺序表模型int 数组 int 下标这是最经典的结构体定义方式#define MAX_SIZE 6 typedef struct { int data[MAX_SIZE]; int front; int rear; } LoopQueue;在这个模型里front 和 rear 是整数下标。front 指向队头元素rear 指向队尾元素的下一个空位。初始化后 front rear 0。判空是front rear判满是(rear 1) % MAX_SIZE front。由于默认牺牲一个存储单元MAX_SIZE 为 6 时最多存储 5 个元素。这种模型的好处是便于调试取模逻辑直观代码运行时可以通过打印 front 和 rear 的值迅速定位问题。期末考试和笔试手写题绝大多数采用这种形式。2.2 动态数组模型int * 指针 指针算术题目如果要求“使用指针实现循环队列”结构体通常这样设计typedef struct { int *base; // 动态数组起始地址 int *front; // 指向队头元素 int *rear; // 指向队尾元素的下一个空位 int capacity; } LoopQueue;此时 front 和 rear 不是下标而是真正的指针。取模运算不能直接写在指针上需要转换为“是否到达数组末尾”的判断。比如入队时把元素写入*rear后执行rear如果rear base capacity就让rear base。指针回绕是这种模型的难点。2.3 链表模型Node 指针 front/reartypedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *front; Node *rear; } LinkedQueue;链表队列不需要考虑假溢出因为节点可以动态申请。但判断题里常见一个坑链式队列的 front 和 rear 指针在队列为空时都指向 NULL出队时需要额外判断 front 是否等于 rear如果相等删除节点后要把 rear 也置为 NULL。链表模型下真正需要重点处理的是内存释放而不是取模。2.4 三种模型对比模型front/rear 的形式判空条件判满条件典型题目数组 下标int 下标front rear(rear 1) % capacity front教材基础题、期末笔试动态数组 指针int * 指针front rear指针边界判断后与 front 比较面试手写题、内存操作题链表节点 指针Node * 指针front NULL无固定判满节点动态分配内存释放、队列销毁、实验报告做题时先看题目初始化语句。如果写的是q.front 0; q.rear 0;就是下标模型。如果写的是q.front q.base;就是指针模型。如果写的是q.front NULL;就是链表模型。3. 搭建一个本地可运行的 C 语言复习工程3.1 为什么建议用最小工程复习循环队列很多数据结构的题目在草稿纸上写一遍和在本机编译运行一遍效果完全不同。手写代码容易漏掉(rear 1) % capacity的括号或者漏掉队列为空时指针置空的分支。这些问题只有通过实际运行才能暴露。复习时不需要引入复杂框架一个单文件 C 程序加上几个测试函数就够了。工程目标有三个用最小代码跑通入队、出队、判空、判满。验证环形回绕逻辑。输出每一步 front、rear 和队列内容方便人工对照。3.2 目录结构和编译方式建议建立以下目录loop_queue_review/ ├── loop_queue_array.c ├── loop_queue_pointer.c ├── linked_queue.c └── test_main.c每个文件独立可编译。编译命令如下gcc -g -Wall loop_queue_array.c test_main.c -o test_array gcc -g -Wall loop_queue_pointer.c test_main.c -o test_pointer gcc -g -Wall linked_queue.c test_main.c -o test_linked-g用于生成调试信息-Wall会提示常见警告。如果使用 Visual Studio可以直接建立空项目把对应源文件加入项目后运行。3.3 一个简单的队列内容打印函数循环队列的遍历和普通数组不同不能从 0 遍历到 capacity-1需要从 front 开始按(i 1) % capacity前进直到 i 等于 rear 结束。打印函数如下void printQueue(LoopQueue *q) { printf(front%d, rear%d, elements: , q-front, q-rear); if (isEmpty(q)) { printf((empty)\n); return; } int i q-front; while (i ! q-rear) { printf(%d , q-data[i]); i (i 1) % MAX_SIZE; } printf(\n); }这段代码必须正确处理队列为空的情况。如果 isEmpty 判断有误循环会死循环。打印的结果要和手写推导一致才能确认后面代码逻辑正确。3.4 验证时的核心检查点完成一个函数后不要只看程序不崩溃需要检查空队列出队时是否会提示“队列为空”而不是返回错误数据。满队列入队时是否会被拒绝。front 移动到 capacity-1 后下一次出队是否回到 0。rear 移动到 capacity-1 后下一次入队是否回到 0。队列长度是否与手算结果一致。后续每一章都会围绕这些检查点写测试用例。4. 数组下标版循环队列一道高频题的完整解析4.1 题目描述设计一个循环队列支持以下操作initQueue初始化队列。enQueue入队成功返回 1失败返回 0。deQueue出队成功返回 1失败返回 0。isEmpty判断队列是否为空。isFull判断队列是否已满。getFront返回队头元素不删除。queueSize返回当前队列长度。约定front 指向队头元素rear 指向队尾元素的下一个空位循环队列容量为 MAX_SIZE最多存储 MAX_SIZE-1 个元素。4.2 完整代码#include stdio.h #include stdbool.h #define MAX_SIZE 6 typedef struct { int data[MAX_SIZE]; int front; int rear; } LoopQueue; void initQueue(LoopQueue *q) { q-front 0; q-rear 0; } bool isEmpty(LoopQueue *q) { return q-front q-rear; } bool isFull(LoopQueue *q) { return (q-rear 1) % MAX_SIZE q-front; } int enQueue(LoopQueue *q, int value) { if (isFull(q)) { printf(Queue is full, cannot enqueue %d\n, value); return 0; } q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; return 1; } int deQueue(LoopQueue *q, int *value) { if (isEmpty(q)) { printf(Queue is empty, cannot dequeue\n); return 0; } *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return 1; } int getFront(LoopQueue *q, int *value) { if (isEmpty(q)) { printf(Queue is empty\n); return 0; } *value q-data[q-front]; return 1; } int queueSize(LoopQueue *q) { return (q-rear - q-front MAX_SIZE) % MAX_SIZE; }4.3 关键点解释这段代码里有几个容易被忽略的地方。第一为什么是(q-rear 1) % MAX_SIZE而不是q-rear 1。当 rear 位于 MAX_SIZE-1 时rear1 等于 MAX_SIZE取模后变成 0正好回到数组头部。如果没有取模判满逻辑在 rear 未到数组末尾时可以工作但一旦 rear 到达末尾就会判断错误。第二入队时先写入元素再移动 rear。如果先移动 rearrear 指向的位置会变成下一个空位元素写入的位置就会错位。这是顺序队列和循环队列共有的基本约定。第三queueSize的公式是(rear - front capacity) % capacity。为什么需要加 capacity因为循环后可能 rear 小于 front此时rear - front是负数加上 capacity 保证结果为正再取模得到正确的元素个数。例如 capacity 为 6front 为 4rear 为 1实际元素是下标 4、5、0 三个元素公式计算为(1 - 4 6) % 6 3正确。4.4 测试用例与预期结果测试操作操作序列预期输出初始化initQueuefront0, rear0空队列出队deQueue返回 0提示队列为空入队 5 个元素enQueue 1-5第 6 次入队返回 0出队 2 个元素deQueue 两次先得到 1再得到 2继续入队 2 个元素enQueue 6, 7front2, rear1? 需要配合具体位置判断长度计算queueSize与剩余元素个数一致清空后判断出队到空isEmpty 返回 true建议在 main 函数中逐步打印 front、rear 和队列内容确认环形回绕发生的位置。5. 指针变量版循环队列连续数组加指针回绕5.1 题目描述题目如果要求“不通过下标使用指针实现循环队列”本质上是把上文的 int front 替换成 int * 指针。这里的关键不是写元素而是指针如何回绕。结构体定义如下typedef struct { int *base; // 动态数组起始地址 int *front; // 指向队头元素 int *rear; // 指向队尾元素的下一个空位 int capacity; // 数组容量 } PointerLoopQueue;初始化时动态分配 capacity 个 int 空间front 和 rear 都指向 base。5.2 完整代码#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *base; int *front; int *rear; int capacity; } PointerLoopQueue; void initPointerQueue(PointerLoopQueue *q, int capacity) { q-base (int *)malloc(sizeof(int) * capacity); if (q-base NULL) { printf(malloc failed\n); exit(1); } q-capacity capacity; q-front q-base; q-rear q-base; } bool isEmpty(PointerLoopQueue *q) { return q-front q-rear; } bool isFull(PointerLoopQueue *q) { if (q-rear 1 q-base q-capacity) { return q-front q-base; } return q-rear 1 q-front; } int enQueue(PointerLoopQueue *q, int value) { if (isFull(q)) { printf(Queue is full, cannot enqueue %d\n, value); return 0; } *(q-rear) value; if (q-rear 1 q-base q-capacity) { q-rear q-base; } else { q-rear; } return 1; } int deQueue(PointerLoopQueue *q, int *value) { if (isEmpty(q)) { printf(Queue is empty, cannot dequeue\n); return 0; } *value *(q-front); if (q-front 1 q-base q-capacity) { q-front q-base; } else { q-front; } return 1; } void destroyPointerQueue(PointerLoopQueue *q) { free(q-base); q-base NULL; q-front NULL; q-rear NULL; }5.3 指针版本最关键的三个易错点第一指针取模不能直接写。下标版本里(rear 1) % capacity一行代码解决问题指针版本必须判断rear 1是否越界。如果直接写rear当 rear 指向数组最后一个元素时rear 1会越过 base capacity成为野指针。回绕判断是这道题的核心考点。第二计算队列长度时不能直接用rear - front。在循环状态下如果 rear 已经回绕到 base而 front 还在数组后半段rear - front是负数。正确写法是int pointerQueueSize(PointerLoopQueue *q) { return (q-rear - q-front q-capacity) % q-capacity; }这里的底层逻辑和下标版本一致只是把下标差换成了指针差。指针差单位是元素个数正好对应队列长度。第三销毁队列的顺序不能错。必须先释放 base 指向的动态数组再把 front、rear、base 都置为 NULL。如果没有释放 base 就释放结构体会发生内存泄漏。如果释放后再调用 isEmpty又会因为访问野指针产生不可预知的错误。5.4 链表式循环队列与内存释放补充链表式循环队列没有数组回绕问题但多了一个内存释放的考点。释放时不能只 free 结构体要先把所有节点逐个释放。示例代码如下void clearLinkedQueue(LinkedQueue *q) { Node *cur q-front; while (cur ! NULL) { Node *tmp cur; cur cur-next; free(tmp); } q-front NULL; q-rear NULL; }如果队列只有一个节点出队删除节点后需要检查front rear并把 rear 置为 NULL。很多实现漏掉这一步导致删除最后一个节点后 rear 变成野指针后续入队操作直接崩溃。注意内存释放类题目最危险的不是入队出队逻辑而是“最后一个节点删除后 rear 是否置空”和“动态数组使用完后是否 free”。写链表队列时把这两个分支单独用测试用例覆盖。6. 循环队列与栈的配合考查如何在一套题里快速切换6.1 为什么复习时要把栈和队列放在同一个解题索引里很多复习资料把栈和队列分成两章但笔试题目经常把它们放在一起考。典型的组合有用两个栈实现队列。用两个队列实现栈。用栈做表达式求值用队列保存输出结果。BFS 使用队列DFS 使用栈二者解决同一类遍历问题。因此建议按“栈 队列”作为一组题目进行复习。栈的 top 指针指向栈顶元素队列的 front/rear 游标指向队头和队尾虽然结构不同但“移动游标 判断边界”的思维方式完全一致。复习时把两个结构的代码并排放在一起更容易看出它们的异同。6.2 用两个栈实现队列的解题思路题目要求只能使用栈的 push、pop、isEmpty 操作模拟队列的入队和出队。思路是维护两个栈inStack 负责入队outStack 负责出队。入队时直接 push 到 inStack。出队时如果 outStack 为空先把 inStack 中所有元素 pop 出来再 push 到 outStack然后从 outStack pop 一个元素。伪代码如下void enqueue(int x) { push(inStack, x); } int dequeue() { if (isEmpty(outStack)) { while (!isEmpty(inStack)) { int x top(inStack); pop(inStack); push(outStack, x); } } int result top(outStack); pop(outStack); return result; }这段代码的巧妙之处在于inStack 底部元素会先进入 outStack 的顶部从而实现了先进先出。复杂度上每个元素最多被移动两次均摊复杂度为 O(1)。6.3 用两个队列实现栈的解题思路题目要求只能使用队列的入队、出队、isEmpty 操作模拟栈的 push 和 pop。思路是始终保持一个队列为空另一个队列存元素。入栈时把元素放入非空队列。出栈时把非空队列中除最后一个元素外的所有元素移到空队列再出队最后一个元素这时两个队列的角色互换。关键判断是void push(int x) { if (!isEmpty(q1)) { enqueue(q1, x); } else { enqueue(q2, x); } } int pop() { if (isEmpty(q1) isEmpty(q2)) return -1; if (isEmpty(q1)) { while (queueSize(q2) 1) { enqueue(q1, dequeue(q2)); } return dequeue(q2); } else { while (queueSize(q1) 1) { enqueue(q2, dequeue(q1)); } return dequeue(q1); } }没有使用循环队列时普通队列也可以完成这道题。但使用循环队列时queueSize 公式是否写对会直接影响判断“是否还剩最后一个元素”。6.4 栈与循环队列的对比表维度栈循环队列数据访问顺序LIFO后进先出FIFO先进先出操作端一端操作top 指针两端操作front 和 rear数组实现的关键指针topfront、rear边界判断top -1 空top capacity-1 满front rear 空牺牲一个空间判满常见题目括号匹配、表达式求值、函数调用栈约瑟夫环、循环缓冲区、BFS与递归的关系递归调用依赖系统栈层级遍历依赖队列这张表适合在复习最后阶段作为自测清单。能在不看资料的情况下解释清楚每一项说明基础已经比较牢固。7. 典型边界题目与易错点7.1 计算循环队列长度的通用公式已知 front 和 rear容量为 capacity队列长度公式int length (rear - front capacity) % capacity;这个公式适用于 front 和 rear 都是下标或指针差的情况。容量必须取模前的最大值而不是 capacity-1。如果取成 capacity-1当一个元素都没有时公式会得到 capacity-1明显错误。7.2 环形遍历循环队列遍历循环队列要从 front 开始按取模方式向后移动直到回到 rear。常见的错误是写成for (i 0; i capacity; i)这样会输出空位上的垃圾数据。正确写法在 3.3 节已经给出核心是循环条件i ! rear和步进i (i 1) % capacity。7.3 题目陷阱容量为 6 的数组最多存放 5 个元素如果题目明确说明“不增加辅助变量必须牺牲一个存储单元”那么容量为 N 的数组最大元素个数是 N-1。这个结论经常出现在判断题和选择题中。举例MAX_SIZE 6依次入队 6 个数最后一个入队操作应该失败。如果代码允许 6 个数全部入队说明判满逻辑写错了。测试用例必须覆盖这一条。7.4 三个高频坑的完整排查第一个坑判满条件没有取模只有front rear 1。现象是 rear 在数组中间时判断正确rear 到达数组末尾后判满失效。解决办法是统一写成(rear 1) % capacity front。第二个坑指针版本中 front 和 rear 越界后没有回绕。现象是程序输出正常但数组尾部越界写入可能覆盖其他变量导致难以定位的诡异错误。解决办法是在入队、出队后都判断指针是否等于base capacity如果是则回到 base。第三个坑链表队列删除最后一个节点后没有将 rear 置空。现象是删除最后一个元素后再入队程序访问野指针崩溃。解决办法是出队时判断front rear如果相等删除节点后把 front 和 rear 都置为 NULL。第四个坑测试用例没有覆盖空队列和满队列。现象是代码能跑通正常入出队但一遇到空队列出队或满队列入队就返回错误结果。解决办法是设计专门测试函数把空、满、绕回三种边界全部覆盖。8. 复习和面试时的排查链路与清单8.1 遇到循环队列题先走的六步排查链路不管题目是笔试代码题还是面试手写题建议按以下顺序检查确认 front 和 rear 的语义。front 指向队头元素rear 指向队尾元素还是 rear 指向队尾元素的下一个空位两个约定不同判空判满逻辑完全不同。确认 front 和 rear 的类型。是 int 下标还是 int * 指针还是 Node *。确认数组长度与容量的关系。数组长度为 N 时最多存放 N-1 个元素还是 N 个。检查判空条件。初始状态、连续出队后状态是否都正确。检查判满条件。rear 在数组末尾时是否仍能正确判断。检查指针回绕。入队、出队、遍历时是否都在取模或回绕后继续操作。如果程序崩溃还要增加第 7 步检查动态内存是否越界、是否释放后被继续访问。8.2 空指针和野指针问题的排查方法如果程序运行时报段错误或者输出结果随机变化原因很可能出在指针操作上。常见的排查工具和命令如下# 使用 gdb 定位崩溃位置 gdb ./test_pointer run bt # 使用 valgrind 检测内存泄漏和非法访问 valgrind --leak-checkfull ./test_pointer手动排查时在 front 和 rear 每次变化的代码处打印它们的地址printf(after enqueue: front%p, rear%p, base%p, basecap%p\n, (void *)q-front, (void *)q-rear, (void *)q-base, (void *)(q-base q-capacity));观察 front 和 rear 是否超过 base capacity。如果超过说明回绕条件写错了如果没有超过但程序仍然崩溃说明访问的元素不在队列范围内。注意指针操作题的排查顺序应该是“先确认指针是否越界再确认是否访问了已释放内存最后确认是否初始化失败”。不要一开始就怀疑编译器或系统环境数据结构题目里绝大多数崩溃都来自自身指针逻辑错误。8.3 循环队列复习完成度检查清单检查项能否不看资料完成备注手写数组下标版循环队列是 / 否需要包含判空、判满、入队、出队、长度解释为什么牺牲一个存储单元是 / 否能说明 front rear 时无法区分空满写出 queueSize 公式是 / 否(rear - front capacity) % capacity手写指针变量版循环队列是 / 否需要包含指针回绕手写链表式循环队列是 / 否需要包含最后一个节点删除后的 rear 置空写出两个栈实现队列是 / 否需要理解 inStack 和 outStack 的角色转换写出两个队列实现栈是 / 否需要理解非空队列与空队列的角色互换说明 BFS 用队列、DFS 用栈的原因是 / 否体现对 FIFO 和 LIFO 语义的理解这个清单既可以作为期末复习的收尾自测也可以作为面试前一晚的速查表。8.4 下一步扩展方向循环队列的基本代码掌握之后可以往几个方向继续深入。第一个方向是环形缓冲区。操作系统、消息队列、音视频播放器里常见的 RingBuffer本质就是循环队列的生产者消费者版本。区别在于生产者和消费者各自维护一个写指针和读指针需要考虑并发访问。可以先从单线程版本开始再引入锁或无锁队列。第二个方向是 Redis 中的列表结构。Redis 的 List 在数据量较小时使用压缩列表数据量较大时使用 quicklist其中也涉及链表节点和连续内存块的组合。理解 C 语言的链表队列后再读 Redis 源码会容易很多。第三个方向是刷题整合。把栈、队列、链表、字符串相关的题目整理到一个自己的解法索引里每道题记录使用场景、边界条件和复杂度。这比按照教材顺序零散复习更有效。数据结构期末复习中循环队列的指针题是性价比很高的一类题代码量不大但边界条件密集只要把“牺牲一个存储单元”和“指针回绕”两个关键点掌握清楚就能拿分。建议今天就把第 4 章的数组版代码在本地跑一遍再用第 5 章的指针版做对比最后用第 8 章的检查清单自测一轮。