LeetCode 上“设计循环队列”这道题我刷了不止一遍。第一次写的时候觉得很简单不就是数组加两个指针吗结果一提交就栽在isFull的判断上后面又接连踩了数组越界、队空取值没加保护、Rear()取错位置这几个坑。后来才明白这道题考的不是你会不会用队列而是你对“环形数组 两个指针 容量边界”这套组合拳有没有真正吃透。也正因为这个原因我一直觉得这道题是数据结构设计题里性价比极高的入门题。它不涉及复杂的贪心、动态规划却把工程里最常用的环形缓冲思想塞得满满当当。操作系统里的环形缓冲区、音视频播放的 jitter buffer、日志系统的滚动写入底层思路跟这题几乎一模一样。把它吃透了再去碰LRU Cache、用栈实现队列、用队列实现栈这些设计题会顺手很多。题目本身没有给任何多余干扰项就是让你实现一个定长的循环队列支持入队、出队、取队首、取队尾、判空、判满六件事。适合刚开始刷题想巩固数据结构的同学也适合准备面试前快速过一遍环形缓冲原理的开发者。接下来我把完整的解题思路、两种实现方案、边界条件的坑以及我从这道题里延伸出来的刷题方法一次说清楚。1. 题目拆解这道题到底在考什么1.1 设计题的考察逻辑LeetCode 里的设计题通常有一个特点算法难度不深但对“数据结构的组合理解”要求很细。最常见的例子是实现getMin()的栈、用两个队列模拟栈、用两个栈模拟队列以及本题的循环队列。这类题目的信噪比其实很高。面试官选这类题时看的不是你能不能背出某个奇技淫巧而是你对“指针指向的含义”“容量的边界”“满和空的状态转移”有没有天然的习惯。很多人刷题只盯着算法标签觉得设计题“简单”但真到白板写代码的时候head、tail、size三者一交叉很快就开始乱套。循环队列就是这中间非常典型的试金石——它恰好位于“基础数据结构”和“工程实践”的交界地带。1.2 循环队列要解决的四个问题循环队列本质上解决的是普通数组当队列用时的空间浪费问题。如果用数组实现普通队列每次deQueue都移动head前面空出来的位置永远没法再用数组空间只会越来越少。循环队列通过“下标取模”的方式让head和tail在数组范围内绕圈把空间复用起来。实现过程中必须回答四个问题空队列和满队列分别怎么判断tail指向的是“当前末尾元素”还是“下一个空闲位置”入队之后tail怎么移动、出队之后head怎么移动当tail绕回数组开头时取队尾元素的下标怎么算这四个问题就是整道题的骨架。代码只有几十行任何一个地方理解偏差输出就完全不对。而 LeetCode 判题系统会把这些边界情况全部覆盖到所以想靠“碰巧对”是过不了的。1.3 题目要求背后的工程语义这道题的函数签名也值得注意。enQueue和deQueue返回bool而不是void不是故意刁难而是环形缓冲在实际使用中满了就写入失败、空了就弹出失败本来就是非常正常的业务分支。比如日志系统里缓冲区写满了写入函数就要告诉调用方“你现在需要做降级处理”这时false就是一个明确的信号。理解了这个语义写代码时就会自然养成习惯任何修改队列状态的函数第一行先做状态判断。这个习惯放到工程里就是“先校验再操作”放到并发场景里还会额外加上锁或者 CAS 操作。刷这道题练出的防御式编程习惯比会背一道题本身有价值得多。2. 核心难点环形下标与满空状态判断2.1 环形下标的本质是取模环形数组有个核心公式所有索引移动都可以归结为next (current 1) % capacity prev (current - 1 capacity) % capacity之所以要加上capacity再取模是因为在某些语言里负数的取模运算结果不会是预期的正数索引。Java 里(0 - 1) % 5的结果是-1直接作为数组下标就会抛异常加上一个长度再取模(0 - 1 5) % 5 4才能安全绕回数组末尾。你可以用钟表来理解12 点之后过 1 小时是 1 点这就是“下标”绕回起点而“9 点前推 2 小时是 7 点”对应(9 - 2 12) % 12 7。环形队列在数组上做绕圈和钟表的时间运算是一模一样的数学结构。2.2 判空判满的两条路线循环队列判空和判满的方式决定了整个实现的风格。常见的有两条路线。路线一维护一个 size 计数器每次入队size出队size--。判空看size 0判满看size capacity。这个方案最直白也最不容易出错因为没有歧义head和tail指向哪里都无所谓队列到底有多少元素全看计数器。路线二不维护 size牺牲一个存储位让tail始终指向“下一个空闲位置”并规定当tail再往前走一步就和head相等时说明数组已经满了。用公式表示就是isEmpty: head tail isFull: (tail 1) % capacity head这个方案省了一个字段代码更简洁但实际可用容量变成了capacity - 1。举个例子初始化capacity 5最多只能存 4 个元素。如果不理解这个设计很容易在测试k 1的队列时空想为什么只能入队一次两条路线各有拥趸。我自己的建议是刷题阶段优先用size计数法因为可读性好、边界容易推理面试时如果被问“能不能优化或者不用 size 怎么实现”再切换到预留一个位置的方案说明你能从“空间换简单”和“空间换时间”两个维度权衡设计。2.3 指针语义必须先定死写代码之前最忌讳的是head和tail的含义没有在心里定死。一旦写的过程中摇摆后面全是错乱。我推荐采用的定义是指针指向含义head队列中第一个有效元素的下标tail队列中下一个空闲位置的下标在这个定义下Front()直接返回q[head]Rear()返回q[(tail - 1 capacity) % capacity]。enQueue是在q[tail]处写入新值写完后tail (tail 1) % capacitydeQueue是把head (head 1) % capacity往后推一位表示这个元素被“逻辑删除”了。这里有个很容易被搞错的点出队时不需要真的去清理数组里的旧值。因为head已经越过它了只要队列判空逻辑不出错旧值永远不会再被Front()或Rear()读到。这算是一个典型的“逻辑删除”思维跟操作系统里删除文件时只改索引、不清数据块的做法是同一个思路。2.4 这道题的边界测试点LeetCode 的判题用例主要集中在这些边界上初始化后直接调Front()和Rear()应该返回-1。空队列里执行deQueue()应该返回false而不是抛异常。容量为k的队列连续入队k次后第k1次必须返回false。交替入队出队验证环形下标能否跨过数组边界。队列满后Front()仍然是队首值Rear()仍然是最后一次成功入队的值。这些测试点看起来简单但只有在代码里先有isEmpty()和isFull()的完整判断才能一一通过。自己练习时如果只是“主流程跑通就算过”很容易漏掉这些隐藏条件。3. 数组实现最直接、最容易复现的方案3.1 完整可运行的参考代码我先把最常用的数组方案写出来这个实现基于size计数器思路清晰适合作为模板记忆。语言我用 C但逻辑可以照搬到任何语言。class MyCircularQueue { private: vectorint q; int head; int tail; int cnt; int cap; public: MyCircularQueue(int k) { q.resize(k); head 0; tail 0; cnt 0; cap k; } bool enQueue(int value) { if (isFull()) return false; q[tail] value; tail (tail 1) % cap; cnt; return true; } bool deQueue() { if (isEmpty()) return false; head (head 1) % cap; cnt--; return true; } int Front() { if (isEmpty()) return -1; return q[head]; } int Rear() { if (isEmpty()) return -1; return q[(tail - 1 cap) % cap]; } bool isEmpty() { return cnt 0; } bool isFull() { return cnt cap; } };3.2 逐段拆解每个成员变量为什么存在q数组存放队列元素。初始化时直接分配好k个位置后续不动态伸缩。这是循环队列的“定长”语义决定的也是它和普通队列最大的区别。head队首下标。所有人都知道Front()要看它但容易忽略的是出队时它是在“原地向后移动”而不是让后面的元素往前搬。之所以能这么做是因为循环队列本身就是环形逻辑数组下标到了末尾会绕回开头。tail我把它定义成下一个空闲位置。每次入队的一瞬间元素不是放在tail指向的位置前面而是就放在tail指向的位置。这一点如果搞反Rear()就会取到错误的值。cnt当前元素数量。它让isEmpty()和isFull()变得非常直白。实际工程中如果你希望尽量少维护一个字段可以用head tail判空、(tail 1) % cap head判满但那就会牺牲一个数组位置。这里选择多维护一个cnt换取逻辑简单度我认为对于刷题和大多数应用场景都是划算的。3.3 关键操作的执行细节入队enQueue分三步先判满然后在q[tail]处写入最后移动tail。这里写入和移动的顺序不能换一旦先把tail移动了再写就会写到错误的位置。出队deQueue只需要移动head。注意我们不会真的去把q[head]里的值清掉这是它的“逻辑过期”阶段。如果后续队列再次写入这个位置新值直接覆盖旧值就行。Front()和Rear()最大的坑在于Rear()。因为tail指向的是下一个空位所以“最后一个有效元素”实际上是tail的前一个位置。下标公式是(tail - 1 cap) % cap不要丢掉 cap这一步。举个例子tail 0时前一个位置应该是cap - 1如果你直接写tail - 1那就变成了-1成了非法下标。3.4 面试时能主动讲出来的优化点如果面试官要求“不能使用 size 字段”你可以马上切换到第二种实现只需要改动三处isEmpty判断head tailisFull判断(tail 1) % cap head构造函数里可以清空数组或做任意初始化。改动之后需要注意所有方法里“当前容量”的概念变了传入k实际能同时存在的最大元素是k - 1。LeetCode 官方解法里很多都这样写但初学者照着敲的时候往往没明白为什么k 2只能入队一次成功。这一步理解到位了面试官再问“有没有办法既不浪费一个位置又不用size字段”你就可以顺势补充第三种方案用head和tail再加一个bool标记“上次操作是写入还是删除”但工程上维护起来更复杂多数情况下不如直接用size字段。说到底这道题最好的回答方式不是“我会写一种标准答案”而是“我知道这两种方案各自的空间代价和代码复杂度并能根据场景选一种”。4. 链表实现换个数据结构解同一道题4.1 为什么链表也能做却不一定更优很多人一看到“循环”两个字就幻想着用循环链表去模拟。其实链表实现的核心仍然是“定长 计数器”只是把数组换成了动态节点。链表方案的优点是不需要担心下标取模写起来非常“顺拐”不需要记忆% cap那一堆公式。缺点是每个节点都要动态分配内存缓存不友好实际操作里性能通常不如连续数组。如果你在工程中看到一个“循环队列”绝大多数底层的首选是数组而不是链表。不过这道题作为设计题链表是一份合格的备选答案能体现你不只会一种存储结构。4.2 链表版本参考代码struct Node { int val; Node* next; Node(int v) : val(v), next(nullptr) {} }; class MyCircularQueue { private: Node* head; Node* tail; int cnt; int cap; public: MyCircularQueue(int k) { head nullptr; tail nullptr; cnt 0; cap k; } bool enQueue(int value) { if (isFull()) return false; Node* node new Node(value); if (isEmpty()) { head node; } else { tail-next node; } tail node; cnt; return true; } bool deQueue() { if (isEmpty()) return false; Node* tmp head; head head-next; if (head nullptr) tail nullptr; delete tmp; cnt--; return true; } int Front() { if (isEmpty()) return -1; return head-val; } int Rear() { if (isEmpty()) return -1; return tail-val; } bool isEmpty() { return cnt 0; } bool isFull() { return cnt cap; } };4.3 链表版本的细节与对比这个版本的tail不需要什么(tail - 1)的公式因为tail直接指向最后一个节点Rear()直接返回tail-val。它用cnt作为判满和判空的依据所以不需要像之前那样在判满时牺牲容量。需要注意一个细节当队列删空时head已经变为nullptr这时必须手动把tail也置空否则下次入队时enQueue判断isEmpty()为真走的是head node但旧的tail还残留在内存里指向那个被删除的节点后续操作就错乱了。这种“删光后让两个指针同时归零”的操作是链表实现里最容易疏忽的点。如果要把链表改成真正的“环”可以在容量满时让tail-next指向head。但说实话对于这道题维护一个普通定长链表加cnt已经能覆盖全部功能要求强行成环反而增加了内存管理的复杂度。工程实现也一样能满足语义、逻辑简洁、性能过关就是好设计不需要为了“看起来很技术”而去过度设计。5. 常见问题与排查技巧实录5.1 我刷这道题时犯过的五个经典错误第一个错误是出队前置判断忘写。空队列deQueue()被调用时如果没有isEmpty()保护head (head 1) % cap会把本来正确的head推向错误位置将来即使再入队队首也永远不对。LeetCode 判题系统里这个用例几乎是必测的所以一忘就报错。第二个错误是**Rear()返回位置错误**。我一开始把tail理解为“当前队尾元素下标”入队后tail就被赋值为新元素的下标也确实返回对了。结果某次把tail改成“下一个空位”之后忘了同步更新Rear()的返回逻辑导致第二次入队后取到的还是旧值。根源就是对指针语义没有保持全程一致。第三个错误是没处理k 1的特殊情况。用预留一个位置的方案时capacity 1意味着实际容量为 0这显然不符合题意。用size计数器方案在任何容量下都天然不踩这个坑这也是我推荐它的一个现实原因。第四个错误是**tail和head初始化没有归零**。如果你用了构造函数传参但忘记初始化这两个字段结果是完全随机的。这个问题在本地运行时不一定爆因为内存里碰巧是 0但在判题环境里就是数组越界或者返回随机值。第五个错误是判满条件写成cnt 1 cap。稍微手滑就会把容量计算错。更稳的写法是cnt cap因为它直接复用了当前元素数量不会多出一个off-by-one的隐患。5.2 排查思路从“出错”到“定位”的路径遇到提交失败我建议按下面顺序排查而不是一头扎进代码里乱猜先看是哪个函数报错。越界异常通常出在索引计算重点看% cap有没有加、 cap有没有写。返回-1时机不对重点看Front()、Rear()有没有先判空。提交结果里false/true反了重点看isFull()和isEmpty()用的是不是同一个计数基准。再检查指针语义边界。自己脑中复述一遍head指向什么tail指向什么然后把整个类里所有用到head、tail的地方全部标注出来看看有没有哪个地方默认了不同含义。最后做手算用例。找一个k 3的实例依次执行enQueue(1)enQueue(2)enQueue(3)enQueue(4)期望 falsedeQueue()enQueue(4)期望成功Front()期望 2Rear()期望 4这个过程走一遍大部分指针错乱都能暴露出来。刷这道题最大的收获不是最终跑通而是建立起“我可以用一个最小用例在纸上把状态转移全程推出来”的能力。5.3 一个容易忽略但实际很常见的真实场景这类队列在工程中经常配合“覆盖写”使用。比如日志缓冲区满了以后我们不希望阻塞而是希望直接覆盖最旧的数据。这个时候isFull()的判断就不是“拒绝入队”而是“要先deQueue再enQueue”或者更紧凑些直接让tail覆盖head指向的旧数据然后head和tail一起前移。这个场景在 LeetCode 里不会考但它是理解循环队列价值的关键环形缓冲不是为了“存满就不许写”而是在“满了之后还能高效滚动”。做题的时候如果只追求通过很容易把这层工程语义丢掉。所以我在刷完基础题后建议你拓展一下“允许覆盖的变体”亲手在现有代码上改一版不仅加深印象面试被追问时也能多聊几句。6. 从这道题延伸出去的刷题闭环思路6.1 环形序列思路可以用在哪类题循环队列背后的(i 1) % n思想在很多高频题里都会出现。做过的朋友可能已经发现滑动窗口、约瑟夫环、轮转数组、设计停车场全都涉及“下标绕回”的数学结构。LeetCode 里常见的热搜题比如腐烂的橘子、基本计算器、爱吃香蕉的狒狒表面看是 BFS、栈、二分答案但底层都有“状态按某种规则流转”的模型。刷题最忌讳的是“只见题不见类”。我个人的做法是每做完一道题写一行关键词标明它背后绑定了哪些数据结构或数学结构。今天做循环队列我就给自己记了一笔“环形下标、单调循环、缓冲区覆盖”。过几天遇到一个旋转数组题看到%运算能马上联想到这题知识就开始连接成网了。6.2 和同类设计题放在一起对比推荐把下面几道题作为一组对比训练题目类型核心数据结构和循环队列的共通点用两个栈实现队列双栈用“状态转移”模拟队列语义用队列实现栈双队列用不同结构模拟 LIFO/FIFOLRU Cache哈希表 双向链表定长 淘汰策略的容器设计设计循环双端队列数组 双指针在头部和尾部同时操作做完循环队列再做一组对比你会发现自己对“设计题”的整体感觉上了一个台阶。因为这些题的共同点是数据结构的组合方式比算法本身更关键边界条件比主流程更值得花时间。这和纯算法题“暴力→优化”的刷法差别很大。6.3 我个人的刷题建议如果你还在刷题初期不要急着追求一天刷十道题而是一道题彻底吃透比你十道题囫囵吞枣要高效得多。所谓彻底吃透我定义为三条标准第一不看题解能独立写出正确解法。看题解找到思路后把页面关掉从头开始写直到所有边界用例通过。第二能用一句话概括核心难点。对循环队列就是“用取模实现环形下标用计数器区分空和满。”能说出来说明你真的抓住了重点。第三能写出至少一种变体方案。比如这题里从“数组 size”切换到“预留一个位置”从普通定长链表切换到“允许覆盖”的滚动缓冲。能把方案迁移才叫掌握了而不是背会了。最后再分享一个小的实操经验我刷这类设计题会刻意先画一张状态表把空队列、部分填充、满队列三种状态下的head、tail、size全部写出来。这道题我做三遍之后发现每次重新写的时候画状态表这一步比直接写代码更有用因为它强制我把模糊的直觉变成精确的约束。如果你现在卡在某个测试用例过不去不妨也停下来先把状态表画出来大概率一眼就能定位问题出在哪里。