循环队列原理详解：解决顺序队列假溢出与判空判满实现-北京尧图网络

1. 为什么队列会“假满”——顺序队列的致命缺陷1.1 队列的语义先进先出队列这个词大家都不陌生。食堂打饭排队、打印机排队出纸、银行叫号系统本质上都是队列先到的人先被服务后来的人只能排在队尾。放到数据结构里队列就是限制插入和删除位置的特殊线性表。它只允许在一端插入元素这一段叫队尾只允许在另一端删除元素这一段叫队头。插入操作叫入队删除操作叫出队。这种规则被称为FIFOFirst In First Out先进先出。这和我们熟悉的栈完全相反。栈是后进先出LIFO你往一个开口的箱子里放东西先放进去的反而最后才能拿出来。队列则像一根水管从一头塞进去从另一头流出来顺序不变。1.2 线性表插入删除的“一头一尾”错位如果队列是用数组实现的我们会维护两个指针变量front指向队头元素rear指向队尾元素的下一个位置。初始时front和rear都指向下标0队列为空。入队时把元素放到rear指向的位置然后rear加1。出队时把front指向的元素取出来然后front加1。这个逻辑看起来没有任何问题。假设数组容量是8连续入队5个元素后front0rear5。再出队3个元素front变成了3rear还是5。此时队列里还剩2个元素分别在下标3和4的位置。关键问题来了此时rear5还没有到数组末尾8但数组下标0、1、2的位置已经被空出来了。可是rear只会往后走不会回头。如果我再入队4个元素rear会逐个移动到6、7直到8。当rear等于8的那一刻队列明明还有空闲空间下标0、1、2全是空的程序却会判定“队列已满”拒绝继续入队。这就是顺序队列著名的“假溢出”现象数组尾部满了头部却空着整个队列处于一种“有空间但不能用”的尴尬状态。初学者看到这个现象往往一脸茫然以为是自己代码写错了实际上这是顺序存储结构本身的天然缺陷——rear指针“只能前进不能后退”空间利用率没有被拉满。解决思路有两个方向。第一个是数据搬移每次出队时把后面的元素全部往前挪一位保证队列元素永远从数组下标0开始连续存储。这个方案操作简单但出队的时间复杂度从O(1)变成了O(n)队列一旦很长性能损耗极其明显。第二个方案就是让rear和front两个指针“绕圈走”当rear走到数组末尾时让它重新指向下标0把之前出队留下的空位利用起来。这就是循环队列的核心思想。2. 循环队列的“转圈”机制取模运算与容量设计2.1 取模运算如何让rear“绕圈”循环队列的原理说穿了就是一句话把数组当成一个首尾相接的圆环。普通队列中rear到达数组末尾后无法继续后移因为下标8之后没有元素了。循环队列的做法是让rear在“到达末尾”这个瞬间跳回下标0。这个跳回操作不用if判断直接用取模运算搞定rear (rear 1) % capacity;当rear7、capacity8时(71)%80rear直接回到下标0。当rear5时(51)%86正常加1。取模运算天然地让rear的活动范围被限制在0到capacity-1之间无论它怎么移动永远不会越界。front指针的出队操作同样处理front (front 1) % capacity;两个指针都在环形空间内移动。用生活化的类比来说普通队列像一条笔直的走廊走到底就撞墙了循环队列把走廊的两端接起来变成了一个环形跑道你可以一直跑下去不会撞墙。数组的物理存储仍然是线性的并没有真正变成环。取模运算只是在逻辑上把“下标8之后”映射回“下标0”让指针的移动路径在逻辑上闭合了。这一点初学者容易混淆看到数组还是那个数组就以为循环队列是某种魔法其实只是改了一个移动指针的运算方式而已。2.2 容量到底怎么定为什么推荐2的幂既然取模运算要用到%操作符那么有一个性能优化的小技巧值得注意如果数组容量是2的幂比如8、16、32、64那么取模运算可以替换成位与运算rear (rear 1) (capacity - 1);对于任意2的幂nx % n等价于x (n - 1)。例如容量为8时7%87二进制是0111777结果一致8%80100001110结果也一致。位与运算比取模运算快得多在嵌入式开发、高频消息处理等场景中能省下不少CPU周期。不过这只是优化技巧不是必需条件。普通服务器程序里取模运算的性能损耗可以忽略不计容量设为7、9、10也完全没有问题。我个人的习惯是容量能设成2的幂就设成2的幂代码里顺手写位与运算既能提升性能代码读起来也干净。还有一个决定容量时必须考虑的点循环队列的可用空间不是capacity而是capacity-1。为什么少了一个格子这涉及判空判满的问题下一章详细展开。3. 判空判满的三种方案从浪费一个格子到计数器3.1 方案一浪费一个存储单元最经典循环队列里front和rear两个指针都在移动光靠frontrear无法区分队列是空还是满。因为空队列时front和rear相等队列满时它们也可能相等。举个例子容量为8的循环队列初始时frontrear0此时队列为空。不断入队当rear经过加1环绕一圈后再次等于front时队列恰好装满了8个元素。同样是frontrear含义却截然不同。最简单的解决办法是故意浪费一个存储单元。规定队列满的条件是“队尾指针的下一个位置是队头指针”也就是(rear 1) % capacity front这个条件下即使数组中还有一个空格子也视为满队列。换句话说容量为8的数组实际能存7个元素。多出的那1个格子作为“哨兵”充当区分空和满的界碑。判断空的条件不变仍然是front rear。这样问题就解决了空和满两个状态不再重叠因为满的时候rear永远不会直接等于front它们之间必然隔着一个空格。这个方案的缺点是每个队列都白白牺牲一个存储单元的容量。元素存储密度不是100%这是刻意为之的换来了判空判满逻辑的简洁。在绝大多数业务场景中牺牲一个元素的空间换来代码的清晰可靠完全值得。3.2 方案二计数器如果连一个格子都不愿意浪费可以在结构体里加一个size变量记录当前队列中的元素个数。入队成功则size加1出队成功则size减1。判空条件变为size0判满条件变为sizecapacity。这个方案逻辑最直观不需要理解复杂的取模关系也不浪费存储空间。代价是多维护一个变量入队出队操作都要同步更新它增删代码时必须小心翼翼。此外严格来说size确实属于“额外开销”虽然只有一个int的大小但对于某些追求极致内存利用率的嵌入式场景能省则省。3.3 方案三标志位第三种方法是在结构体里加一个flag变量初始为0。每次出队操作如果导致队列变空就把flag设为1每次入队操作把flag设为0。判空条件变成front rear flag 1判满条件变成front rear flag 0。这个方案同样不浪费存储空间但语义比较绕。你必须时刻记得flag记录了“最近一次操作是否让队列变空”一旦代码里某个分支漏更新flagbug会非常隐蔽排查起来费时费力。我在实际项目中几乎不用这个方案只有在某些不允许多占用字节的裸机环境中才会考虑。三种方案对比起来浪费一个存储单元是绝大多数教科书和开源库采用的做法。C标准库里的std::queue默认使用deque作为底层容器本身不涉及这个问题但自己手写环形缓冲区时几乎所有成熟的实现都选择“空一格”方案。因为判断条件简单、无额外变量、逻辑容易验证。下面我写的代码也用这个方案。4. 手写循环队列C语言实现与逐段拆解4.1 结构体定义与初始化完整代码里我先把结构体和初始化函数写出来typedef struct { int *data; // 动态数组存放队列元素 int front; // 队头下标 int rear; // 队尾下标指向下一个入队位置 int capacity; // 数组容量 } CircularQueue;这一步没有太多玄机数据结构就是三个字段加一个指针。关键是初始化时要给动态数组分配内存同时把front和rear都置为0CircularQueue *createQueue(int capacity) { CircularQueue *queue (CircularQueue *)malloc(sizeof(CircularQueue)); queue-data (int *)malloc(sizeof(int) * capacity); queue-front 0; queue-rear 0; queue-capacity capacity; return queue; }这里有两个容易被忽视的细节。第一capacity的含义是数组物理容量不是队列最大元素数。如果你调用createQueue(8)那么这个队列实际最多只能存放7个元素。新手经常在这里犯迷糊明明创建了容量8的队列怎么第8个元素死活入不了队。记住有一个格子被“浪费”了这是故意设计。第二如果capacity极端情况下为0malloc(0)的行为在不同编译器下表现不一致可能导致后续操作越界。初始化时最好加一个判断capacity太小就直接拒绝创建或按最小容量处理。这个属于健壮性的范畴线上代码必须考虑课堂练习可以暂时忽略。4.2 入队与出队的边界细节入队操作的完整实现int enqueue(CircularQueue *queue, int value) { if ((queue-rear 1) % queue-capacity queue-front) { return -1; // 队列已满入队失败 } queue-data[queue-rear] value; queue-rear (queue-rear 1) % queue-capacity; return 0; }入队分三步检查队列是否已满、在rear指向的位置写入数据、让rear向前移动一格。为什么先判断再写入因为如果队列已经满此时rear的下一个位置就是front再写入会把队头元素覆盖掉。这个覆盖不是我们想要的所以必须拦截。出队操作则是镜像对称int dequeue(CircularQueue *queue, int *value) { if (queue-front queue-rear) { return -1; // 队列为空出队失败 } *value queue-data[queue-front]; queue-front (queue-front 1) % queue-capacity; return 0; }出队同样三步检查是否为空、取出front指向的元素、让front前进一位。出队的值通过指针参数带出去返回值用来表示成功或失败这是C语言中常见的约定。还有一个查看队头元素但不出队的操作叫peek或frontint peek(CircularQueue *queue, int *value) { if (queue-front queue-rear) { return -1; } *value queue-data[queue-front]; return 0; }peek和dequeue的区别只有一个dequeue会让front移动peek不会。这两个操作在实际使用中都很重要比如消息队列里经常需要“看一眼”队头消息的优先级决定是否处理而暂时不把它出队。4.3 扩容与搬移看似简单实则容易翻车动态数组的队列用着用着总会有容量不够的一天。循环队列的扩容可比普通数组扩容麻烦多了因为元素在数组里的位置不再是连续的。普通数组扩容申请新数组把旧数组的元素按原下标拷过去释放旧数组完事。循环队列扩容旧的元素可能一部分在数组头部一部分在数组尾部直接按原下标复制会让元素顺序错乱。以容量为8的队列为例如果当前front5rear2那么队列中的元素依次存放在下标5、6、7、0、1这5个位置。扩容到容量16后正确的做法是让元素仍然保持原来的先后顺序依次放入新数组的下标0、1、2、3、4。具体实现思路是先算出队列中实际元素个数count然后从front开始遍历逐个搬移到新数组的连续位置。搬移完成后更新front为0rear为countint resizeQueue(CircularQueue *queue, int newCapacity) { int *newData (int *)malloc(sizeof(int) * newCapacity); if (newData NULL) { return -1; } int count 0; int index queue-front; while (index ! queue-rear) { newData[count] queue-data[index]; count; index (index 1) % queue-capacity; } free(queue-data); queue-data newData; queue-front 0; queue-rear count; queue-capacity newCapacity; return 0; }每次扩容之后队列的物理布局都被重新“捋直”了。元素全部从下标0开始连续存放下次再扩容时照旧处理。这种做法虽然搬移了全部元素但扩容本身是低频操作一两次O(n)的搬移代价可以接受。扩容这里最容易翻车的地方是如果你在搬移时用了一个临时数组存储旧元素又在这中间忘记更新queue-capacity那么index 1的操作就会用旧的容量做取模导致死循环。我在早期写这段代码时就栽过一次调试了半个小时才发现是取模运算用了旧容量的值。5. 循环队列的真实战场应用场景、变体与易错点5.1 循环队列在系统设计中的真实角色循环队列绝对不只是教材里的抽象概念它在真实系统中出现在各种关键位置。最典型的场景是操作系统的键盘缓冲区你打字的速度和CPU处理字符的速度是不一致的键盘中断产生字符的速度可能远快于应用程序读取的速度。如果字符被直接丢给应用程序处理一旦CPU繁忙字符就会丢失。操作系统用一个环形缓冲区暂存这些按键键盘中断往缓冲区写应用程序从缓冲区读两边互不阻塞。消息队列是另一个经典场景。生产者线程往队列尾部写入任务消费者线程从队头取出任务执行。如果队列满了生产者可以选择阻塞等待或者丢弃任务如果队列空了消费者可以选择休眠。循环队列作为中间缓存天然适应这种“一边写一边读”的生产者消费者模型。BFS广度优先搜索算法的辅助队列也经常用循环队列。BFS需要按层依次访问节点每访问一个节点就把它的邻居加入队列。在处理大规模图数据时如果图的节点数已知可以提前分配一个足够大的循环队列避免频繁的内存申请和释放。搜索的时间复杂度是O(VE)队列操作本身是O(1)配合起来整体性能非常稳定。在网络驱动里网卡收包后不是立刻交给协议栈而是放入一个环形缓冲区。因为这个缓冲区的大小通常是固定的通过读指针和写指针的差来判断剩余空间一有空闲就继续接收数据包。这些场景虽然细节不同但核心都是循环队列这一套逻辑。5.2 从单端到多端双端队列与优先队列理解了循环队列之后很多人会自然地问能不能在队列的两端都做插入和删除答案是可以这就是双端队列。双端队列允许在队头和队尾分别进行插入和删除操作。它的实现基于循环队列的思路但需要额外维护两端的移动规则。一个常见实现是用一个更大的数组front和back两个指针分别控制两端插队头时front向前移动注意是逆时针插队尾时back向后移动顺时针。如果一个队列需要支持“紧急任务插队”的需求双端队列就非常有用了。普通任务从队尾进入紧急任务可以直接从队头插入。但双端队列不能解决优先级排序问题如果你想按优先级出队而不是按入队顺序出队那要用的是优先队列通常用堆实现和循环队列不是一个维度的东西了。5.3 实战中容易踩的5个坑我把这些年在循环队列上踩过的坑统一整理一遍你写代码时可以对照自查。第一个坑是忘记判空就取队头元素。有些代码在调用peek或dequeue之前没检查is_empty结果queue是空的peek直接读到data[front]访问了一块未初始化的内存区域。在C语言中这种错误不会立刻崩溃而是返回一个乱七八糟的值问题定位非常头疼。第二个坑是入队时不判断满就直接写入。后果是rear追上了front导致旧数据被覆盖。如果你的程序没有崩溃但数据总是莫名其妙丢失十有八九是这个原因。第三个坑是迭代器遍历循环队列时循环条件写错。正确写法是int index queue-front; while (index ! queue-rear) { printf(%d , queue-data[index]); index (index 1) % queue-capacity; }有人会把循环条件写成index queue-rear这在普通队列中是对的放到循环队列里由于front可能大于rear一上来就跳过一半元素。取模运算的循环条件只能用!不能用或因为环形空间中根本没有“大小”关系。第四个坑是扩容搬移时取模用了旧容量前面已经提到。每次写代码前要提醒自己凡是和数组搬移相关的循环必须明确取模时用的是哪个capacity。第五个坑是在多线程环境下使用了同一个循环队列而没有加锁。std::queue都不是线程安全的循环队列更是如此。如果生产者和消费者同时操作front和rear会出现数据竞争。解决方法是加互斥锁或者使用无锁队列技术。无锁队列的进阶版比较复杂新手先从加锁开始保证线程安全再谈性能优化。5.4 如何用抽象接口提高代码复用性如果你的项目中有多处地方需要使用队列不建议每个模块都自己写一份循环队列代码。更优雅的做法是设计一套抽象接口把数据存储和业务逻辑解耦。C语言里可以用函数指针模拟面向对象的多态typedef struct { int (*enqueue)(void *self, void *value); int (*dequeue)(void *self, void *value); int (*is_empty)(void *self); int (*is_full)(void *self); } QueueInterface;每个具体队列实现只需要填充这四个函数指针。这样写的好处是上层业务代码只依赖QueueInterface不关心底层是循环队列还是链式队列。将来需要改动底层实现时上层代码完全不用动。在C或Java等面向对象语言中这一步实现起来更自然直接定义一个Queue接口让CircularQueue类实现它即可。不过需要注意过度抽象会带来一定的性能损失。如果你写的是底层基础组件追求极致性能直接操作结构体或类就好如果是业务层的代码抽象接口的收益远大于那一点点开销。6. 从数组到链式循环队列还有对手数组实现的循环队列有一个天然的制约——容量固定。即使你实现了扩容逻辑扩容也是一次性O(n)的操作。如果你需要的是一个容量不限的队列链式队列可能是更好的选择。链式队列用链表节点存储元素front指向头节点rear指向尾节点。入队就是在rear后面挂一个新节点出队就是摘掉front节点。它的优点是容量完全动态不受数组大小的限制缺点是每个节点有额外的指针开销访问元素的cache局部性不如数组。还有一个折中方案把循环队列的数组改成动态增长的方案每次扩容按1.5倍或2倍的因子增长。比如本次容量是8满了就扩到16再满就扩到32。这样分摊下来扩容的均摊时间复杂度是O(1)和链式队列的性能差距不大却享受了数组连续内存带来的cache优势。Go语言的切片、Java的ArrayDeque内部都采用了类似动态扩容的环形缓冲区实现它们在标准库中作为Deque接口的默认实现性能表现相当好。这说明循环队列不仅没有过时反而演化成了现代语言标准库中的高效容器。如果你需要读多写少的场景比如读取频繁、写入稀疏的应用数组实现更占优如果写入频繁且容量不定动态扩容的循环队列或链式队列更合适。选择哪种队列结构没有绝对的对错只有合不合适的区别。我个人的实践经验是优先选择动态扩容的循环队列因为它在尺寸灵活性和性能之间取得了最好的平衡。只有当你的生产环境对内存使用有硬性限制或队列长度不会大幅波动时才会考虑固定容量的循环队列。写到这里循环队列的核心实现、判空判满方案、扩容逻辑和易错点基本都过了一遍。如果你正在学习数据结构建议把上面的代码自己动手敲一遍然后跑几个测试用例观察当front和rear跨越数组边界时队列是如何工作的。实际运行一次的效果胜过阅读十遍理论。

循环队列原理详解：解决顺序队列假溢出与判空判满实现

相关推荐

Kubernetes初始搭建：从环境契约到控制平面自举

Windows主机痕迹管控：从日志审计到应急响应的闭环方案

从模糊代号‘rea‘到前端工程化：项目需求拆解实战

更多资讯

从招聘JD看网文平台算法化转型：内容策略、推荐算法与数据运营成新方向

rea式极简架构：从最小闭环到完整项目思维

PHP伪协议与反序列化：CTF文件包含漏洞的审计链路

可燃气体报警器电路设计：抗干扰、低漂移与硬件级可靠性实现

CentOS 8 内网离线安装 OpenOffice 全流程与依赖处理实战

C++基础核心：内存模型、对象生命周期与智能指针实战解读

今日更新

微信云开发旅游小程序实战：LBS打卡+UGC社交全栈方案

金融AI代理平台核心拆解：从多代理协作到财报分析实战

基于大数据的智慧旅游推荐与可视化平台架构实践

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？