数组实现循环队列这是我这些年写代码时用得最多的数据结构之一尤其是做串口数据缓冲、日志采集和直播推流这类需要固定容量 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 rear2.1 经典 front rear 方案的尴尬教科书里最常见的实现是维护 front 和 rear 两个整数。front 指向队头元素rear 指向队尾的下一个位置。初始时两个都是 0。入队把元素写到 rearrear 后移出队把 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绝不看 frontrear。对比一下三种方案方案判空判满最大容量队头来源frontrear留空位frontrear(rear1)%mfrontm-1front 直接记录frontrearlengthlength0lengthmmfront 直接记录rearlengthlength0lengthmm(rear-lengthm)%m 推导第三种方案省一个字段还省了一个空位。缺点是每次出队和取队头要多做一次减法加取模但这是 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导致队列大小卡死。换成 rearlength 之后这类低级 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 减一不需要像 frontrear 方案那样显式让 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 2length 5rear - 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 0rear 0位置一致。入队一个元素后length 1rear 1还是对。但等队列出过队之后再入队两者就会错开。比如 MAX_SIZE 8入队 5 个出队 3 个此时 rear 5length 2下一个插入位置应该是 5而不是 2。所以写入位置永远看 rear不要看 length。length 只负责计数rear 才负责下标。我建议在命名上就更明确一点比如把 rear 命名为 writeIndex把 length 命名为 count能有效避免这类混淆。4.3 出队后旧数据残留造成调试幻觉使用 rearlength 方案时出队只执行 length--并没有把 q[front] 对应的数据清空。这本来没问题因为 length 已经表示这些位置不再属于逻辑队列。调试时如果你把整个 data 数组打印出来会看到队列已经空了但数组里还留着上一次的数据容易被误导以为队列没清干净。我建议在调试版本里把出队位置重置为 0q-data[front] 0;不过这只是辅助手段。正式发布代码里做这一步会白白增加一次写内存操作在性能敏感场景不应该加。核心是逻辑上一定要用 length 判断而不是用“数组里某块有没有数据”来判断。4.4 多线程读写循环队列的注意事项数组循环队列常被用在生产者消费者场景但这不是说任意实现直接就能多线程使用。如果在多个线程里同时调用 enqueue 或 dequeue必须加锁或者使用原子操作。单生产者单消费者场景下有一种无锁环形缓冲区做法生产者和消费者各自维护自己的读写位置配合内存屏障实现。但如果你使用 rearlength 方案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 的配合在 rearlength 方案里反而简单因为你不需要维护 front旧队列线性化后直接写新数组即可。如果使用 frontrear 方案扩容后 front 还要额外改成 0容易漏。5.3 扩展二从 int 队列到对象队列代码模板里的 data 是 int 数组。实际项目中队列里放的可能是一个结构体、一个指针甚至一个对象。两种处理思路一种是在数组里直接存对象副本入队时做拷贝另一种是存指针或引用对象本身在堆上管理。用数组存对象副本的问题在于复制开销和生命周期管理。C 语言里结构体可以直接赋值但如果有指针成员浅拷贝容易带来悬垂指针。用指针数组更常见int* 数组或者 void* 数组入队时只搬运地址出队时取回地址。面试题里经常提到的“指针数组”在这里就有了实际用途它本质上就是一组地址的线性容器正适合做对象缓冲。不过我不建议在面向对象语言里这样折磨自己。现代语言直接用现成队列或者 ring buffer 库就行自己实现循环队列的意义主要在学习、笔试面试和底层嵌入式场景。5.4 扩展三循环队列和双端队列的区别数组循环队列只支持一端入队、另一端出队是 FIFO。如果想两端都能插入删除那是双端队列需要另外维护 front 和 back 两个索引。rearlength 方案并不适合直接改造成双端队列因为它的单 rear 设计假设了入队只发生在尾端。我在 5.1 提到的滑动窗口其实也可以用双端队列实现而且更灵活因为它还需要从队尾丢弃过期数据。但双端队列的数组实现通常要判断左移右移的边界坑比 FIFO 多。如果业务只需要 FIFO就老老实实写循环队列不要为了“以后可能用到”提前引入双端队列的复杂度。最后分享一个我自己的调试习惯。每次写完循环队列我首先会做一个容量刚好为 1 的验证因为容量为 1 时空和满的转换是最容易出错的。然后我会把 enqueue 成功、失败、dequeue 成功、失败各打一行日志日志里同时打印 expected length 和 rear 的值这样任何一次下标错了都能立刻定位。数组实现循环队列不难难的是每次在边界上都不出错。熟记那个非负取模公式记住 length 是唯一的权威状态这套代码基本就能一次写对。