循环队列是 408 数据结构中队列部分最高频的考点之一而“初始时 front 和 rear 到底设为多少”这类问题几乎每年都能让一批考生在考场上卡住。2011 年 408 统考第 3 题就是从这个角度切入的题目没有直接考入队出队代码而是考初始化约定。看起来只是两个数字实际上背后牵涉到 front 和 rear 的指向语义、判空判满条件的设置以及“第一个进入队列的元素存放在 A[0]”这三个要素之间的联动。很多同学刷题时只记住了结论数组实现循环队列初始值 front 0rear 0。于是看到 2011 年这道题下意识就填了 0 和 0。这个答案在某些教材约定下是对的但在 2011 年统考真题的常见题面下并不对。问题不出在记性而出在没有区分“rear 指向队尾元素”和“rear 指向队尾元素的下一个位置”这两套完全不同的约定。这篇文章会把这道题真正讲透先建立循环队列初始化的分析框架再回到 2011 年真题推导标准答案然后补充一套相反约定的实现最后给出常见的失分点和排查清单。全程配有可运行的 C 代码适合正在复习 408 数据结构、准备期末考试或者只想把循环队列彻底搞清楚的读者。1. 循环队列的初始化不是随便填两个数1.1 循环队列要解决什么问题循环队列本质上是把一维数组的头尾在逻辑上接成一个环。普通顺序队列用数组存储时入队使 rear 后移出队使 front 后移反复操作后 rear 会走到数组末尾即使队列前面还有空闲位置也无法继续入队。这就是“假溢出”。循环队列的解决办法是让 rear 和 front 在到达数组末尾后回绕到数组开头回绕操作通过取模完成rear (rear 1) % MAXSIZE; front (front 1) % MAXSIZE;MAXSIZE 是数组长度数组有效下标是 0 到 MAXSIZE - 1。一旦下标超过最大值取模运算会把下标拉回起点整个数组因此被抽象成一个环形缓冲区。理解循环队列的关键不是背公式而是想清楚两个问题front 和 rear 分别指向什么队列为空时这两个指针的初值如何配合别人队动作初值并不是随便填的两个数。它必须保证第一次入队时第一个元素恰好存到规定的位置后续每次入队出队时判空和判满条件仍然成立。1.2 三个要素指向语义、判空判满、入队顺序循环队列的初始化是一组约束条件的共同结果至少包含三个要素。第一front 和 rear 的指向语义。不同教材或题目里front 可能指向队头元素也可能指向队头元素的前一个位置rear 可能指向队尾元素也可能指向队尾元素的下一个位置。指向语义一旦变了初始值、入队顺序和判空判满条件会全部跟着变。第二判空判满方式。常见的有三种牺牲一个存储单元、设置 count 计数器、设置 tag 标志位。每种方式对“front 和 rear 取什么值代表空或满”的定义都不同。第三入队时先移动 rear 再写入还是先写入再移动 rear。这个执行顺序决定了 rear 的初始值必须是哪个数。三者必须放在一起推导不能拆开记忆。很多考研资料习惯于直接给出“front rear 0判满条件是 (rear 1) % MAXSIZE front”这套组合但这只是若干种设计中的一种。2011 年真题考的是另一种组合。1.3 不同教材的“默认值”不一样做题必须先对齐约定考研复习时最常见的冲突来自不同教材使用了不同的循环队列实现。严蔚敏《数据结构》C 语言版中循环队列采用牺牲一个存储单元的方式初值通常是 front rear 0队空条件为 front rear队满条件为 (rear 1) % MAXSIZE front。部分习题册为了减少空间浪费使用 size 计数器初值也可能是 front rear 0。2011 年统考真题中题目单独说明了 front 和 rear 的指向语义并要求第一个入队元素存在 A[0]此时初值就不是简单的 0 和 0。做题时第一件事不是套公式而是先圈出题目里“front 指向哪里”“rear 指向哪里”这句话。没有这句话讨论初值就没有确定前提。2. 2011 年 408 第 3 题真题从哪个角度考初值2.1 常见题面与选项2011 年统考第 3 题在王道、天勤等主流辅导资料中的常见版本如下已知循环队列存储在一维数组 A[0..n-1] 中且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空且要求第一个进入队列的元素存储在 A[0] 处则初始时 front 和 rear 的值分别是 A. front 0rear 0 B. front 0rear n - 1 C. front n - 1rear 0 D. front n - 1rear n - 1这道题的标准答案在常见资料中为 B即 front 0rear n - 1。为什么不是 A因为题面写得很明确队列非空时front 指向队头元素rear 指向队尾元素。这句话是整个题目的关键前提。注意如果你手里的题目版本写的是“rear 指向队尾元素的下一个位置”那么答案会变成 front 0rear 0。做题时不要先入为主一定以题面给出的指向语义为准。2.2 拆解题目给出的三个前提这道题一共给了三个限制条件缺一个都会得出不同答案。第一个前提队列非空时front 指向队头元素。这意味着队列为空时front 虽然没有“真正”指向有效元素但它必须提前停在“第一个队头元素将要出现的位置”。只有这样才能保证第一个元素入队后front 不需要移动就恰好指向它。第二个前提队列非空时rear 指向队尾元素。第一个入队的元素既是队头也是队尾所以第一个元素入队完成后rear 必须指向这个元素。第三个前提第一个进入队列的元素存储在 A[0] 处。这是最关键的落点它把前面两个抽象前提变成了具体下标。三个条件合在一起可以得到一个完整推导链条第一个元素存在 A[0]所以第一个队头元素下标是 0。front 指向队头元素因此 front 初始值应为 0它在第一个元素入队前后都不需要变。第一个元素也是队尾元素入队完成后 rear 应指向下标 0。入队动作通常写成 “rear 先加一再存入”因此 rear 的初值必须满足(rear 初值 1) % n 0。解得 rear 初值 n - 1。答案自然就是 front 0rear n - 1。2.3 正确解析front 0rear n - 1再拆细一点看 rear n - 1 的含义。n 是数组 A[0..n-1] 的长度n - 1 是合法下标的最后一个。在循环队列中A[0] 的前一个位置逻辑上就是 A[n-1]。第一个元素要写入 A[0]而入队动作又是“先移动 rear 再写入”于是 rear 必须从 A[0] 的前一个位置出发。A[0] 的前一个位置在环形逻辑中就是 A[n - 1]。入队第一个元素的过程如下初始front 0rear n - 1 入队 10 rear (n - 1 1) % n 0 data[0] 10 此时 front 0rear 0count 1这个过程中 front 没有移动但它仍然指向队头元素 A[0]。rear 通过一次回绕移动到 A[0]表示队尾元素也是 A[0]。这种状态下 front 和 rear 数值相等但队列是满的吗不队列只有一个元素不是空也不是满。这就是为什么在这种约定下不能用 front rear 判断空满必须引入 count 计数器。先入队后 front rear 的这种情况正好说明“front 和 rear 相等”不等于“队列为空”。真题考初始化本质上是考你能不能区分“两个指针数值相等”和“队列状态为空”这两件事。2.4 为什么很多考生会写成 0 和 0写 0 和 0 的同学通常是把“牺牲一个存储单元的循环队列”那套实现直接搬过来了。在那套实现里rear 指向队尾元素的下一位置初值 front rear 0 是标准写法判空也是 front rear。但 2011 年真题的前提完全不同题目明确说明“队列非空时 rear 指向队尾元素”。这个前提下rear 0 意味着第一个元素入队后rear 如果还是 0就无法表示“队尾元素是 A[0]”。除非你换一种入队顺序先写入 data[0]再移动 rear这样 rear 从 0 出发写完后变成 1也能让第一个元素落在 A[0]。但问题来了这道题的常规范式是“先移动 rear 再写入”。两者执行顺序不同rear 初值也不同。做题时最容易踩的坑就是没有确认题目采用的入队顺序只记住了“循环队列初值 0,0”这个结论。结论本身没错但它属于另一套约定。把约定和题目互换答案就错了。3. rear 指向队尾元素下一个位置时初值为什么是 0 和 03.1 这套约定常配合“牺牲一个存储单元”如果题目改成这样front 指向队头元素rear 指向队尾元素的下一个位置最多使用 n - 1 个存储单元那么初始值才是最常见的 front rear 0。这套约定的核心是“牺牲一个存储单元”判满队空条件front rear 队满条件(rear 1) % MAXSIZE front为什么 rear 初始值要是 0因为第一个元素入队时按照“先写入 data[rear]再把 rear 后移”的顺序第一个元素直接写入 data[0]rear 从 0 变成 1。第一个元素成功落在 A[0]同时 rear 保持“指向队尾元素下一个位置”的语义。如果初值写成 rear MAXSIZE - 1第一次入队会先把元素写到 data[MAXSIZE - 1]而不是 A[0]。这在前面的真题前提下就不成立。把这套约定和真题约定放在一起差异会非常清楚对比项2011 真题约定牺牲一个存储单元约定front 指向队头元素队头元素rear 指向队尾元素队尾元素的下一个位置初始值front 0rear n - 1front 0rear 0队空判断count 0front rear队满判断count MAXSIZE(rear 1) % MAXSIZE front可用存储单元数MAXSIZEMAXSIZE - 1第一个元素入队后rear 0front 0rear 1front 0可以看到同样是“第一个元素入队”两套约定中 rear 的最终位置完全不同。这就是指向语义带来的连锁反应。3.2 最小可运行 C 实现下面这套实现完整展示了牺牲一个存储单元约定下的初始化、入队、出队、判空和判满。#include stdio.h #define MAXSIZE 6 typedef struct { int data[MAXSIZE]; int front; // 指向队头元素 int rear; // 指向队尾元素的下一个位置 } SqQueue; void InitQueue(SqQueue *Q) { Q-front 0; Q-rear 0; } int QueueEmpty(SqQueue Q) { return Q.front Q.rear; } int QueueFull(SqQueue Q) { return (Q.rear 1) % MAXSIZE Q.front; } int EnQueue(SqQueue *Q, int x) { if (QueueFull(*Q)) { return 0; } Q-data[Q-rear] x; Q-rear (Q-rear 1) % MAXSIZE; return 1; } int DeQueue(SqQueue *Q, int *x) { if (QueueEmpty(*Q)) { return 0; } *x Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; } int main() { SqQueue Q; int x; InitQueue(Q); EnQueue(Q, 10); printf(入队10后front%d, rear%d, empty%d, full%d\n, Q.front, Q.rear, QueueEmpty(Q), QueueFull(Q)); EnQueue(Q, 20); EnQueue(Q, 30); EnQueue(Q, 40); EnQueue(Q, 50); printf(再入队4个后empty%d, full%d\n, QueueEmpty(Q), QueueFull(Q)); DeQueue(Q, x); EnQueue(Q, 60); printf(出队%d后再入队60front%d, rear%d, empty%d, full%d\n, x, Q.front, Q.rear, QueueEmpty(Q), QueueFull(Q)); return 0; }代码里 MAXSIZE 6但队列最多只能存 5 个元素因为要留一个空位区分空和满。运行结果中第一次入队 10 之后 front 0、rear 1说明元素写在了 data[0]rear 指向 1 这个“下一位置”。当连续入队 5 个元素后 full 变为 1说明队满。随后出队一个并再入队 60front 和 rear 都发生了环形回绕这正好验证了取模运算的作用。3.3 与 2011 真题约定的对照表把两套约定直接对照比单独记哪一套都更容易形成长期记忆。可以这样理解2011 真题版本是“rear 指向有效元素需要 count 帮助判断空满”牺牲存储单元版本是“rear 指向无效空位留一格来区分空满”。两套实现的入队顺序也不一样2011 真题约定先移动 rear再写入 data[rear]。牺牲存储单元约定先写入 data[rear]再移动 rear。这个顺序不是随便定的而是由 rear 的指向语义决定的。rear 指向队尾元素那么入队时新元素要放在队尾之后所以必须先移动到新位置rear 指向队尾元素的下一个位置那么下一个位置就是空位可以直接写入写入后再把 rear 移动到下一个空位。理解了这个关系以后再遇到任何变体题目都不用背初始值现场推导即可。4. 用 C 代码验证两种初值设定的运行结果4.1 约定一front 指队头、rear 指队尾初值 0, n-1为了验证 2011 真题的推导下面实现一个带 count 计数器的版本。它允许数组全部存满同时解决“front rear 时可能是空也可能是满”的歧义。#include stdio.h #define MAXSIZE 6 typedef struct { int data[MAXSIZE]; int front; // 指向队头元素 int rear; // 指向队尾元素 int count; // 当前元素个数 } Queue; void InitQueue(Queue *Q) { Q-front 0; Q-rear MAXSIZE - 1; Q-count 0; } int EnQueue(Queue *Q, int x) { if (Q-count MAXSIZE) { return 0; } Q-rear (Q-rear 1) % MAXSIZE; Q-data[Q-rear] x; Q-count; return 1; } int DeQueue(Queue *Q, int *x) { if (Q-count 0) { return 0; } *x Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; Q-count--; return 1; } int main() { Queue Q; int x; InitQueue(Q); EnQueue(Q, 10); printf(入队10后front%d, rear%d, count%d, data[0]%d\n, Q.front, Q.rear, Q.count, Q.data[0]); EnQueue(Q, 20); DeQueue(Q, x); printf(再入队20后出队%dfront%d, rear%d, count%d\n, x, Q.front, Q.rear, Q.count); return 0; }这段代码的初始化正是 front 0rear MAXSIZE - 1。第一次入队 10 后rear 从 5 回绕到 0元素写入 data[0]count 变为 1。此时 front 仍然是 0恰好指向队头元素 A[0]验证了真题中的核心推导。出队一个元素后front 从 0 变成 1。此时 front 1rear 1count 1队列里还有一个元素 20。如果只用 front rear 判空这个状态会被误判为空队。count 的存在就是为了避免这个歧义。4.2 约定二rear 指队尾下一个位置初值 0, 0第 3 章已经给出了完整代码这里把它与约定一的输出做一个对应验证。在约定二下MAXSIZE 6最多存 5 个元素。第一次入队后 front 0rear 1。此时 data[0] 存放第一个元素rear 指向下一个空位 1。判断队满时必须满足 (rear 1) % MAXSIZE front。这两个实现放到同一个测试流程里能得到一致的行为第一个元素都存放在 data[0]入队出队都能正确回绕判空判满都不会把非空状态当成空。区别只在初始值和 rear 的语义运行状态约定一front 指队头、rear 指队尾约定二rear 指队尾下一位置初始化front 0rear 5front 0rear 0入队第一个元素 10rear 变为 0data[0] 10data[0] 10rear 变为 1队空判断count 0front rear队满判断count MAXSIZE(rear 1) % MAXSIZE front背后逻辑用计数器区分空满用预留空位区分空满4.3 验证检查点写完代码后不要只看它能不能编译运行要按以下检查点确认行为正确。检查点一第一个元素必须位于 data[0]。这是 2011 真题的硬性要求两种实现都满足。检查点二出队后 front 要指向下一个队头元素。如果数组发生回绕front 必须能从 MAXSIZE - 1 回绕到 0。检查点三判空判满结果不能出现歧义。用 front rear 判空的版本必须保证队列永远留一个空位用 count 的版本必须保证 count 在入队出队时同步增减。检查点四连续多次入队出队后front 和 rear 仍能回到合法范围。循环队列最常见的隐患是某一步忘记取模导致下标越界。这些验证在考场上没法用电脑跑但可以在草稿纸上手动模拟两三轮入队出队效果一样。5. 考研循环队列高频易错点与排查清单5.1 易错点一判满条件与初值组合错配很多人背下了“牺牲一个存储单元”的完整写法看到循环队列题目就默认初始值是 0 和 0判满是 (rear 1) % MAXSIZE front。但题目可能有两类前提题面说非空时 front 指向队头元素、rear 指向队尾元素。此时初值是 0 和 n - 1判空判满不能用 rear 和 front 相等来判断。题面说 rear 指向队尾元素的下一个位置。此时初值是 0 和 0判满才会用 (rear 1) % MAXSIZE front。解决方法是先做一道判断题题目里的 rear 指向有效元素还是指向空位错误现象错误原因处理建议看到循环队列直接填“front0, rear0”只背了牺牲存储单元版本先划出题面中 front/rear 的指向语义判满条件写成 rear front混淆了两种判空方式确认当前实现使用 count 还是预留空位初值写 rear n数组最大下标是 n - 1初值只可能落在 0..n-1 区间5.2 易错点二第一元素存 A[0] 只是结果不是入队方式真题要求“第一个进入队列的元素存储在 A[0]”。有些同学理解为入队时先移动 rear再把元素写入 rear 的位置因此 rear 初值只要是 n - 1 就行front 无所谓。但 front 也有自己的约束因为在非空队列中 front 必须指向队头元素第一个元素入队后 front 必须指向 A[0]所以 front 初值也只能是 0。换句话说A[0] 同时决定了 front 和 rear 的初值A[0] 是第一个队头元素front 初值 0。A[0] 是第一个队尾元素入队后 rear 0在“先移动后写入”的顺序下rear 初值 n - 1。只注意 rear 而忽略 front会在后续出队时出错因为出队第一步要取 data[front]如果 front 初值不对第一个出队元素就不是 A[0]。5.3 易错点三数组长度 n 与最大下标 n - 1 混用数组 A[0..n-1] 的长度是 n最后一个元素下标是 n - 1。初值计算涉及取模时模数是 n不是 n - 1。例如 rear 初值写成 n第一次入队时 (n 1) % n 1元素会写到 data[1]而不是 data[0]直接违反题目要求。正确的是 (n - 1 1) % n 0。判断一个初值是否合法有一个非常快的办法代入第一次入队过程看结果有没有落到 data[0]。如果第一次入队后元素出现在 data[0]初值通常没有问题如果出现在其他位置说明初值选择有误。5.4 循环队列做题排查清单遇到循环队列选择题或手写题可以按这个顺序检查圈出题面中 front 和 rear 的指向语义确认“指向队头元素”“指向队尾元素”“指向队尾元素的下一个位置”“指向队头元素的前一个位置”是哪一种。确认入队顺序是“先移动 rear 再写入”还是“先写入再移动 rear”。根据第一个元素存放位置反推 rear 初值。根据第一个队头元素存放位置确认 front 初值。根据判空判满条件检验初值是否存在 front rear 却非空或非满的歧义。在草稿纸上模拟两次入队和两次出队验证回绕是否正确。这套排查清单不仅适用于 2011 年这道题也适用于循环队列这个考点下的大多数变体题目。6. 工程实现里的循环队列比考研版本更灵活6.1 为什么工程中不常用牺牲一个存储单元考研中牺牲一个存储单元是为了简洁只靠 front 和 rear 两个指针就能判断空满不需要额外字段。但它有一个明显缺点长度为 MAXSIZE 的数组只能存 MAXSIZE - 1 个元素空间利用率不是 100%。在工程里数组或内存资源往往不是单选题的边界条件更常见的需求是“能用满就用满”和“读写效率可控”。因此工程实现中更倾向于用一个单独字段记录元素个数或者用一个状态标志位区分空和满。count 计数器实现简单、空间利用率高但多了一个字段入队出队时都要同步维护。tag 标志位则通过“最后一次操作是入队还是出队”来区分 front rear 时的状态如果最后一次操作是入队说明是满最后一次是出队说明是空。6.2 工程中更常见的四种做法第一种是 count 计数器。结构体里加一个 int count入队加一出队减一。判空判满直接比较 count 和容量不依赖 front 和 rear 的相对位置使用最直观。第二种是 tag 标志位。初始 tag 0front rear 0。入队成功后 tag 1出队成功后 tag 0。当 front rear 时通过 tag 判断空满。它不浪费存储空间但每次入队出队都要额外维护一个标志位。第三种是掩码法。要求容量为 2 的幂例如 8、16、64通过 index (size - 1) 代替 index % size运算效率更高。类似 Linux 内核环形缓冲区 kfifo 的思路。这种实现适合对读写性能敏感的场景。第四种是直接使用语言或框架提供的队列结构。比如 C 中可以使用 std::queue但它的默认底层容器是 deque并不是严格的循环数组。如果要固定容量一般使用 boost::circular_buffer 或自己封装环形数组。工程实践中“用哪种方式”取决于容量是否固定、是否需要高并发、取模运算是否成为瓶颈以及是否需要利用全部存储空间。考研题目中那种“留一个空位判满”的方式胜在概念清晰工程适用性其实有限。注意生产环境中的队列还需要额外考虑线程安全、内存屏障、批量入队出队、容量动态扩容等问题。这些不只是考研层面关心的问题但它们恰恰说明数据结构底层机制越清楚工程实现越不容易踩坑。6.3 从真题到工程真正要掌握的能力2011 年这道真题表面上只考了两个初值实际上考的是建模能力给定一组约束能不能推导出一套自洽的实现方案。生产中的环形缓冲区设计也是同样的思路。当你面对一个固定大小的共享缓冲区时需要依次确定读指针和写指针分别代表什么。空间满和空分别如何判断。读写过程中如何保证不会覆盖未消费的数据。单生产者单消费者、多生产者多消费者分别需要什么同步手段。每一条都对应到循环队列初始化时的那套逻辑。只是工程中的“初值”可能变成一个内存地址、一个写偏移或者一个水位阈值。概念变了推导方式不变。因此复习 408 时不要只满足于记住“答案是 B”。真正有价值的是把这个推导过程变成你自己的思维模板任何循环队列问题先定义指针语义再定义状态判断最后反推初始值。这套模板既能解决考试题也能迁移到后续课程设计和实际开发中。7. 复习建议把“初值问题”变成“送分点”循环队列初值题是性价比很高的得分点。它不依赖复杂算法只依赖几个基础概念的正确组合。很多同学失分并不是不知道循环队列而是没有意识到“初始值不是背出来的是推出来的”。复习时建议做一个动作不看答案自己推导 2011 年第 3 题。只要能在三分钟内写清楚“front 为什么是 0rear 为什么是 n - 1”这个考点就算真正掌握了。再把同样方法用于其他变体比如把题面改成 “rear 指向队尾元素的下一个位置”初值如何变化。把题面改成 “front 指向队头元素的前一个位置”初值如何变化。在牺牲一个存储单元的基础上数组长度改为 n最多能存几个元素。每推导一个变体就把“指向语义、入队顺序、判空判满、初始值”四个要素列到一张表里。你会发现循环队列所有选择题都变得非常机械确定前提代入公式验证第一次入队结束。408 的复习时间很紧张但这种“一道题带出一类题”的总结方式效率远高于盲目刷题。下次遇到循环队列不要再问“初值该填 0 吗”而是问一句“题目里 rear 到底指向哪里”这个问题想清楚答案就已经出来了。