很多朋友学到队列这一节时都会有一个疑问队列用链表实现不是更自然吗为什么还要搞一个“循环队列”其实在实际生产环境里数组版本的循环队列恰恰是更常见、更贴近底层的方案。像消息中间件的环形缓冲区、串口接收缓存、音视频解码的帧缓冲底层基本都是“数组 头尾指针”的循环结构。我最早是在一个嵌入式项目里接触这种结构的串口数据是一帧一帧进来的如果用普通队列前面数据还没取走后面数据就把空间占满了整个缓冲很快就“假溢出”了。后来换成数组实现循环队列问题一下子解决。这篇文章就把我从原理、设计到代码实现的完整思路整理出来包括踩过的坑和排查方法。内容主要围绕“rear 和 length”这个经典方案展开也顺带讲清楚它和“预留一格”方案的区别。适合正在学数据结构的初学者也适合想在项目里自己封装一个环形缓冲区的工程师参考。1. 从“假溢出”说起为什么队列要循环起来1.1 顺序队列的致命短板最基本的队列如果直接用数组做头指针 front 指向队头元素尾指针 rear 指向队尾元素的下一个位置。入队时把元素放到 rear 位置rear 往后移出队时 front 往后移。写成代码非常简单但真正跑起来你就会发现一个问题出队过的位置永远空着因为 front 只会往后走前面的空间即使被释放了rear 也回不去。举个例子容量是 5 的数组连续入队 5 个元素后 rear 指向 5然后出队 4 个元素front 指向 4。这时候队列其实只有一个元素数组前面 4 个位置都空着但 rear 已经到末尾了再入队就越界。你可能会说那我把 front 和 rear 都往前挪一下不就行了这在偶尔出队一次的场合还行但在高频读写场景里每次都要搬移数据性能完全不能看。这个现象就是顺序队列的“假溢出”。判断逻辑看起来没有越界数组里明明还有空位却因为指针只能单向运动导致空间用不上。循环队列就是针对这个局面设计的把数组看成一个环形rear 走到尾部之后再绕回头部空出来的位置自然就能被复用。1.2 数组实现循环队列的应用场景很多人觉得循环队列只是一个考试题实际工作里可能用不上。这个想法其实低估了它。我自己用过的场景就至少有三类第一类是串口或者网络数据缓冲。数据到达时间不确定处理线程又不可能一直阻塞在读取端口上这时候就需要一个缓冲区把先到的数据存起来稍后再处理。缓冲区如果不够大稍微有波动就会丢数据用循环队列就能以最小开销实现连续读写。第二类是生产者消费者模型。生产者和消费者的速度往往不一致中间必须有一个“蓄水池”。循环队列天然适合这种场景尤其是单生产者单消费者的情况配合原子操作甚至可以做到无锁。第三类是算法题和面试题里的高频题。比如“设计一个支持取最小值的队列”“滑动窗口最大值”这些题底层很多都跟循环队列相关。更关键的是有的同学把二维数组、指针数组、动态数组背得滚瓜烂熟但真到用数组解决一个具体工程问题时反而无从下手循环队列就是最好的练手场景之一。2. 设计取舍rear length 的来历2.1 经典方案对比数组实现循环队列最核心的问题就一个怎么判断队列到底是空还是满。因为如果用 front 和 rear 两个指针循环之后空队列时 front rear满队列时 front 也等于 rear因为绕了一圈追上了。不引入额外信息这两个状态根本无法区分。网上最常见的做法是“预留一格空间”。也就是让数组容量为 n但队列最多只能存 n - 1 个元素。判空条件仍然是 front rear判满条件变成 (rear 1) % capacity front。这个方案的好处是简单直观不需要额外的计数器缺点是浪费一个存储位而且当 capacity 为 1 的时候逻辑会比较别扭。另一种做法就是我这篇文章要重点讲的“rear length”方案。rear 指向队尾元素的下一个位置length 记录当前队列元素个数。判空条件是 length 0判满是 length capacity。这个方案不浪费空间判空判满逻辑也极其朴素不用纠结指针相等的问题。两者对比下来差别很明确我用个表格直观展示一下判断项预留一格rear length最大可用容量capacity - 1capacity判空条件front rearlength 0判满条件(rear 1) % capacity frontlength capacity额外存储无一个 length 变量出队后维护移动 front移动 frontlength--入队后维护移动 rear移动 rearlength2.2 为什么我推荐 length 计数先说结论如果不是对内存极度敏感的场景我建议优先用 rear length。原因有三点。第一逻辑直接。判空判满不再依赖指针关系读代码的人不需要在脑子里把“预留一格”的循环过程画一遍直接看 length 就行。第二容量利用完整。很多场景下缓冲区的大小是固定的比如 1024 字节用预留一格方案实际能用 1023 字节虽然只差一字节但在嵌入式这种抠内存的地方省下任何一个字节都是有意义的。第三扩展性更好。后面如果要扩容或者统计队列中还有多少剩余空间有 length 就能一步算出 capacity - length预留一格方案还得额外再推一圈。当然 length 方案也有代价就是多维护一个计数器。入队、出队都要同步修改 length如果操作频率是每秒数千万次这个计数器更新会有轻微开销。但在绝大多数业务场景里这点开销完全可以忽略反而是逻辑清晰带来的可维护性收益更大。我在实际项目里遇到过一次很有意思的情况设计文档里用的就是预留一格方案但后来需求变更缓冲区要从 64 字节改成可配置大小上限是 1000结果预留一格方案每个缓冲区都少存一个元素累计起来浪费不小。最后干脆改成 length 计数配置多少就存多少省了很多解释成本。3. 完整代码实现与逐段解析3.1 数据结构定义与初始化我用 C 语言写一个精简版本支持创建、销毁、入队、出队、判空、判满。数据结构定义如下#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; // 底层存储动态数组 int capacity; // 缓冲区总容量 int front; // 队头下标 int rear; // 队尾下标指向下一个写入位置 int length; // 当前元素个数 } CircularQueue;这里 front 指向队头元素的下标rear 指向队尾元素下一个位置的下标。data 是一个动态分配的数组capacity 表示数组长度length 表示队列中实际存放的元素个数。初始化函数也很简单CircularQueue* createQueue(int cap) { CircularQueue *q (CircularQueue*)malloc(sizeof(CircularQueue)); q-data (int*)malloc(sizeof(int) * cap); q-capacity cap; q-front 0; q-rear 0; q-length 0; return q; } void destroyQueue(CircularQueue *q) { if (!q) return; free(q-data); free(q); }初始化时 front 和 rear 都指向 0length 为 0此时队列为空。之所以把 data 做成动态数组而不是定长数组是为了让容量可以在运行时决定这样同一个结构既可以装小容量的串口缓冲也可以装大容量的网络缓冲。3.2 入队、出队与判空判满判空和判满是整个设计里最简单的部分bool isEmpty(CircularQueue *q) { return q-length 0; } bool isFull(CircularQueue *q) { return q-length q-capacity; }没有指针比较没有取模没有任何绕圈的理解成本。接下来是入队bool enqueue(CircularQueue *q, int value) { if (isFull(q)) { return false; } q-data[q-rear] value; q-rear (q-rear 1) % q-capacity; q-length; return true; }入队时先把元素写入 rear 指向的位置然后把 rear 向后移动一位。这个“向后移动”在环形数组里要用取模实现到达数组末尾后回到头部。最后 length 加一。出队也不复杂bool dequeue(CircularQueue *q, int *value) { if (isEmpty(q)) { return false; } *value q-data[q-front]; q-front (q-front 1) % q-capacity; q-length--; return true; }出队时先取出 front 指向的元素再把 front 向后移动一位length 减一。如果只是想知道队头元素而不弹出可以再加一个 peek 函数直接返回 q-data[q-front]。这套代码用起来的感觉就是“丝滑”每个操作的时间复杂度都是 O(1)而且没有数据搬移没有复杂的边界判断第一次看代码的人也能快速理解。3.3 关于取模运算的边界细节取模看起来是个很基础的操作真用起来还是有很多细节值得注意。最容易被忽略的一点是取模的对象是 capacity 而不是 capacity - 1。因为 rear 可能已经等于 capacity - 1到达数组最后一个位置这时候 (rear 1) % capacity 的结果是 0正好回到数组开头。如果错误地对 capacity - 1 取模就会让下标永远走不到最后一个位置白白浪费一个空间。另一个细节是 front 和 rear 的移动方向。在循环队列里front 和 rear 都是朝“下标增大”的方向移动到尾部再从头部绕回来不存在向前移动的情形。这个方向一旦搞反队列逻辑会立刻乱掉而且排查起来很难发现。我见过一个很隐蔽的 bug出队时 front 写成了 (front - 1 capacity) % capacity看起来像模像样结果出队顺序完全反了变成了从队尾出队整个队列的顺序被颠倒。还有一点如果队列的容量不是 2 的幂取模运算在 CPU 层面会比位运算慢一些。对于极致性能要求可以把 capacity 设为 2 的幂然后用 (rear 1) (capacity - 1) 代替取模这算是一个进阶优化。但基础版本还是用取模语义清晰不易出错。4. 实操中容易踩的坑4.1 误区把 front rear 当作判空这个是写循环队列最容易踩的坑几乎每个初学者都会踩一次。原因也很简单前面学普通队列时front rear 确实代表空队列但是在循环队列中满队列时 front 也可能等于 rear。如果用 rear length 方案满队列时 length capacityrear 在绕一圈之后正好追上 front这个时候 front rear但队列是满的。如果代码里仍然用 front rear 判空满状态下调用 isEmpty 会返回真进而导致入队覆盖旧数据或者出队读空数据。我在代码评审里看到过一个很典型的写法明明定义了 length 字段但判空还是写 if (front rear)。问作者为什么他说这样更快。实际上这不是快慢的问题是语义错误的问题。既然选了 length 方案就统一用 length 判空判满不要在两种方案之间横跳横跳的结果往往是 bug。4.2 容量设置与溢出循环队列的容量设置得过大会浪费内存过小会导致频繁溢出。这个问题在实践中往往比想象中复杂。比如串口缓冲假设串口波特率 115200每秒大约接收 11520 字节如果处理线程每隔 10 毫秒读取一次缓冲那么这 10 毫秒内最多积累 115 字节左右。缓冲区设置为 256 字节看起来已经够用但万一某个中断处理函数耗时超过预期或者系统频繁调度其他线程导致处理延迟缓冲区仍然可能溢出。这种时候入队函数返回 false数据就直接丢了。针对这种情况我一般会在 createQueue 阶段就预留一定的余量通常是理论峰值的 2 到 3 倍。另外enqueue 返回 false 时不要直接忽略至少要留一个日志或者计数器记录丢了多少数据这样出了问题才能定位。很多人忽略这个细节直到数据不完整才回头查很难排查。4.3 扩容时 front 和 rear 的迁移前面说 length 方案扩容方便具体实现还是有讲究的。如果直接把底层数组 realloc 到更大的空间front 和 rear 在逻辑上是循环的原数组的“环”被截断后数据顺序就会错乱。简单说直接 realloc 是错的。正确的做法是先分配一个新的数组然后按照从 front 到 rear 的循环顺序依次把所有元素搬到新数组搬完后让 front 0rear length。这里的关键在于搬移顺序必须从 front 开始而不是从下标 0 开始。我见过有人图省事直接从下标 0 遍历 data 数组拷贝结果队列顺序被打乱因为环形队列里下标 0 不一定是逻辑上的队头。更稳妥的做法是设计一个 resize 接口内部实现如下bool resizeQueue(CircularQueue *q, int newCapacity) { if (newCapacity q-length) return false; int *newData (int*)malloc(sizeof(int) * newCapacity); for (int i 0; i q-length; i) { newData[i] q-data[(q-front i) % q-capacity]; } free(q-data); q-data newData; q-capacity newCapacity; q-front 0; q-rear q-length; return true; }这个实现里新数组的下标 0 到 length - 1 就是队列从头到尾的顺序front 归零rear 指向 length新的环从下标 0 开始完全符合循环语义。5. 延伸可以做得更通用5.1 从 int 到 void*前面示例里队列的存储类型是 int。但在实际项目中队列里存的对象往往不是 int而是结构体指针、消息帧、任务控制块等。如果每种类型都写一遍队列代码会膨胀得很厉害。C 语言里最通用的做法是把底层数组换成 void* 数组也就是存储指针而不是存储值。这样入队的就是指针出队时拿到的也是指针。使用时由调用方负责类型转换队列本身只关注指针的搬运。这个思路在操作系统内核的任务队列、驱动层的异步事件队列中很常见。当然用 void* 也有成本开发者需要自己保证指针指向的对象生命周期正确队列不负责释放。如果队列出队速度慢于入队速度指针指向的对象又不能及时释放就会累积内存占用。这属于使用层面的问题不是数据结构本身的问题。如果用的是 C可以直接用模板封装一个 CircularQueueT内部用 std::vectorT 做底层存储这样既能自动扩容又能保持类型安全。Python、Java、C# 也都有类似的库或者可以自己实现核心逻辑殊途同归。5.2 单生产者单消费者的无锁场景循环队列还有一个非常优秀的使用场景单生产者单消费者模型。在这种模型下如果保证同一时刻只有一个线程操作 front消费者只有一个线程操作 rear生产者那么不需要加锁入队和出队可以并发执行。原因也很简单生产者只修改 rear 和 length消费者只修改 front 和 length。理论上 length 是共享的会有竞争但只要把 length 的操作限定在各自线程内部合理同步或者采用内存屏障队列本身的数据区域就不会出现并发写同一个槽位的冲突。我在一个嵌入式项目中用这种方式实现了音频数据的实时采集和播放中间用了一个 2048 个元素的环形缓冲读写延迟极低。这个场景也是面试官特别喜欢的追问点。如果你能答出“单生产者单消费者不需要加锁”并且解释清楚为什么已经超过大多数候选人。再配合循环队列的数组实现整个面试表现会相当亮眼。还有一点想特别提一下即使是多生产者多消费者场景循环队列也可以作为基础组件在外部加锁或者用 CAS 操作保证原子性改造起来很方便。很多消息中间件内部的 channel 就是这么设计的。我个人用了这么多年数组实现循环队列最大的体会是这个结构看着简单但想在多线程场景里不出问题需要你对 front、rear、length 三者的语义有极其清晰的认识。任何一个字段的含义模糊了后面就是无穷无尽的调试。我在第一次实现无锁版本的时候就因为没有理解 length 在线程间的可见性导致偶发性丢数据排查了整整两天。后来老老实实先画清楚每个线程会改哪些字段再动手写代码就再也没出过类似问题。如果你正在犹豫要不要自己手写一个循环队列我的建议是不要犹豫直接写。先用 rear length 方案写一个单线程版本跑通之后再往多线程方向扩展。写完你会对数组、指针、取模这些基础概念有一个全新的认识比刷多少道算法题都实在。