队列和循环队列这两个词每一个学数据结构的人都不会陌生但说实话大部分人只停留在“会用”的阶段考试会背定义、刷题会写模板真到项目里自己设计一个缓冲区或者消息管道的时候反而容易翻车。我见过不少同学用数组实现队列跑着跑着发现明明前面有空位却入不了队最后靠移动元素硬扛性能直接崩掉。这篇内容想做的事情很简单把队列从原理到循环队列的实现细节完整拆一遍包括为什么顺序队列会有“假溢出”、循环队列的队空队满怎么判断、代码怎么写才不容易出bug以及从课堂代码到工程级环形缓冲还需要补哪些课。适合正在学数据结构的学生、刚接触嵌入式或后端开发的新人以及想回头把基础补扎实的老手。1. 从食堂排队到CPU调度队列到底解决了什么问题1.1 先进先出为什么这个规则不可替代队列强调的规则只有一条先来的人先服务后来的排后面。这个规则太自然了以至于我们常常忽略了它背后解决的核心问题——公平性和顺序性。食堂打饭的时候如果大家都挤成一团窗口就崩溃了如果允许插队弱势的一方根本吃不上饭。排队这个机制把“谁先谁后”这件事用一种极简的规则固定下来任何人不需要争论次序只需要站在队尾即可。计算机世界里这种需求更为强烈。CPU一次只能执行一个线程单核视角但进程和线程却不止一个谁先用CPU最公平也最容易被接受的规则就是“先来先服务”把准备执行的线程排成一个队列一个个来。再比如两台设备通信发送方和接收方速度不一定匹配如果不做缓冲高速发送方会冲垮低速接收方。引进一个队列作为中间缓冲数据谁先到谁先被处理顺序就不会乱。这就是队列存在的基本动机在顺序敏感的生产者-消费模型里队列是连接两侧最自然的结构。它的入队enqueue总是往队尾追加出队dequeue总是从队头移除访问限定在两端内部元素不允许跳队。正因为这种“受限”队列的实现可以做到极简出错的概率也被压缩到最小。1.2 计算机里的队列最常见的六大应用场景操作系统调度就绪队列、阻塞队列是操作系统课程里绕不开的概念线程的调度执行本质就是队列在运转。Linux内核里甚至有非常复杂的调度器但是最基本的“任务排队”思想永远一致。生产者-消费者模型日志系统就是典型。业务线程疯狂产生日志你不可能让每个业务线程都自己直接写磁盘而是把日志丢到一个队列里后台一个专门的线程慢慢刷盘。生产者和消费者的节奏彻底解耦。广度优先搜索BFS图的BFS必须借助队列保存“待访问节点”用栈做DFS行不通因为BFS天然要求按层序处理这正是FIFO的特性。I/O请求缓冲磁盘、网卡驱动里都有请求队列。当多个进程同时请求读磁盘驱动必须把这些请求排成队列逐个处理否则磁头反复跳动性能会断崖式下降。消息队列从Windows的消息队列到分布式消息中间件Kafka、RabbitMQ底层虽然各有各的存储结构但对外呈现的核心语义都是“先进先出”。后端的异步解耦、削峰填谷本质就是拿队列做容器。打印任务/批处理打印机同一时间只能服务一个任务多个用户提交打印作业时系统把它们排成队列按提交顺序依次打印你不会希望别人的文档插到你前面。1.3 队列这个抽象到底给了我们什么站在工程的角度队列真正提供的价值是三层第一层是解耦。生产者和消费者共享的只是队头和队尾两个操作接口彼此不知道对方的存在和状态。你可以随便改生产者的速率、消费者的处理逻辑只要不破坏入队出队规则两端互不影响。第二层是削峰填谷。突发请求瞬间涌进来时队列像一个蓄水池先把洪峰吸收掉后台按自己的节奏慢慢处理系统不会因为瞬时压力过大而崩溃。第三层是接口约束。因为元素只能从一端进、一端出你反而更难写出逻辑混乱的代码。想象一下如果你让操作者可以任意取出中间某个元素这个数据结构很快就退化成数组了各种越界和覆盖问题会接踵而至。2. 顺序队列的“假溢出”陷阱为什么数组实现不能直接玩2.1 顺序队列最简单的实现方式最直观的队列实现就是用数组。定义两个整型指针或者说索引front和rearfront指向队头元素rear指向队尾元素的下一个位置。初始状态下front rear 0。入队时把元素放到rear指向的位置然后rear往后挪一位void enqueue(int queue[], int *rear, int val) { queue[*rear] val; (*rear); }出队时把front指向的元素取走然后front往后挪一位int dequeue(int queue[], int *front) { int val queue[*front]; (*front); return val; }数组大小固定为N那这个队列能用的空间就只有N吗严格来说不是。只要rear不超过N每次入队一个元素front和rear之间的距离也就是队列长度就会增加出队则是缩小这个距离。当rear N时按这个实现就再也入不了队了。2.2 看似正常运作直到rear走到尽头关键问题来了。假设数组长度为5你依次入队a、b、c、d、e然后出队a、b、c、d这时候front已经移到4指向e。rear也已经走到5数组最后一个位置的下一个位置。此时队列里明明只有一个元素e数组前4个位置全是空的但是rear 5意味着不能再入队了。这就是经典的假溢出数组还有空间队列却告诉你满了。这种别扭现象的本质是我用两个单调递增的索引去描述一个可能反复出队入队的队列出队操作让front增大但数组前面只要front不回头就相当于被永久遗弃了。空间并没有被循环利用。那有同学会问能不能在入队前把元素批量往前移动技术上可以但代价太大。每次入队都触发一次O(n)的数据搬移均摊下来每次入队成本从O(1)变成O(n)。在高频场景下等于把队列用废了。你想想一个串口接收缓冲区每来一个字节都要搬移全体数据MCU早就烧起来了。2.3 循环的关键一步让rear“绕回去”既然数组前面的空间还在最合理的做法就是让rear走到末尾后绕回数组头部。也就是说数组在逻辑上不再是一根直线而是一个首尾相接的环。“绕回去”的实现手段是取模运算rear (rear 1) % N;当rear 4、N 5时(4 1) % 5 0re a r 直接跳回0号位置。同样的front出队时也要取模。这样整个数组的空间就被循环使用起来了。这种“首尾相接”的逻辑结构就是循环队列Circular Queue。它的物理存储依然是数组但在逻辑上构成一个环。搞清楚这一点你就明白了循环队列不是什么高深的东西本质上就是为了解决顺序队列假溢出问题而做的一层“逻辑包装”。3. 循环队列核心设计队空与队满的三种判断方案3.1 方案一牺牲一个存储单元最经典做法循环队列最大的难点不是入队出队而是如何区分队空和队满。因为我们是用两个索引来描述队列状态当front rear时可能是空队列也可能是队列恰好被填满因为满的时候rear绕一圈又追上了front。经典的解决方案要求队列最多只存放capacity - 1个元素始终空出一个单元不用。这时候队空条件front rear队满条件(rear 1) % capacity front为什么空出这一个格子就能区分因为此时队列满时rear的下一个位置恰好是front而rear本身不可能等于front。换句话说这两个状态不再共用同一个判定式风险自然解除。这个方案最大的好处是判断条件极简只需要比较两个索引不需要额外的变量空间开销为零。它的代价是牺牲了一个存储单元——数组申请了8个元素实际最多只能存7个。在大多数场景下为了一个单元的空间去增加复杂度并不划算所以这是我在教学和实践中优先推荐的方案。3.2 方案二维护计数器length灵活直观不想浪费那个格子的话可以额外维护一个变量length表示当前队列中元素个数。初始length 0入队时length出队时length--。队空条件length 0队满条件length capacity队尾位置(front length - 1) % capacity入队时新元素要放的位置(front length) % capacity这个方案看起来多臭一个变量但收益也很明显首先是空间利用率达到100%数组申请8个就能存8个其次是调试方便队列里到底有多少数据直接看length一目了然不用拿两个索引推半天。缺点就是每次入队出队都要额外更新length多了一次读写操作。但这个成本几乎可以忽略现代CPU做一次整数自增和判断撑死几个时钟周期。所以在工程上这个方案也很常见尤其是需要快速获取队列长度的场景。3.3 方案三设置标志位少用但值得一提第三种思路是维护一个布尔标志flag。入队时把flag置为true出队时把flag置为false。那么队空条件front rear flag false队满条件front rear flag true理论上可行空间利用率也是100%而且不像length那样每次操作都要自增自减只需要在边界时修改标志。但这个方案的隐患在于标志位可能会因为异常流程而失真。比如某个分支忘记更新flag整个队列的判空判满逻辑就会全线崩溃而且排查起来比length方案绕得多。所以我在实际项目里很少用只当它是个锻炼思维的拓展题。三种方案放在一起对比方案判空条件判满条件空间利用率额外开销复杂度牺牲单元front rear(rear1)%capacity frontcapacity-1个无最简单计数器lengthlength 0length capacity100%每次操作更新length简单直观标志位flagfrontrear且flag为falsefrontrear且flag为true100%每次操作更新flag容易出错3.4 三种方案的选择建议我的建议很直接如果这是面试、考试或者你写一个通用工具类用方案一。它的判定逻辑是行业默认大家看了你的代码立刻就能读懂沟通成本最低。如果你需要精确控制缓冲区容量一个元素都不能浪费或者你经常需要知道当前队列占用情况来做流量控制用方案二。比如网络驱动里缓冲区大小就那么几KB能省一个是一个。方案三除非是理工学院实验要求否则别碰。它的维护成本和出错概率完全不划算。4. 手写循环队列C语言实现与关键细节拆解4.1 结构体设计与初始化我自己写循环队列的习惯是把队列封装成一个结构体避免散落裸指针。下面这段代码基于方案一是工程里最常用也最稳的组合#define MAX_SIZE 8 typedef struct { int data[MAX_SIZE]; int front; // 队头索引指向队头元素 int rear; // 队尾索引指向队尾元素的下一个位置 } CircularQueue; void initQueue(CircularQueue *q) { q-front 0; q-rear 0; }注意MAX_SIZE定义成了8但实际队列容量是7。因为方案一必须牺牲一个格子。这个容量 MAX_SIZE - 1的关系写代码时要铭记在心。有人会问为什么rear不直接指向队尾元素而是指向队尾的下一个位置这里其实是历史习惯和判断便利性的双重选择。如果rear直接指向队尾元素出队入队的代码要绕更多弯判断条件也容易出错。保持“队头指向元素队尾指向空位”的约定代码写起来很顺手你只需要接受这个惯例就好。4.2 入队、出队以及存取操作入队函数int enqueue(CircularQueue *q, int val) { // 队满判断(rear 1) % MAX_SIZE front if ((q-rear 1) % MAX_SIZE q-front) { return -1; // 队列已满入队失败 } q-data[q-rear] val; q-rear (q-rear 1) % MAX_SIZE; return 0; }出队函数int dequeue(CircularQueue *q, int *val) { // 队空判断front rear if (q-front q-rear) { return -1; // 队列已空出队失败 } *val q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return 0; }获取队头元素和当前长度int getFront(CircularQueue *q, int *val) { if (q-front q-rear) { return -1; } *val q-data[q-front]; return 0; } int getLength(CircularQueue *q) { // 队列长度的标准公式 return (q-rear - q-front MAX_SIZE) % MAX_SIZE; }这里有个细节值得多说一句计算队列长度时(rear - front MAX_SIZE) % MAX_SIZE这个公式绝对不能简化成rear - front。因为rear绕回头部后它可能小于front直接相减会得到负数。加上MAX_SIZE再取模是为了把所有情况都归一化到[0, MAX_SIZE - 1]区间。4.3 几个容易写错的地方都是血泪教训取模运算的优先级很多人会踩坑。(q-rear 1) % MAX_SIZE注意是(q-rear 1)整体先算不要写成了q-rear 1 % MAX_SIZE。后者等于q-rear 1当MAX_SIZE大于1时相当于没做任何限制队列满了还会越界写入属于必炸的bug。我见过不止一次这种事故发生场景全是内存被悄无声息改坏之后的诡异行为。容量换算的坑。初始化数组为MAX_SIZE但实际队列能用的元素是MAX_SIZE - 1个。很多人在入队时判断“还要看看当前元素数是否小于MAX_SIZE”结果立刻踩中假溢出的边界问题。记住循环队列的判断依据只有两个front rear表示空(rear 1) % MAX_SIZE front表示满不要再额外引入其他判断。索引越界问题往往发生在取模没写全的函数里。每次操作front或rear都必须用取模把结果限制在[0, MAX_SIZE - 1]之间。你可能会觉得rear之后最多等于MAX_SIZE但连续多次入队后rear必然超出数组边界此时如果不取模轻则数组越界写重则直接段错误。4.4 性能优化容量取2的幂用位运算替代取模在嵌入式或者高频收发场景里取模运算%虽然价格不高但积少成多还是有影响。有一个非常经典的优化技巧把数组容量定义成2的幂比如16、32、64、256。此时(x) % N可以改写成(x) (N - 1)。因为对2的幂做取模结果只有低N-1位的位模式。比如N 8x % 8的结果正好是x 7。位与运算一个时钟周期就能完成编译器也不会自动帮你优化取模因为取模本身要考虑负数等复杂情况直接改写是实打实的收益。#define MAX_SIZE 256 int enqueue(CircularQueue *q, int val) { if ((q-rear 1) (MAX_SIZE - 1) q-front) { // 注意括号 return -1; } q-data[q-rear] val; q-rear (q-rear 1) (MAX_SIZE - 1); return 0; }这种方式下MAX_SIZE必须是2的幂否则MAX_SIZE - 1的位运算结果就完全不对了这是一个必须写进注释的前置条件。我自己在STM32的串口环形缓冲里就是这么干的代码跑起来毫无压力而且逻辑更简洁。5. 从课堂到工程循环队列的边界与进阶扩展5.1 让循环队列更通用泛型与void*前面代码里元素类型是int真到项目里队列里往往是结构体、指针或者任意自定义类型。C语言标准库里没有泛型容器但你可以用void*存指针或者用宏模板模拟泛型。用void*实现的话底层存储就是void* data[MAX_SIZE]入队存指针出队取指针元素本身是调用方管理的。这种方式灵活但要小心内存生命周期入队后原指针指向的对象必须保持有效出队后由调用方负责释放否则就会内存泄漏或悬垂指针。宏模板方案则接近C模板的展开思路为不同类型生成一套独立函数。宏写起来贼灵活但很难调试报错信息能把你绕晕。我的建议是如果项目用C直接template或者直接用标准库的std::queue和std::deque如果必须在纯C环境先评估队列元素个数和复杂度再用void*方案别一开始就搞宏体操。5.2 动态扩容与数据搬移的取舍数组实现循环队列容量是固定的。但业务是动态的队列满了怎么办两个选择要么入队失败返回错误码简单粗暴要么动态扩容灵活但麻烦。动态扩容的思路不算复杂分配一个更大的数组把原队列中的元素按逻辑顺序拷过去然后更新front、rear。要注意的是循环逻辑下元素在内存里是“断裂”的队头到队尾可能跨越了数组的末尾。拷贝的时候不能简单用memcpy整块复制得考虑两段从front到数组末尾这一段以及从数组头部到rear这一段如果有的话。一个可行的办法先算出当前队列中元素数量len然后把front重置为0rear重置为len依次把元素移到新数组的从0开始的位置。本质上就是一次“逻辑摆正”。int resize(CircularQueue *q, int new_capacity) { // 实际上你需要一个能表示长度的结构可以用方案二改造 int len (q-rear - q-front q-capacity) % q-capacity; int *new_data (int*)malloc(new_capacity * sizeof(int)); if (!new_data) return -1; for (int i 0; i len; i) { new_data[i] q-data[(q-front i) % q-capacity]; } free(q-data); q-data new_data; q-front 0; q-rear len; q-capacity new_capacity; return 0; }这种扩容方式有一个小代价扩容时要把所有元素搬一次复杂度O(n)。但扩容不是高频操作均摊下来依然可接受。另外扩容后记得更新容量新的容量最好仍然是2的幂方便继续用位运算优化。5.3 多线程下的队列阻塞队列、原子操作与无锁队列循环队列的单线程版本写稳了接下来要面对的就是多线程。生产者和消费者跑在不同的线程里这时必须考虑数据竞争。最容易想到的方案是加锁。入队出队都包一层互斥锁简单可靠但锁竞争激烈时性能会恶化。进阶一点可以用读写锁只是队列的入队出队都是写操作读写锁收益不太明显。再进阶就是原子操作与无锁队列。无锁队列的核心思路是让入队和出队分别只操作自己的索引rear和front配合CASCompare-And-Swap原子指令来保证操作的原子性。这里有很多坑比如ABA问题、内存序问题、George在单核上看起来没问题但多核上缓存不一致导致的现象。真正要在生产环境中实现无锁队列建议直接读成熟项目的源码比如LMAX Disruptor、Boost的lockfree队列或者Linux内核的kfifo不要自己拍脑袋写很容易写出“自认为无锁、实际上bug一堆”的代码。在Java里阻塞队列被封装得很好ArrayBlockingQueue、LinkedBlockingQueue、ConcurrentLinkedQueue都是一线常用的类。它们背后的核心思想仍然是“循环数组 队头队尾索引 并发控制”只是复杂度更高。理解了我们手写的循环队列再去看这些源码会顺畅很多。5.4 循环队列在实际项目中的典型位置说实话学了循环队列你不用太纠结“现实世界里哪个大型项目直接用了我写的这段代码”。但它的变体和思想无处不在串口/UART环形缓冲这是嵌入式里最常见的应用。串口中断不断把收到的字节写入环形缓冲区主循环再把字节取出来处理。之所以用环形缓冲是因为中断里不能做太多事也不可能在中断里做动态分配提前开一块固定大小的环形缓冲区是最稳的。音视频采集缓冲音频帧、视频帧从采集设备进来编码线程按帧取走。缓冲队列天然需要FIFO语义来保证帧序。网络协议栈收包缓存网卡驱动的DMA环形队列本质就是一个循环缓冲区放满了包描述符驱动逐个取回来处理。在Linux内核里环形队列的经典实现叫kfifo它的高效之处就是无锁化位运算优化。消息队列的核心调度语义消息队列产品里会把队列解耦成多个消费者组、分区等复杂概念但“单队列先进先出”这条底线从来没变过。底层数据结构的实现者依然绕不开怎么高效管理头部和尾部。所以我的看法是循环队列本身是个基础构件它不会独立成为业务系统但它会持续出现在你最意想不到的底层位置。把它的原理彻底吃透看底层代码就会有一种“这不就是循环队列换层皮吗”的亲切感。最后说一个我个人的习惯做完循环队列的代码后一定要写一个简单的压力测试函数一次性入队大量数据再出队打印出队顺序、长度变化和最终front、rear的值。这个测试能暴露绝大多数逻辑错误而且测试成本极低。我在调试串口缓冲时发生的一件事也让我记忆深刻一开始我一直以为队列满了导致丢包后来加了一个length计数器才发现问题是出队端消费太慢缓冲区容量设计太小根本不是队列实现本身的错。所以搞清楚队列的状态和容量规划往往比调整代码本身更重要。 循环队列从原理到工程实践：假溢出与环形缓冲实现解析
队列和循环队列这两个词每一个学数据结构的人都不会陌生但说实话大部分人只停留在“会用”的阶段考试会背定义、刷题会写模板真到项目里自己设计一个缓冲区或者消息管道的时候反而容易翻车。我见过不少同学用数组实现队列跑着跑着发现明明前面有空位却入不了队最后靠移动元素硬扛性能直接崩掉。这篇内容想做的事情很简单把队列从原理到循环队列的实现细节完整拆一遍包括为什么顺序队列会有“假溢出”、循环队列的队空队满怎么判断、代码怎么写才不容易出bug以及从课堂代码到工程级环形缓冲还需要补哪些课。适合正在学数据结构的学生、刚接触嵌入式或后端开发的新人以及想回头把基础补扎实的老手。1. 从食堂排队到CPU调度队列到底解决了什么问题1.1 先进先出为什么这个规则不可替代队列强调的规则只有一条先来的人先服务后来的排后面。这个规则太自然了以至于我们常常忽略了它背后解决的核心问题——公平性和顺序性。食堂打饭的时候如果大家都挤成一团窗口就崩溃了如果允许插队弱势的一方根本吃不上饭。排队这个机制把“谁先谁后”这件事用一种极简的规则固定下来任何人不需要争论次序只需要站在队尾即可。计算机世界里这种需求更为强烈。CPU一次只能执行一个线程单核视角但进程和线程却不止一个谁先用CPU最公平也最容易被接受的规则就是“先来先服务”把准备执行的线程排成一个队列一个个来。再比如两台设备通信发送方和接收方速度不一定匹配如果不做缓冲高速发送方会冲垮低速接收方。引进一个队列作为中间缓冲数据谁先到谁先被处理顺序就不会乱。这就是队列存在的基本动机在顺序敏感的生产者-消费模型里队列是连接两侧最自然的结构。它的入队enqueue总是往队尾追加出队dequeue总是从队头移除访问限定在两端内部元素不允许跳队。正因为这种“受限”队列的实现可以做到极简出错的概率也被压缩到最小。1.2 计算机里的队列最常见的六大应用场景操作系统调度就绪队列、阻塞队列是操作系统课程里绕不开的概念线程的调度执行本质就是队列在运转。Linux内核里甚至有非常复杂的调度器但是最基本的“任务排队”思想永远一致。生产者-消费者模型日志系统就是典型。业务线程疯狂产生日志你不可能让每个业务线程都自己直接写磁盘而是把日志丢到一个队列里后台一个专门的线程慢慢刷盘。生产者和消费者的节奏彻底解耦。广度优先搜索BFS图的BFS必须借助队列保存“待访问节点”用栈做DFS行不通因为BFS天然要求按层序处理这正是FIFO的特性。I/O请求缓冲磁盘、网卡驱动里都有请求队列。当多个进程同时请求读磁盘驱动必须把这些请求排成队列逐个处理否则磁头反复跳动性能会断崖式下降。消息队列从Windows的消息队列到分布式消息中间件Kafka、RabbitMQ底层虽然各有各的存储结构但对外呈现的核心语义都是“先进先出”。后端的异步解耦、削峰填谷本质就是拿队列做容器。打印任务/批处理打印机同一时间只能服务一个任务多个用户提交打印作业时系统把它们排成队列按提交顺序依次打印你不会希望别人的文档插到你前面。1.3 队列这个抽象到底给了我们什么站在工程的角度队列真正提供的价值是三层第一层是解耦。生产者和消费者共享的只是队头和队尾两个操作接口彼此不知道对方的存在和状态。你可以随便改生产者的速率、消费者的处理逻辑只要不破坏入队出队规则两端互不影响。第二层是削峰填谷。突发请求瞬间涌进来时队列像一个蓄水池先把洪峰吸收掉后台按自己的节奏慢慢处理系统不会因为瞬时压力过大而崩溃。第三层是接口约束。因为元素只能从一端进、一端出你反而更难写出逻辑混乱的代码。想象一下如果你让操作者可以任意取出中间某个元素这个数据结构很快就退化成数组了各种越界和覆盖问题会接踵而至。2. 顺序队列的“假溢出”陷阱为什么数组实现不能直接玩2.1 顺序队列最简单的实现方式最直观的队列实现就是用数组。定义两个整型指针或者说索引front和rearfront指向队头元素rear指向队尾元素的下一个位置。初始状态下front rear 0。入队时把元素放到rear指向的位置然后rear往后挪一位void enqueue(int queue[], int *rear, int val) { queue[*rear] val; (*rear); }出队时把front指向的元素取走然后front往后挪一位int dequeue(int queue[], int *front) { int val queue[*front]; (*front); return val; }数组大小固定为N那这个队列能用的空间就只有N吗严格来说不是。只要rear不超过N每次入队一个元素front和rear之间的距离也就是队列长度就会增加出队则是缩小这个距离。当rear N时按这个实现就再也入不了队了。2.2 看似正常运作直到rear走到尽头关键问题来了。假设数组长度为5你依次入队a、b、c、d、e然后出队a、b、c、d这时候front已经移到4指向e。rear也已经走到5数组最后一个位置的下一个位置。此时队列里明明只有一个元素e数组前4个位置全是空的但是rear 5意味着不能再入队了。这就是经典的假溢出数组还有空间队列却告诉你满了。这种别扭现象的本质是我用两个单调递增的索引去描述一个可能反复出队入队的队列出队操作让front增大但数组前面只要front不回头就相当于被永久遗弃了。空间并没有被循环利用。那有同学会问能不能在入队前把元素批量往前移动技术上可以但代价太大。每次入队都触发一次O(n)的数据搬移均摊下来每次入队成本从O(1)变成O(n)。在高频场景下等于把队列用废了。你想想一个串口接收缓冲区每来一个字节都要搬移全体数据MCU早就烧起来了。2.3 循环的关键一步让rear“绕回去”既然数组前面的空间还在最合理的做法就是让rear走到末尾后绕回数组头部。也就是说数组在逻辑上不再是一根直线而是一个首尾相接的环。“绕回去”的实现手段是取模运算rear (rear 1) % N;当rear 4、N 5时(4 1) % 5 0re a r 直接跳回0号位置。同样的front出队时也要取模。这样整个数组的空间就被循环使用起来了。这种“首尾相接”的逻辑结构就是循环队列Circular Queue。它的物理存储依然是数组但在逻辑上构成一个环。搞清楚这一点你就明白了循环队列不是什么高深的东西本质上就是为了解决顺序队列假溢出问题而做的一层“逻辑包装”。3. 循环队列核心设计队空与队满的三种判断方案3.1 方案一牺牲一个存储单元最经典做法循环队列最大的难点不是入队出队而是如何区分队空和队满。因为我们是用两个索引来描述队列状态当front rear时可能是空队列也可能是队列恰好被填满因为满的时候rear绕一圈又追上了front。经典的解决方案要求队列最多只存放capacity - 1个元素始终空出一个单元不用。这时候队空条件front rear队满条件(rear 1) % capacity front为什么空出这一个格子就能区分因为此时队列满时rear的下一个位置恰好是front而rear本身不可能等于front。换句话说这两个状态不再共用同一个判定式风险自然解除。这个方案最大的好处是判断条件极简只需要比较两个索引不需要额外的变量空间开销为零。它的代价是牺牲了一个存储单元——数组申请了8个元素实际最多只能存7个。在大多数场景下为了一个单元的空间去增加复杂度并不划算所以这是我在教学和实践中优先推荐的方案。3.2 方案二维护计数器length灵活直观不想浪费那个格子的话可以额外维护一个变量length表示当前队列中元素个数。初始length 0入队时length出队时length--。队空条件length 0队满条件length capacity队尾位置(front length - 1) % capacity入队时新元素要放的位置(front length) % capacity这个方案看起来多臭一个变量但收益也很明显首先是空间利用率达到100%数组申请8个就能存8个其次是调试方便队列里到底有多少数据直接看length一目了然不用拿两个索引推半天。缺点就是每次入队出队都要额外更新length多了一次读写操作。但这个成本几乎可以忽略现代CPU做一次整数自增和判断撑死几个时钟周期。所以在工程上这个方案也很常见尤其是需要快速获取队列长度的场景。3.3 方案三设置标志位少用但值得一提第三种思路是维护一个布尔标志flag。入队时把flag置为true出队时把flag置为false。那么队空条件front rear flag false队满条件front rear flag true理论上可行空间利用率也是100%而且不像length那样每次操作都要自增自减只需要在边界时修改标志。但这个方案的隐患在于标志位可能会因为异常流程而失真。比如某个分支忘记更新flag整个队列的判空判满逻辑就会全线崩溃而且排查起来比length方案绕得多。所以我在实际项目里很少用只当它是个锻炼思维的拓展题。三种方案放在一起对比方案判空条件判满条件空间利用率额外开销复杂度牺牲单元front rear(rear1)%capacity frontcapacity-1个无最简单计数器lengthlength 0length capacity100%每次操作更新length简单直观标志位flagfrontrear且flag为falsefrontrear且flag为true100%每次操作更新flag容易出错3.4 三种方案的选择建议我的建议很直接如果这是面试、考试或者你写一个通用工具类用方案一。它的判定逻辑是行业默认大家看了你的代码立刻就能读懂沟通成本最低。如果你需要精确控制缓冲区容量一个元素都不能浪费或者你经常需要知道当前队列占用情况来做流量控制用方案二。比如网络驱动里缓冲区大小就那么几KB能省一个是一个。方案三除非是理工学院实验要求否则别碰。它的维护成本和出错概率完全不划算。4. 手写循环队列C语言实现与关键细节拆解4.1 结构体设计与初始化我自己写循环队列的习惯是把队列封装成一个结构体避免散落裸指针。下面这段代码基于方案一是工程里最常用也最稳的组合#define MAX_SIZE 8 typedef struct { int data[MAX_SIZE]; int front; // 队头索引指向队头元素 int rear; // 队尾索引指向队尾元素的下一个位置 } CircularQueue; void initQueue(CircularQueue *q) { q-front 0; q-rear 0; }注意MAX_SIZE定义成了8但实际队列容量是7。因为方案一必须牺牲一个格子。这个容量 MAX_SIZE - 1的关系写代码时要铭记在心。有人会问为什么rear不直接指向队尾元素而是指向队尾的下一个位置这里其实是历史习惯和判断便利性的双重选择。如果rear直接指向队尾元素出队入队的代码要绕更多弯判断条件也容易出错。保持“队头指向元素队尾指向空位”的约定代码写起来很顺手你只需要接受这个惯例就好。4.2 入队、出队以及存取操作入队函数int enqueue(CircularQueue *q, int val) { // 队满判断(rear 1) % MAX_SIZE front if ((q-rear 1) % MAX_SIZE q-front) { return -1; // 队列已满入队失败 } q-data[q-rear] val; q-rear (q-rear 1) % MAX_SIZE; return 0; }出队函数int dequeue(CircularQueue *q, int *val) { // 队空判断front rear if (q-front q-rear) { return -1; // 队列已空出队失败 } *val q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return 0; }获取队头元素和当前长度int getFront(CircularQueue *q, int *val) { if (q-front q-rear) { return -1; } *val q-data[q-front]; return 0; } int getLength(CircularQueue *q) { // 队列长度的标准公式 return (q-rear - q-front MAX_SIZE) % MAX_SIZE; }这里有个细节值得多说一句计算队列长度时(rear - front MAX_SIZE) % MAX_SIZE这个公式绝对不能简化成rear - front。因为rear绕回头部后它可能小于front直接相减会得到负数。加上MAX_SIZE再取模是为了把所有情况都归一化到[0, MAX_SIZE - 1]区间。4.3 几个容易写错的地方都是血泪教训取模运算的优先级很多人会踩坑。(q-rear 1) % MAX_SIZE注意是(q-rear 1)整体先算不要写成了q-rear 1 % MAX_SIZE。后者等于q-rear 1当MAX_SIZE大于1时相当于没做任何限制队列满了还会越界写入属于必炸的bug。我见过不止一次这种事故发生场景全是内存被悄无声息改坏之后的诡异行为。容量换算的坑。初始化数组为MAX_SIZE但实际队列能用的元素是MAX_SIZE - 1个。很多人在入队时判断“还要看看当前元素数是否小于MAX_SIZE”结果立刻踩中假溢出的边界问题。记住循环队列的判断依据只有两个front rear表示空(rear 1) % MAX_SIZE front表示满不要再额外引入其他判断。索引越界问题往往发生在取模没写全的函数里。每次操作front或rear都必须用取模把结果限制在[0, MAX_SIZE - 1]之间。你可能会觉得rear之后最多等于MAX_SIZE但连续多次入队后rear必然超出数组边界此时如果不取模轻则数组越界写重则直接段错误。4.4 性能优化容量取2的幂用位运算替代取模在嵌入式或者高频收发场景里取模运算%虽然价格不高但积少成多还是有影响。有一个非常经典的优化技巧把数组容量定义成2的幂比如16、32、64、256。此时(x) % N可以改写成(x) (N - 1)。因为对2的幂做取模结果只有低N-1位的位模式。比如N 8x % 8的结果正好是x 7。位与运算一个时钟周期就能完成编译器也不会自动帮你优化取模因为取模本身要考虑负数等复杂情况直接改写是实打实的收益。#define MAX_SIZE 256 int enqueue(CircularQueue *q, int val) { if ((q-rear 1) (MAX_SIZE - 1) q-front) { // 注意括号 return -1; } q-data[q-rear] val; q-rear (q-rear 1) (MAX_SIZE - 1); return 0; }这种方式下MAX_SIZE必须是2的幂否则MAX_SIZE - 1的位运算结果就完全不对了这是一个必须写进注释的前置条件。我自己在STM32的串口环形缓冲里就是这么干的代码跑起来毫无压力而且逻辑更简洁。5. 从课堂到工程循环队列的边界与进阶扩展5.1 让循环队列更通用泛型与void*前面代码里元素类型是int真到项目里队列里往往是结构体、指针或者任意自定义类型。C语言标准库里没有泛型容器但你可以用void*存指针或者用宏模板模拟泛型。用void*实现的话底层存储就是void* data[MAX_SIZE]入队存指针出队取指针元素本身是调用方管理的。这种方式灵活但要小心内存生命周期入队后原指针指向的对象必须保持有效出队后由调用方负责释放否则就会内存泄漏或悬垂指针。宏模板方案则接近C模板的展开思路为不同类型生成一套独立函数。宏写起来贼灵活但很难调试报错信息能把你绕晕。我的建议是如果项目用C直接template或者直接用标准库的std::queue和std::deque如果必须在纯C环境先评估队列元素个数和复杂度再用void*方案别一开始就搞宏体操。5.2 动态扩容与数据搬移的取舍数组实现循环队列容量是固定的。但业务是动态的队列满了怎么办两个选择要么入队失败返回错误码简单粗暴要么动态扩容灵活但麻烦。动态扩容的思路不算复杂分配一个更大的数组把原队列中的元素按逻辑顺序拷过去然后更新front、rear。要注意的是循环逻辑下元素在内存里是“断裂”的队头到队尾可能跨越了数组的末尾。拷贝的时候不能简单用memcpy整块复制得考虑两段从front到数组末尾这一段以及从数组头部到rear这一段如果有的话。一个可行的办法先算出当前队列中元素数量len然后把front重置为0rear重置为len依次把元素移到新数组的从0开始的位置。本质上就是一次“逻辑摆正”。int resize(CircularQueue *q, int new_capacity) { // 实际上你需要一个能表示长度的结构可以用方案二改造 int len (q-rear - q-front q-capacity) % q-capacity; int *new_data (int*)malloc(new_capacity * sizeof(int)); if (!new_data) return -1; for (int i 0; i len; i) { new_data[i] q-data[(q-front i) % q-capacity]; } free(q-data); q-data new_data; q-front 0; q-rear len; q-capacity new_capacity; return 0; }这种扩容方式有一个小代价扩容时要把所有元素搬一次复杂度O(n)。但扩容不是高频操作均摊下来依然可接受。另外扩容后记得更新容量新的容量最好仍然是2的幂方便继续用位运算优化。5.3 多线程下的队列阻塞队列、原子操作与无锁队列循环队列的单线程版本写稳了接下来要面对的就是多线程。生产者和消费者跑在不同的线程里这时必须考虑数据竞争。最容易想到的方案是加锁。入队出队都包一层互斥锁简单可靠但锁竞争激烈时性能会恶化。进阶一点可以用读写锁只是队列的入队出队都是写操作读写锁收益不太明显。再进阶就是原子操作与无锁队列。无锁队列的核心思路是让入队和出队分别只操作自己的索引rear和front配合CASCompare-And-Swap原子指令来保证操作的原子性。这里有很多坑比如ABA问题、内存序问题、George在单核上看起来没问题但多核上缓存不一致导致的现象。真正要在生产环境中实现无锁队列建议直接读成熟项目的源码比如LMAX Disruptor、Boost的lockfree队列或者Linux内核的kfifo不要自己拍脑袋写很容易写出“自认为无锁、实际上bug一堆”的代码。在Java里阻塞队列被封装得很好ArrayBlockingQueue、LinkedBlockingQueue、ConcurrentLinkedQueue都是一线常用的类。它们背后的核心思想仍然是“循环数组 队头队尾索引 并发控制”只是复杂度更高。理解了我们手写的循环队列再去看这些源码会顺畅很多。5.4 循环队列在实际项目中的典型位置说实话学了循环队列你不用太纠结“现实世界里哪个大型项目直接用了我写的这段代码”。但它的变体和思想无处不在串口/UART环形缓冲这是嵌入式里最常见的应用。串口中断不断把收到的字节写入环形缓冲区主循环再把字节取出来处理。之所以用环形缓冲是因为中断里不能做太多事也不可能在中断里做动态分配提前开一块固定大小的环形缓冲区是最稳的。音视频采集缓冲音频帧、视频帧从采集设备进来编码线程按帧取走。缓冲队列天然需要FIFO语义来保证帧序。网络协议栈收包缓存网卡驱动的DMA环形队列本质就是一个循环缓冲区放满了包描述符驱动逐个取回来处理。在Linux内核里环形队列的经典实现叫kfifo它的高效之处就是无锁化位运算优化。消息队列的核心调度语义消息队列产品里会把队列解耦成多个消费者组、分区等复杂概念但“单队列先进先出”这条底线从来没变过。底层数据结构的实现者依然绕不开怎么高效管理头部和尾部。所以我的看法是循环队列本身是个基础构件它不会独立成为业务系统但它会持续出现在你最意想不到的底层位置。把它的原理彻底吃透看底层代码就会有一种“这不就是循环队列换层皮吗”的亲切感。最后说一个我个人的习惯做完循环队列的代码后一定要写一个简单的压力测试函数一次性入队大量数据再出队打印出队顺序、长度变化和最终front、rear的值。这个测试能暴露绝大多数逻辑错误而且测试成本极低。我在调试串口缓冲时发生的一件事也让我记忆深刻一开始我一直以为队列满了导致丢包后来加了一个length计数器才发现问题是出队端消费太慢缓冲区容量设计太小根本不是队列实现本身的错。所以搞清楚队列的状态和容量规划往往比调整代码本身更重要。