写在前面前两篇分别完成了栈、队列的基础实现以及 LeetCode 225「用队列实现栈」。到了这一篇开始真正进入队列本身的经典实现问题如果底层使用数组怎样避免队首出队之后前面的空间越来越浪费这就是循环队列要解决的核心问题。普通数组队列如果只让rear一直向后移动即使前面的元素已经出队只要rear到达数组末尾看起来就无法继续插入了。比如容量为 5 的顺序队列下标 0 1 2 3 4 初始入队5个元素 [ 10 ][ 20 ][ 30 ][ 40 ][ 50 ] ↑ ↑ front rear 连续出队3个元素后 [ × ][ × ][ × ][ 40 ][ 50 ] ↑ ↑ front rear前面明明已经空出了 3 个位置却因为 rear 走到了数组末尾就判定“满了”无法继续插入新元素。这种“物理空间有空位但逻辑上认为溢出”的现象就叫做假溢出。循环队列的核心思路非常直白让数组下标走到末尾以后重新回到开头把已经释放的前置空间继续利用起来把线性数组“掰成一个环”。这道题真正值得吃透的不是代码量而是三个本质问题为什么实际要申请k1个位置front和rear分别代表什么为什么所有下标移动都要取模一、题目要求LeetCode 622 要求设计一个固定容量的循环队列支持以下接口接口功能MyCircularQueue(k)创建最大有效容量为 k 的循环队列enQueue(value)向队尾插入元素成功返回 truedeQueue()删除队首元素成功返回 trueFront()获取队首元素队空返回 -1Rear()获取队尾元素队空返回 -1isEmpty()判断队列是否为空isFull()判断队列是否已满队列依然遵循 FIFO先进先出原则区别只是底层数组被逻辑上首尾相连地使用。二、核心方案牺牲一个位置区分队空与队满在正式讲标准写法之前先提一种最直观的 “笨办法”不用取模全靠if手动判断边界。比如数组长度是 4rear向后移动时如果rear还没到末尾就rear如果rear已经是最后一个下标了就让它直接回到 0判满也是同理分情况写正常情况rear 1 front就满了边界情况rear已经在 0而front在数组最后一位也算满了同样取队尾、移动 front 也都要写两套逻辑处理边界。这种写法思路最直白对着特殊情况一条条补if就行但缺点也很明显每个操作都要写分支判断代码冗余、容易漏边界本质就是把 “环形回绕” 的逻辑拆成了多个 if 手动处理。而后面要讲的取模写法其实就是用一个数学公式把这些分支统一了起来。循环队列有一个绕不开的经典矛盾 如果只靠front和rear两个下标当front rear时我们无法区分当前队列是空还是满。举个例子队空时所有元素都出队了front 和 rear 最终会重合队满时所有位置都存满了rear 绕一圈回来也会和 front 重合单靠两个下标两种状态共用同一个表达式必然产生歧义。解决这个问题有两种主流思路额外增加一个size变量记录当前元素个数用size0判空、sizek判满主动牺牲一个存储位置多开一格空间用“rear 再走一步就撞上 front”表示队满本篇采用最经典、也最适合理解环形下标的第二种方案用户要求容量为 k数组实际开辟k 1个位置其中最多只存 k 个有效元素多出来的 1 格只用来区分空满状态不存放有效数据。由此可以得到两个非常清晰的判断规则队空front rear队满(rear 1) % (k 1) front没有歧义也不需要额外维护计数变量。三、结构体设计先固定 front 和 rear 的语义我们统一语义typedef struct { int* arr; // 底层动态数组 int front; // 当前队首元素的下标 int rear; // 下一个可插入位置的下标不是队尾元素下标 int k; // 用户指定的最大有效容量 } MyCircularQueue;front永远指向当前第一个有效元素rear永远指向下一个可以插入新元素的空位举个直观例子数组内容[ 10 ][ 20 ][ 30 ][ ][ ] 下标 0 1 2 3 4 ↑ ↑ front rear此时队首元素 arr[front] 10队尾元素是 30位于rear的前一个位置下一个新元素应该放在下标 3也就是rear指向的位置这个语义一旦固定后面所有公式都可以顺着推导出来不需要死记硬背。四、为什么一定要取模取模运算%是实现“环形”的核心手段。物理上的数组是线性的下标只能从 0 到 n-1 单向增加但逻辑上我们要让它首尾相连下标走到末尾后能自动跳回开头。假设数组实际长度是 4k3k14我们希望下标按这个规律循环0 → 1 → 2 → 3 → 0 → 1 → 2 ...这个效果刚好可以通过(下标 1) % 数组长度实现。比如当前 rear 3向后移动一位rear (3 1) % 4; // 计算结果rear 0下标就从数组末尾跳回了开头完成了一次“回绕”。所以取模不是炫技它的作用非常纯粹用数学方式把线性数组的下标映射成逻辑上的环形队列。五、六个核心操作逐个拆解5.1 初始化MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj-k k; obj-arr (int*)malloc(sizeof(int) * (obj-k 1)); obj-front 0; obj-rear 0; return obj; }初始化时 front 和 rear 都为 0满足front rear表示队列为空。 注意数组开辟的是k1个空间而不是 k 个。5.2 判断队空bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj-front obj-rear; }我们已经把“下标重合”专门定义为空状态判空直接判断即可时间复杂度 O(1)。5.3 判断队满bool myCircularQueueIsFull(MyQueue* obj) { return (obj-rear 1) % (obj-k 1) obj-front; }可以理解为如果 rear 再往前走一步就会碰到 front说明再插入就会破坏“留一格”的规则队列已经满了。 取模是为了处理 rear 在数组末尾的边界情况。5.4 入队bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)){ return false; } obj-arr[obj-rear] value; obj-rear (obj-rear 1) % (obj-k 1); return true; }因为 rear 本身就是“下一个可插入位置”所以步骤一定是把新元素写入 rear 指向的空位rear 向后移动一位继续指向下一个空位顺序不能搞反这完全由我们定义的 rear 语义决定。5.5 出队bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)){ return false; } obj-front (obj-front 1) % (obj-k 1); return true; }出队不需要真的清空原队首的数据只需要把 front 向后移动一位让原来的位置退出有效区间即可。 和顺序栈 pop 只移动 top 不清空数组是同一个思想数据是否有效由边界指针决定而不是看内存里的旧值有没有被抹掉。5.6 获取队首int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)){ return -1; } return obj-arr[obj-front]; }front 本身就指向第一个有效元素直接返回即可。六、Rear 为什么比 Front 多一步计算这是本题最容易写错的地方但顺着语义推导其实非常自然。因为 rear 指向的是“下一个空位”不是队尾元素所以真正的队尾一定在 rear 的前一个位置。正常情况下写rear - 1没问题但如果 rear 刚好在 0 号位置rear - 1就变成了 -1数组没有负下标。所以要先加上一整个数组长度保证数值为正再取模回绕(rear - 1 数组长度) % 数组长度完整代码int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)){ return -1; } int pos (obj-rear - 1 (obj-k 1)) % (obj-k 1); return obj-arr[pos]; }举个边界例子验证k 3数组长度 4 rear 0代入计算(0 - 1 4) % 4 3 % 4 3说明队尾元素在下标 3 的位置正好完成了跨边界的回绕。七、完整 LeetCode AC 代码#include stdlib.h #include stdbool.h typedef struct { int* arr; int front; int rear; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj-k k; obj-arr (int*)malloc(sizeof(int) * (obj-k 1)); obj-front 0; obj-rear 0; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj-front obj-rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj-rear 1) % (obj-k 1) obj-front; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)){ return false; } obj-arr[obj-rear] value; obj-rear (obj-rear 1) % (obj-k 1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)){ return false; } obj-front (obj-front 1) % (obj-k 1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)){ return -1; } return obj-arr[obj-front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)){ return -1; } int pos (obj-rear - 1 (obj-k 1)) % (obj-k 1); return obj-arr[pos]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj-arr); free(obj); }八、用一个完整例子看懂“循环”我们用 k3实际数组长度 4完整走一遍流程直观感受环形效果。初始状态[ ][ ][ ][ ] ↑ front rear依次入队 10、20、30[10][20][30][ ] ↑ ↑ front rear此时有效元素已经有 3 个虽然还有一个空位但必须保留用于区分空满因此队列已满。执行一次出队[10][20][30][ ] ↑ ↑ front rear10 被逻辑删除front 后移一位。再入队 40 元素写入 rear 指向的下标 3[10][20][30][40] ↑ frontrear 向后移动一位通过取模回到 0rear ↓ [10][20][30][40] ↑ front此时逻辑上的有效队列是20 → 30 → 40虽然物理数组里 40 在 20 前面但从环形顺序看完全连续。 这就是循环队列最核心的魅力物理线性逻辑环形。九、复杂度分析这套实现没有任何遍历操作所有接口都是常数时间接口时间复杂度enQueueO(1)deQueueO(1)FrontO(1)RearO(1)isEmptyO(1)isFullO(1)空间复杂度为 O(k)需要申请与容量成正比的数组。相比链式队列它没有额外的指针开销不需要频繁申请释放节点连续内存对 CPU 缓存也更友好代价是容量固定无法动态扩容。两种实现没有绝对优劣只是用不同的存储结构换取不同的特性。十、拓展对比链式实现队列的思路与局限讲完数组方案自然会有一个疑问队列本来就可以用链表实现那用单链表、循环链表、双向链表来做这道题行不行答案是都能实现队列功能但都不是本题最贴合考点、最省事的方案这里简单梳理一下。10.1 普通单链表实现队列思路很直接维护head队首、tail队尾两个指针再加一个size计数控制最大容量 k。入队尾节点后插入新节点tail 后移出队删除头节点head 后移取队首/队尾直接访问 head/tail 节点的值它的优点是天然动态扩容不存在假溢出头尾操作都是 O(1)取队尾也很方便。 但麻烦的点也很明显边界处理繁琐空队列、仅一个节点时头删后 tail 指针要同步置空很容易漏写每个节点带next指针空间开销比数组大节点内存不连续CPU 缓存命中率低最关键的是它只是普通链式队列完全没有体现“循环复用空间”的核心和 622“循环队列”的考点关联度很低10.2 循环单链表也就是让尾节点的next指向头节点形成一个环甚至可以只存一个tail指针用tail-next表示队首。名字里虽然带“循环”但对于只操作两端的队列来说它并没有带来实质优势反而让空队列、单节点的边界判断更绕属于形式上循环实用性不如普通单链表双指针。10.3 双向链表每个节点同时带prev和next指针头尾各一个指针。 优点是两端插入删除都绝对 O(1)边界处理更顺手但缺点也很突出实现最繁琐每个节点多一个指针空间开销最大对于队列这种“尾部入、头部出”的结构单链表已经能做到 O(1)双链表属于能力过剩增加了不必要的复杂度小结链式实现更适合容量不确定、动态增减的通用队列场景但对于 622 这种固定容量、核心考察“环形空间复用思想”的题目数组循环队列才是最贴合题意、最能体现考点的标准解法。十一、再拓展能不能用两个栈实现这道题学过“用队列实现栈”之后很多人会自然反问能不能反过来用两个栈实现队列答案是完全可以实现队列语义但它同样不是 622 这道题最自然、最贴合考点的方案。11.1 双栈方案的基本思路用两个栈分工协作inStack专门接收入队所有 push 直接压入此栈outStack专门处理出队、取队头为空时把 inStack 全部元素倒入栈顶即为队头两次 LIFO 叠加就能得到 FIFO 的效果这个方案没有取模运算工程中还可以直接复用已有的栈模块代码复用性很强。11.2 为什么它不适合 622 这道题首先要明确双栈可以实现完整的队列功能并不是“做不到”。 但 622 有一个非常关键的接口——Rear()获取队尾元素这恰恰是纯栈接口的天然短板。元素还在 inStack 时队尾就是栈顶O(1) 可取元素全部迁移到 outStack 后逻辑队尾跑到了outStack 的栈底。而标准栈只能访问栈顶无法直接读取栈底当然我们可以通过额外维护一个backVal缓存变量把 Rear 也优化到 O(1)。但这样一来实现重点就从“双栈模拟 FIFO”变成了“靠额外变量补全接口”偏离了 622 本身的考察核心。622 题名叫“设计循环队列”它真正想考察的是数组空间如何循环复用front/rear 如何回绕空满状态如何区分取模如何构造环形下标这些点恰恰是数组循环队列最直接、最贴切的内容。11.3 那双栈方案什么时候最香如果题目不需要获取队尾只要求入队、出队、取队头、判空双栈方案就会变得非常优雅。 它的迁移逻辑有很巧妙的优化点只有 outStack 为空时才整体迁移每个元素最多被搬运一次能做到摊还 O(1)。而这正好就是下一道经典题的内容。十二、本地工程化拆分代码仓库数据结构/8.19 LeetCode 622. 设计循环队列 · Luminous/Code_2026 - 码云 - 开源中国LeetCode 提交时单文件即可本地我依然按模块化习惯拆分LeetCode622_CircularQueue/ ├── circular_queue.h ├── Arr_circular_queue.c └── main.ccircular_queue.h结构体定义与接口声明Arr_circular_queue.c环形数组核心实现main.c本地测试用例特别建议重点测试 rear 从数组末尾跳回 0 的边界场景这才是真正验证“循环”有没有写对的关键。十三、写在最后LeetCode 622 代码不长但它是一道非常适合锻炼“下标设计思维”的题。真正该记住的从来不是(rear 1) % (k 1)这个公式而是先把每个变量的语义定义清楚front 当前队首元素位置rear 下一个可插入位置变量含义定死之后判空、判满、入队、出队、取队尾的公式全都是自然推导的结果。这也是学习数据结构很重要的一个思路先定义清楚“每个变量代表什么”再去写代码而不是先写代码再去猜变量的含义。下篇预告上一题我们用两个队列模拟了一个栈下一篇我们完全反过来用两个栈模拟一个队列。栈和队列专题四LeetCode 232. 用栈实现队列我们会拆解双栈的分工逻辑、元素迁移时机以及为什么单次 O(n) 的搬运最终能做到摊还 O(1)。