企业官网建设流程全解析

数组实现循环队列，这是我这些年写代码时用得最多的数据结构之一，尤其是做串口数据缓冲、日志采集和直播推流这类需要固定容量 FIFO 的场景。很多教材喜欢用 front 和 rear 两个指针，再留一个空位来区分队空队满，说实话能用，但总觉得别扭。我更习惯维护 rear 和 length 两个整数，一个数组就能转起来，没有链表节点分配，也没有动态扩容的焦虑。这篇文章会把我在写这套东西时怎么设计下标、怎么写入队出队、踩过哪些边界坑，一次讲清楚。无论你是刚在数据结构课上被指针和多维数组折磨的新手，还是要在嵌入式设备里实现环形缓冲的工程师，都可以直接参考。

1. 为什么循环队列要基于数组实现

1.1 数组的连续内存和固定容量是天然的选择

队列是一个先进先出的线性结构。实现队列可以选择链表也可以选择数组。我在实际项目里优先选择数组，理由很直接：数组在内存中是连续的一段空间，访问任意一个下标都是 O(1)，而且 CPU 缓存对连续内存的预取非常友好。链表每次入队都要分配节点，出队要释放节点，在高频收包或者日志写入的场景下，分配器的压力会肉眼可见地拉高延迟。

当然，数组方案的前提是容量上限事先能估出来。比如串口协议一个包不超过 1KB，要缓冲 64 个包，那 MAX_SIZE 给到 64 就够了。如果上限不确定，我会在外部再做一层动态扩容，这个问题在第 5 节专门说。固定容量不是什么缺点，反而是可控性的来源：内存提前分配好，队列不会因为某个瞬间的流量尖峰而无限增长，这一点在嵌入式环境中非常重要。

1.2 取模运算把“顺序队列”变成“循环队列”

顺序队列最尴尬的问题是假溢出。假设数组长度是 8，你在末尾连续入队 8 个元素，然后从队头出队 4 个，数组前面有一半空位，但 rear 已经指向数组末尾，想继续入队却走不进去。如果不做任何处理，明明有空间却入不了队，这就是假溢出。

循环队列的核心思路是用一个取模运算把数组的首尾拼接起来。入队时不再写 q[rear] 然后 rear++，而是写 q[rear] 后执行 rear = (rear + 1) % MAX_SIZE。当 rear 走到 7 时，再入队一个元素，(7 + 1) % 8 = 0，插入位置会回到 0，数组就变成了一个环。你可以把它想象成环形操场：7 号位置跑到头之后，回身一步又能看到 0 号位置。

这里的关键点是，数组的下标天然支持整数运算，所以取模非常自然。如果用链表实现循环队列，你反而需要额外的指针操作；数组实现循环队列的本质就是“下标取模”，代码简短，边界也集中在取模这一处，排查起来目标很明确。

2. 核心设计思路：rear + length 而不是 front + rear

2.1 经典 front + rear 方案的尴尬

教科书里最常见的实现是维护 front 和 rear 两个整数。front 指向队头元素，rear 指向队尾的下一个位置。初始时两个都是 0。入队把元素写到 rear，rear 后移；出队把 front 后移。问题来了：front 和 rear 相等时，它到底是空还是满？

很多数据结构教材的解法是“牺牲一个存储单元”，也就是最多存 MAX_SIZE - 1 个元素。判满条件是 (rear + 1) % MAX_SIZE == front。一个 1024 容量的队列，实际只能放 1023 个元素。对于嵌入式里精打细算的人来说，这 1 格浪费说大不大，但既然有更好的方案，没必要守着这个习惯。

另一个解法是额外增加一个 bool 变量或者计数器。如果增加计数器，那 front 和 rear 还要不要同时维护？我发现只维护 rear 和 length，比维护 front、rear、length 三件套更简洁。因为 front 不直接存储，而是由 rear 和 length 推导，这样状态变量少一个，很多“三个变量配合不一致”的 Bug 就没机会发生。

2.2 从 rear 和 length 推导队头

在这种方案里，rear 始终指向“下一个元素写入的位置”，length 表示队列当前元素个数。空队列 length == 0，满队列 length == MAX_SIZE，两个条件非常明确。

队头的位置不是直接存的，而是用公式算：

front = (rear - length + MAX_SIZE) % MAX_SIZE

这个公式可以这么理解：后进队的元素依次写在 rear 往前的 length 个位置上。如果队列是满的，length == MAX_SIZE，代入公式得到 front == rear，这不代表空，而是满。所以我在代码里判空判满只看 length，绝不看 front==rear。

对比一下三种方案：

第三种方案省一个字段，还省了一个空位。缺点是每次出队和取队头要多做一次减法加取模，但这是 O(1) 的整数运算，在绝大多数场景下可以忽略不计。

2.3 为什么这个设计更适合数组实现

还有一个现实层面的原因：业务代码里经常要查询“队列里现在还有多少条数据”。如果只有 front 和 rear，你需要写 (rear - front + MAX_SIZE) % MAX_SIZE。如果用了 rear + length，直接读 length 字段就行，不但语义清楚，还少一次计算。

另外，数组实现最怕的是下标写乱。维护 front、rear、length 三个变量时，入队要改 rear 和 length，出队要改 front 和 length，稍不留神就有一个变量忘记更新。只用 rear 和 length，入队改 rear 和 length，出队只改 length，状态迁移的路径更短。我在重构老代码时，经常看到有人把 front 改了却忘了 length，导致队列大小卡死。换成 rear+length 之后，这类低级 Bug 明显变少了。

所以从“可维护性”和“内存利用率”两个角度看，rear + length 都是数组实现循环队列时值得优先选择的方案。

3. 完整实现：C语言版循环队列模板

3.1 结构定义与初始化

直接给一个能跑的 C 语言实现。这里用定长数组，MAX_SIZE 先取 8 方便测试。

#include <stdio.h> #define MAX_SIZE 8 typedef struct { int data[MAX_SIZE]; int rear; int length; } LoopQueue; void initQueue(LoopQueue *q) { q->rear = 0; q->length = 0; }

初始化很简单，rear 从 0 开始，length 为 0。可能有人会问，为什么 rear 不放 -1 之类的值？因为 rear 的语义是“下一个写入位置”，初始时下一个写入位置自然是 0。把 rear 设成 -1 反而要在入队时先判断再移动，没必要。

这里需要强调 capacity 和 length 的区别。MAX_SIZE 是数组物理容量，length 是当前逻辑元素个数。物理容量在队列生命周期内不变，逻辑长度只在入队和出队时变化。把这两个概念分开，后面的代码就不会写偏。

3.2 入队、出队、取队头、遍历的代码细节

入队函数：

int enqueue(LoopQueue *q, int value) { if (q->length == MAX_SIZE) { return 0; } q->data[q->rear] = value; q->rear = (q->rear + 1) % MAX_SIZE; q->length++; return 1; }

先判满，满了返回 0。不空时先写入 rear 位置，再让 rear 循环前进一格。最后 length 加一。注意顺序：rear 必须先保存再后移，如果先移动 rear 再写入，就会写到下一个位置去。

出队函数：

int dequeue(LoopQueue *q, int *value) { if (q->length == 0) { return 0; } int front = (q->rear - q->length + MAX_SIZE) % MAX_SIZE; *value = q->data[front]; q->length--; return 1; }

出队时先判断空。然后用公式算出队头下标，把值通过指针带出去。最后 length 减一，不需要像 front+rear 方案那样显式让 front 后移。因为 length 减一后，下一次再按公式计算队头时，结果自然就向后移动了一个位置。这是这个方案的精髓：出队操作对 rear 没有影响，只收缩逻辑范围。

取队头不弹出：

int peek(LoopQueue *q, int *value) { if (q->length == 0) { return 0; } int front = (q->rear - q->length + MAX_SIZE) % MAX_SIZE; *value = q->data[front]; return 1; }

遍历整个队列时，从队头开始，按逻辑顺序访问 length 个元素：

void printQueue(LoopQueue *q) { for (int i = 0; i < q->length; i++) { int idx = (q->rear - q->length + i + MAX_SIZE) % MAX_SIZE; printf("%d ", q->data[idx]); } printf("\n"); }

这里的 idx 公式本质上就是 (front + i) % MAX_SIZE。因为 front = (rear - length + MAX_SIZE) % MAX_SIZE，所以 front 加上 i 之后再取模就得到第 i 个元素的下标。写代码时直接把 rear - length + i + MAX_SIZE 放在一起取模，避免多加一个 front 变量。

3.3 关键参数计算：队头下标、剩余容量、负数取模

队头公式的字面理解：在环形数组中，rear 是下一个插入点，那最后一个入队的元素在 rear - 1 的位置。既然队列中有 length 个元素，最老的那个元素就往前推 length 格，即 rear - length。再加上 MAX_SIZE 是为了防止得到负数。

C 语言里，负数对正数取模的结果是负数。例如 -1 % 8 在 C99 标准下结果是 -1，不是 7。如果你直接写 (q->rear - q->length) % MAX_SIZE，当 rear 小于 length 时，下标就是负数，访问 q[-1] 直接越界。加上 MAX_SIZE 再进行取模，就能把负数修正成 [0, MAX_SIZE) 范围内的有效下标。

剩余容量是 MAX_SIZE - q->length。如果队列已满，入队返回 0；如果还想用覆盖策略，可以改成先出队再入队，但那就不是严格意义上的循环队列，而是滑动窗口或环形缓冲区，语义上要区分开。

完整测试代码可以这样组织：

int main(void) { LoopQueue q; initQueue(&q); for (int i = 1; i <= 10; i++) { if (enqueue(&q, i)) { printf("enqueue %d ok, length=%d\n", i, q.length); } else { printf("enqueue %d failed, queue full\n", i); } } int v; while (dequeue(&q, &v)) { printf("dequeue %d\n", v); } return 0; }

这个测试故意让 10 个元素入队，模拟队列满了之后的拒收行为，应该稳定输出前 8 个成功、后 2 个失败。我建议读者改一改 MAX_SIZE，分别测试 1、2、3、8 这些边界容量，很多隐藏问题马上就会暴露。

4. 常见问题与调试实录

4.1 取模负数导致数组越界

这是我第一次写这个方案时踩的坑。出队时如果直接写：

int front = (q->rear - q->length) % MAX_SIZE;

接着 q->data[front] 就崩了。因为当 rear = 2，length = 5，rear - length = -3，-3 % 8 的结果在 C 语言里是 -3，下标直接变成负数。

解决办法就是前面说的，把被除数的负数先修正：

int front = (q->rear - q->length + MAX_SIZE) % MAX_SIZE;

这里有一个细节：为什么加一次 MAX_SIZE 就够？因为 rear 和 length 的取值范围都在 [0, MAX_SIZE]，它们差的最小值是 -(MAX_SIZE)，加一个 MAX_SIZE 后最小值是 0，最大值小于 2 * MAX_SIZE，再取模一次就能落到 [0, MAX_SIZE)。如果 rear 和 length 维护得正确，这个修正公式永远有效。

4.2 把 length 当成“最后入队位置”来用

入队时最容易犯的低级错误是：

q->data[q->length] = value;

这个写法在初始状态是对的，因为 length = 0，rear = 0，位置一致。入队一个元素后，length = 1，rear = 1，还是对。但等队列出过队之后再入队，两者就会错开。比如 MAX_SIZE = 8，入队 5 个，出队 3 个，此时 rear = 5，length = 2，下一个插入位置应该是 5，而不是 2。

所以，写入位置永远看 rear，不要看 length。length 只负责计数，rear 才负责下标。我建议在命名上就更明确一点，比如把 rear 命名为 writeIndex，把 length 命名为 count，能有效避免这类混淆。

4.3 出队后旧数据残留造成调试幻觉

使用 rear+length 方案时，出队只执行 length--，并没有把 q[front] 对应的数据清空。这本来没问题，因为 length 已经表示这些位置不再属于逻辑队列。调试时如果你把整个 data 数组打印出来，会看到队列已经空了，但数组里还留着上一次的数据，容易被误导，以为队列没清干净。

我建议在调试版本里把出队位置重置为 0：

q->data[front] = 0;

不过这只是辅助手段。正式发布代码里做这一步会白白增加一次写内存操作，在性能敏感场景不应该加。核心是：逻辑上一定要用 length 判断，而不是用“数组里某块有没有数据”来判断。

4.4 多线程读写循环队列的注意事项

数组循环队列常被用在生产者消费者场景，但这不是说任意实现直接就能多线程使用。如果在多个线程里同时调用 enqueue 或 dequeue，必须加锁，或者使用原子操作。

单生产者单消费者场景下，有一种无锁环形缓冲区做法：生产者和消费者各自维护自己的读写位置，配合内存屏障实现。但如果你使用 rear+length 方案，length 会被生产者和消费者同时修改，这就产生了竞争，不能简单当成无锁队列。要无锁，通常用 readIndex/writeIndex 分离的模型，而不是共享 length。

我的建议是：先用互斥锁把 enqueue 和 dequeue 保护起来，保证正确性；性能测出来确实有瓶颈，再考虑无锁优化。不要一上来就搞无锁，数据竞争导致的问题往往非常难查。

5. 应用场景与扩展思路

5.1 我实际用到的几个场景

数组实现循环队列最常见的应用是环形缓冲区。做嵌入式串口驱动时，接收中断会把一字节一字节的数据塞进队列，主循环再从队列里取包解析。中断上下文和主循环上下文之间需要低延迟的读写，数组循环队列比链表好在没有动态内存分配，不会在中断里触发 malloc，也就不会引入不可控的阻塞。

日志系统也很适合。业务线程把日志记录入队，专门的日志线程出队写文件或网络。这样即使在页面上疯狂操作，业务线程也不会因为磁盘 IO 卡住。队列容量固定，最坏情况是丢日志，却不会拖垮整个进程。这里我会把满队列的策略设计成“丢弃新日志并计数”，而不是阻塞业务线程，背后就是用了循环队列的固定容量特性。

还有滑动窗口，比如统计过去一秒钟内进站的流量。你可以把每个请求到达的时间戳入队，窗口长度就是队列容量；新时间戳入队时，如果队头时间戳已经超出窗口，就不断出队。循环队列天然支持这种“先进先出 + 定长窗口”的结构。

5.2 扩展一：给循环队列加动态扩容

定长数组虽然好，但业务容量预估错了怎么办？很多编程范型里直接用“创建新数组，拷贝旧队列”。数组循环队列的扩容有一个细节：不能直接 realloc 整个 data，因为逻辑顺序在物理数组里是环形排列的，可能从 3 号位置开始延续到 2 号位置。

扩容步骤：先分配 newCapacity 的新数组，然后从队头开始，按逻辑顺序把 length 个元素复制到新数组的 0 到 length-1 位置。最后把 rear 更新为 length（因为下一个插入位置正好在新数组的 length 位置），capacity 更新为 newCapacity。这个过程 O(n)，但扩容次数很少，摊下来成本可以接受。

一个注意事项：扩容时 front 和 length 的配合在 rear+length 方案里反而简单，因为你不需要维护 front，旧队列线性化后直接写新数组即可。如果使用 front+rear 方案，扩容后 front 还要额外改成 0，容易漏。

5.3 扩展二：从 int 队列到对象队列

代码模板里的 data 是 int 数组。实际项目中队列里放的可能是一个结构体、一个指针甚至一个对象。两种处理思路：一种是在数组里直接存对象副本，入队时做拷贝；另一种是存指针或引用，对象本身在堆上管理。

用数组存对象副本的问题在于复制开销和生命周期管理。C 语言里结构体可以直接赋值，但如果有指针成员，浅拷贝容易带来悬垂指针。用指针数组更常见：int* 数组或者 void* 数组，入队时只搬运地址，出队时取回地址。面试题里经常提到的“指针数组”在这里就有了实际用途：它本质上就是一组地址的线性容器，正适合做对象缓冲。

不过我不建议在面向对象语言里这样折磨自己。现代语言直接用现成队列或者 ring buffer 库就行，自己实现循环队列的意义主要在学习、笔试面试和底层嵌入式场景。

5.4 扩展三：循环队列和双端队列的区别

数组循环队列只支持一端入队、另一端出队，是 FIFO。如果想两端都能插入删除，那是双端队列，需要另外维护 front 和 back 两个索引。rear+length 方案并不适合直接改造成双端队列，因为它的单 rear 设计假设了入队只发生在尾端。

我在 5.1 提到的滑动窗口其实也可以用双端队列实现，而且更灵活，因为它还需要从队尾丢弃过期数据。但双端队列的数组实现通常要判断左移右移的边界，坑比 FIFO 多。如果业务只需要 FIFO，就老老实实写循环队列，不要为了“以后可能用到”提前引入双端队列的复杂度。

最后分享一个我自己的调试习惯。每次写完循环队列，我首先会做一个容量刚好为 1 的验证，因为容量为 1 时，空和满的转换是最容易出错的。然后我会把 enqueue 成功、失败、dequeue 成功、失败各打一行日志，日志里同时打印 expected length 和 rear 的值，这样任何一次下标错了都能立刻定位。数组实现循环队列不难，难的是每次在边界上都不出错。熟记那个非负取模公式，记住 length 是唯一的权威状态，这套代码基本就能一次写对。