如果你在准备面试拿到“循环队列怎么实现”这道题恭喜你这是一道性价比极高的常考题——前提是你真把它想明白了。我第一次在美团一面碰到这题时第一反应是“教科书上的数组队列改一改就完事”结果在“队空和队满如何区分”这个点上卡了壳。后来复盘才意识到面试官拿着循环队列看的远远不止你会不会背一个环形数组而是数据结构基本功、边界条件敏感度、以及临场写代码的规范性。循环队列的核心价值在于用固定大小的数组实现高效复用空间的先进先出FIFO结构。它解决的是普通数组队列“出队后空间无法复用”的假溢出问题也是操作系统、网络框架、并发编程里环形缓冲区Ring Buffer的底层基础。这篇文章我会从原理讲起逐步手写代码再把面试中常见的连环追问拆开揉碎最后分享我实际踩过的坑。不管你是准备校招、社招还是想真正搞懂环形队列这篇都值得收藏。1. 面试官到底在问什么1.1 一道“简单题”背后的三个核心考点先说一个扎心的真相循环队列的代码量很少核心逻辑不超过20行但面试通过率并不高。为什么因为这道题考察的不只是“会写”而是在高压环境下你能不能把状态边界处理干净。我总结了三个隐藏考点数据结构基本功是否理解队列的 FIFO 特性知道入队出队分别在两端操作。环形回绕思维是否能用取模运算把线性数组“弯成”逻辑上的环。边界条件处理队列空、满时front 和 tail 指针处于什么状态如何处理歧义。很多候选人能写出 enqueue/dequeue 的基本逻辑但一问到“怎么判断满”就开始慌。要么写错条件要么浪费一个存储位置时没跟面试官解释清楚原因。这恰恰是面试官最想听的部分。1.2 普通数组队列的“假溢出”问题要理解循环队列为什么存在必须先看普通数组队列的痛点。假设我们用数组实现一个队列初始 front 0rear 0。入队时写 data[rear]rear出队时读 data[front]front。一开始一切正常但当执行了若干次出队后front 会不断后移数组前部的空间明明还空着却永远无法存放新数据。当 rear 走到数组末尾时即使数组前部还有大量空位队列也“装不下”了。这就是假溢出物理空间有剩余逻辑上却无法使用。有人说那我把元素整体往前搬不就完了可以但搬移一次就是 O(n) 的代价。如果队列频繁入队出队这种搬移会导致性能雪崩。循环队列的思路非常直接让 rear 走到数组末尾后通过取模回到起点把数组当成一个首尾相接的环。这样一来出队释放的空间可以被后续入队立刻复用入队出队都保持在 O(1) 时间复杂度。2. 环形结构设计的核心原理2.1 数组怎么“弯”成环取模回绕数组本身是线性连续的想让它在逻辑上成环靠的是一个数学操作——取模。假设数组容量为 n当前尾部指针为 rear那么下一个写入位置是rear (rear 1) % n当 rear n - 1 时rear 1 n对 n 取模后变回 0这就实现了从数组尾端到首端的跳转。你可以把它类比成钟表时针走到 12 点后下一个时刻不是 13而是回到 1。或者类比操场跑道跑完一圈后你回到起点只不过开始了下一圈。逻辑上的“环”并不是空间真的弯曲了而是下标计算规则变了。同理出队操作也使用同样的取模方式front (front 1) % n这里有一个细节容易被忽略访问队尾元素时不能直接取 data[rear]因为 rear 指向的是下一个可用位置而不是最后一个元素的位置。最后一个元素的位置是lastIndex (rear - 1 n) % n之所以要加 n 再取模是因为当 rear 0 时rear - 1 -1直接取模在多数语言里会得到负数或错误的下标。这是新手最容易踩的坑之一。2.2 判空与判满为什么要“浪费”一个存储位一个环形数组如果 front 一直追着 rear 走会出现一个经典难题当 front rear 时队列到底是空还是满假设初始空队列 front rear 0。现在不停入队rear 一路前进直到绕一圈后 rear 再次等于 front。此时数组被填满了但按判空条件 front rear它会被误判为空。等于说“空”和“满”变成了同一个状态完全无法区分。标准的解决方案是在数组中人为保留一个空位让 rear 最多走到 front 前一个位置就停下来强制制造一个“永远不让 rear 追上 front”的边界。于是判空front rear判满(rear 1) % n front也就是说容量为 n 的数组实际最多存储 n - 1 个元素。这个“浪费的一格”不是缺陷而是为了消除状态二义性付出的成本。举个具体例子数组容量为 5初始化 front 0rear 0。陆续入队 A、B、C、D 四个元素后rear 4。此时 (41)%5 0等于 front队列判满。虽然 data[4] 是空的但设计上不会再允许入队除非先出队腾出位置。提示面试时如果你主动说出“这种方案会浪费一个空间”并且紧接着给出“另一种方案是增加 size 计数器”面试官的好感度会明显提升。因为这表明你不仅能实现还能权衡多种设计。2.3 不浪费空间的两种替代设计如果业务场景要求容量必须用满有三种办法绕开“浪费一格”的问题增加 size 字段维护一个整数 count入队加 1出队减 1。判空用 count 0判满用 count capacity。此时 front rear 时根据 count 判断具体状态不再有歧义。增加 boolean 标志位记录最后一次操作是入队还是出队。如果最后一次是入队且 front rear则队满最后一次是出队且 front rear则队空。这种方法不太直观容易出错但可以避免维护计数器。不存储元素借助哨兵节点链表实现时保留一个 dummy 节点也可以消解空满歧义不过数组场景下更常用的是 size 方案。我个人的建议是基础版本用“浪费一格”的方式因为这是教科书标准实现面试官最熟悉升级版本用 size 方案因为后面做动态扩容时count 是必不可少的信息一套代码可以复用。3. 手撕循环队列从基础版到扩容版3.1 面试笔试版固定容量的循环队列面试时最稳妥的做法是先明确告诉面试官你要用“数组 预留空位”的方式实现然后快速写出代码。这里我给出 Java 版本和 Python 版本逻辑完全等价。Java 实现class MyCircularQueue { private int[] data; private int front; private int rear; private int capacity; public MyCircularQueue(int k) { this.capacity k; this.data new int[k]; this.front 0; this.rear 0; } public boolean enQueue(int value) { if (isFull()) { return false; } data[rear] value; rear (rear 1) % capacity; return true; } public boolean deQueue() { if (isEmpty()) { return false; } front (front 1) % capacity; return true; } public int Front() { if (isEmpty()) { return -1; } return data[front]; } public int Rear() { if (isEmpty()) { return -1; } return data[(rear - 1 capacity) % capacity]; } public boolean isEmpty() { return front rear; } public boolean isFull() { return (rear 1) % capacity front; } }Python 实现class CircularQueue: def __init__(self, k: int): self.data [0] * k self.capacity k self.front 0 self.rear 0 def enqueue(self, value: int) - bool: if self.is_full(): return False self.data[self.rear] value self.rear (self.rear 1) % self.capacity return True def dequeue(self) - bool: if self.is_empty(): return False self.front (self.front 1) % self.capacity return True def front_value(self) - int: if self.is_empty(): return -1 return self.data[self.front] def rear_value(self) - int: if self.is_empty(): return -1 last (self.rear - 1 self.capacity) % self.capacity return self.data[last] def is_empty(self) - bool: return self.front self.rear def is_full(self) - bool: return (self.rear 1) % self.capacity self.front这段代码有几个值得在面试中主动讲出来的点enQueue 时先判满入队失败不是抛异常而是返回 false。面试官会问你“失败怎么处理”你要表达出“定长缓冲场景下满了就是满了由调用方决定阻塞、丢弃还是扩容”。deQueue 时只需要移动 front不需要真正删除数组里的元素。旧值会留在原地等后续入队覆盖即可。这一点体现了数组队列的优雅之处。Rear() 的索引要减一再加容量取模防止负数下标这是手写时最容易漏的边界。3.2 升级版带 size 计数器的循环队列如果你觉得浪费一个空间不优雅可以在类里增加一个 count 字段。这个版本在扩容时特别好用因为 resize 过程中需要知道当前元素个数。class CircularQueueWithSize { private int[] data; private int capacity; private int count; private int front; private int rear; public CircularQueueWithSize(int k) { this.capacity k; this.data new int[k]; this.count 0; this.front 0; this.rear 0; } public boolean enQueue(int value) { if (count capacity) { return false; } data[rear] value; rear (rear 1) % capacity; count; return true; } public boolean deQueue() { if (count 0) { return false; } front (front 1) % capacity; count--; return true; } public int Front() { if (count 0) { return -1; } return data[front]; } public int Rear() { if (count 0) { return -1; } return data[(rear - 1 capacity) % capacity]; } public boolean isEmpty() { return count 0; } public boolean isFull() { return count capacity; } }这个版本的核心改动是用 count 变量明确记录队列中的元素数量front rear 时不再有歧义。注意 rear 的移动逻辑没有变仍然是先写后移。面试时如果你想展示自己思考更全面可以主动说“我可以用 size 字段替代预留空位的方案这样容量能 100% 利用而且实现扩容时无需额外判断当前有效元素个数。”这句话一出口基本就和其他候选人拉开差距了。3.3 再进一步支持动态扩容的循环队列如果面试官追问“队列满了怎么办”常规答案是“返回失败”。但进阶答案是“动态扩容”。扩容的思路是当 count capacity 时申请一个容量翻倍的新数组把旧数组中从 front 开始按顺序的 count 个元素搬移到新数组头部然后重置指针。为什么必须从 front 开始搬而不是从下标 0 开始搬因为循环队列中元素在数组里不一定是连续存放的例如 front 3rear 1有效元素位于下标 3、4、0 三个位置。如果直接遍历旧数组会带出脏数据。正确做法是遍历 count 次每次取 data[(front i) % capacity]。private void resize() { int newCapacity capacity * 2; int[] newData new int[newCapacity]; for (int i 0; i count; i) { newData[i] data[(front i) % capacity]; } this.data newData; this.front 0; this.rear count; this.capacity newCapacity; }搬移完成后元素在新数组的 0 到 count - 1 的位置连续存放因此 front 直接置为 0rear 置为 count。此时 count 仍然有效不需要修改。在 enQueue 方法中把“满则返回 false”改成“先扩容再入队”public boolean enQueue(int value) { if (count capacity) { resize(); } data[rear] value; rear (rear 1) % capacity; count; return true; }扩容的时间复杂度是 O(n)但只发生在队列满的瞬间。入队 n 次扩容 O(log n) 次均摊下来每次入队仍然是 O(1)。这就是动态数组的均摊分析和 ArrayList 的扩容原理一致。注意扩容前后队头元素的下标可能发生变化。如果你在外部持有“某个元素的下标”扩容后就会失效。实际应用中环形缓冲区往往会避免扩容而是通过覆盖旧数据或阻塞生产者来处理满状态。3.4 现场测试一步一步模拟运行面试时写完代码最好主动跑一组数据验证。下面我按容量为 5 的“预留空位版”手动走一遍初始化front 0rear 0数组内容 [_, _, _, _, _]enQueue(1)data[0]1rear 1内容 [1, _, _, _, _]enQueue(2)data[1]2rear 2内容 [1, 2, _, _, _]deQueue()front 1内容 [1, 2, _, _, _]逻辑上只剩 2enQueue(3)data[2]3rear 3内容 [1, 2, 3, _, _]enQueue(4)data[3]4rear 4内容 [1, 2, 3, 4, _]enQueue(5)data[4]5rear 0内容 [1, 2, 3, 4, 5]enQueue(6)(rear1)%5 11 ! front1等等这里其实要小心。第 7 步入队 5 后rear 变成 0此时第 8 步 isFull 检查条件变成 (01)%5 1而 front 1所以确实判满返回 false。但如果真的让 rear 又一次撞上 front就无法区分状态了。这个例子正好说明了为什么预留一格是对的如果不留空格第 8 步入队成功会让 rear 变成 1之后你无法判断队列是满还是空。面试时你可以用这类小例子证明代码能处理边界而不是只求“看起来能跑”。4. 面试里的连环追问不要只会背代码4.1 不直接移动数组元素是因为性能吗面试官可能会问“普通数组队列出队后把后面的元素往前搬一步不也能复用空间吗干嘛要搞得这么复杂”答案是移动元素是 O(n) 的操作。如果队列里有 100 万个元素每出队一个就要搬 99 万个元素这在高频读写场景下是不可接受的。循环队列通过指针移动实现 O(1) 出队入队空间换时间的思路在这里体现得很典型。从另一个角度说普通数组队列的“搬移”还破坏了元素的内存连续性吗其实搬移后内存还是连续的但每次搬移的 CPU 开销远大于指针加一的几百纳秒。在延迟敏感的系统里这种差异就是生死线。4.2 链表实现的队列与数组循环队列怎么选这也是高频追问。很多人只知道链表也能实现队列但说不清两者差异。链表队列的入队出队同样是 O(1)且支持无限容量动态增长。它的缺点是每个节点需要额外的指针开销内存占用更大。节点在内存中分散分布遍历时缓存不友好。频繁创建和销毁节点会产生 GC 压力。数组循环队列的优势是内存连续预分配无 GC 压力。通过下标直接定位缓存命中率高。容量可控适合固定大小的缓冲池。数组循环队列的缺点是容量固定需要提前规划。如果生产速率长期大于消费速率队列会持续打满这时要么扩容要么丢弃要么阻塞。所以面试回答可以这样组织“如果数据量波动大、没有明确的容量上限选链表更灵活如果是高频读写、对延迟敏感、容量可预估数组循环队列几乎是不二之选。Netty、Disruptor 这类高性能框架底层用的就是数组环形缓冲区。”4.3 并发场景下循环队列怎么保证线程安全这个问题能直接区分候选人是在“背题”还是在“做系统”。最简单的方案是在 enQueue 和 deQueue 方法上加synchronized让整个方法串行化。优点是正确率高缺点是吞吐量下降锁竞争激烈。更好的方案是结合业务场景单生产者单消费者SPSC生产者只修改 rear消费者只修改 front互不干扰。配合volatile修饰的读写索引和内存屏障可以在无锁情况下安全地读写。这是 Disruptor 框架的核心设计之一。此时要注意的是生产者写入的数据在更新 rear 索引前必须保证对消费者可见通常需要插入内存屏障。多生产者多消费者MPMC索引被多人争用需要使用 CAS 或锁保证原子性。Java 里可以用AtomicInteger配合自旋重试来实现一个 Lock-Free 队列但 ABA 问题和伪共享都需要考虑复杂度很高面试时点到为止即可。如果面试官只是考察基础你可以先给出synchronized版本然后主动说“如果是一读一写场景可以做到无锁核心思路是让读写双方各持有一个索引互不争抢”。这一句话就能体现你有并发意识。4.4 循环队列在真实系统里的影子很多候选人不知道这题学了有什么用。其实循环队列就是环形缓冲区在真实系统里到处都是Java ArrayDeque底层实现就是循环数组用于 deque。NettyRecycler和一些缓冲池设计中使用了环形回收思路。LMAX Disruptor高性能多线程框架核心就是 Ring Buffer。操作系统键盘缓冲区、网络驱动接收队列很多是环形队列。日志系统异步日志的缓冲队列经常设计成环形满了直接丢弃或覆盖旧日志避免阻塞业务线程。面试时如果能举出两三个这样的例子面试官会认为你不仅有代码能力还有系统架构视野。这也是“一面”中区分度很高的加分项。5. 我踩过的坑与实战建议5.1 循环队列实现的高发 Bug 清单这部分内容是我自己手写循环队列时真实踩过、也给同事 code review 时遇到过的坑列成表格帮大家对照。常见问题具体表现解决方案负下标取模错误获取队尾时使用(rear - 1) % n当 rear0 时得到负数统一写成(rear - 1 n) % n判满条件写反用front rear判断满导致空满不分预留空位时用(rear 1) % n front带 size 时用count capacity出队时没有移动 front只返回队头值但指针不动重复读到同一元素deQueue 必须更新 front并考虑是否需要清空旧引用对象类型时帮助 GC扩容时元素顺序错乱直接按数组下标搬运把脏数据也搬进去按 (front i) % capacity 循环取 count 个元素rear 指向最后一个元素还是下一个空位混淆入队写错位置队尾取值错误明确 rear 永远指向“下一个写入位置”队尾元素要减一索引循环计数时忘记取模在 enQueue 后直接 rear数组越界每次移动都用取模或者额外判断后归零5.2 如何用“对拍测试”验证你的实现面试手写代码容易紧张但如果有平时写单元测试的习惯心里会稳很多。我自己调试循环队列用的方法很简单对着标准行为写一个小测试器随机操作 结果比对。思路如下定义一个普通的ArrayDeque或者LinkedList作为“参考答案”。随机执行 10000 次入队/出队操作。每次操作后把参考答案的队列内容和我自己实现的循环队列内容逐一比对。如果中间发现不一致立刻打印当前 front、rear、容量、内部数组和操作序列。用这种“对拍”的方式10 分钟就能发现所有边界问题。写代码时还可以增加一个辅助方法把内部数组和指针状态打印出来def debug_print(self): print(front:, self.front, rear:, self.rear) print(data:, self.data) print(valid:, [self.data[(self.front i) % self.capacity] for i in range(self.count)])面试时虽然没有时间跑完整测试但你可以手动模拟几个典型场景例如队列满时入队队列空时出队绕一圈回到原点队尾元素访问等。把这些边界都说清楚基本就稳了。5.3 面试回答节奏先讲思路再写代码最后主动测试根据我经历过和模拟过的面试一个合格的回答节奏是先说场景“我用数组实现因为数组内存连续、访问快。普通数组队列会有假溢出问题所以我用取模把数组逻辑上变成环。”说明空满策略“我采用预留一个空位的方式rear 追上 front 就判满。如果希望容量完全利用可以加一个 size 计数器。”快速写码先写核心的 enQueue、deQueue再补 isEmpty、isFull、Front、Rear。主动跑数据手动模拟两个用例展示边界处理。应对追问如果面试官问满了怎么办给出扩容方案如果问线程安全给出 synchronized 到无锁优化的思路。这套节奏最实用的地方在于它让面试官始终跟着你的思路走而不是被零散的代码牵着走。哪怕最终代码有小瑕疵你的思维框架也已经加分了。结尾一次真实复盘后的建议说实话循环队列这道题我后来复盘时最大的感受是越是看起来简单的数据结构越能暴露一个人写代码的底层习惯。那些能够在白板上把 front、rear 的关系讲得清清楚楚的人往往不是背过答案而是在纸上画过十几遍环形图亲手推演过指针的每一次移动。所以我的建议是拿到这道题不要只背代码动手画一个容量为 5 的环形数组把入队、出队、再入队的每一步指针变化都写下来直到你能闭着眼睛说出“什么时候 front 会追上 rear什么时候 rear 会追上 front”。如果你能做到这一步循环队列就不再是面试题而是你工具箱里一件随手能用的武器等真正遇到资源控制、缓冲设计之类的场景时你自然会想到它。 
长河君 · 2026/10/10 1:54:05 · 阅读 1.2k 循环队列实现与面试全攻略：从环形数组到边界处理
如果你在准备面试拿到“循环队列怎么实现”这道题恭喜你这是一道性价比极高的常考题——前提是你真把它想明白了。我第一次在美团一面碰到这题时第一反应是“教科书上的数组队列改一改就完事”结果在“队空和队满如何区分”这个点上卡了壳。后来复盘才意识到面试官拿着循环队列看的远远不止你会不会背一个环形数组而是数据结构基本功、边界条件敏感度、以及临场写代码的规范性。循环队列的核心价值在于用固定大小的数组实现高效复用空间的先进先出FIFO结构。它解决的是普通数组队列“出队后空间无法复用”的假溢出问题也是操作系统、网络框架、并发编程里环形缓冲区Ring Buffer的底层基础。这篇文章我会从原理讲起逐步手写代码再把面试中常见的连环追问拆开揉碎最后分享我实际踩过的坑。不管你是准备校招、社招还是想真正搞懂环形队列这篇都值得收藏。1. 面试官到底在问什么1.1 一道“简单题”背后的三个核心考点先说一个扎心的真相循环队列的代码量很少核心逻辑不超过20行但面试通过率并不高。为什么因为这道题考察的不只是“会写”而是在高压环境下你能不能把状态边界处理干净。我总结了三个隐藏考点数据结构基本功是否理解队列的 FIFO 特性知道入队出队分别在两端操作。环形回绕思维是否能用取模运算把线性数组“弯成”逻辑上的环。边界条件处理队列空、满时front 和 tail 指针处于什么状态如何处理歧义。很多候选人能写出 enqueue/dequeue 的基本逻辑但一问到“怎么判断满”就开始慌。要么写错条件要么浪费一个存储位置时没跟面试官解释清楚原因。这恰恰是面试官最想听的部分。1.2 普通数组队列的“假溢出”问题要理解循环队列为什么存在必须先看普通数组队列的痛点。假设我们用数组实现一个队列初始 front 0rear 0。入队时写 data[rear]rear出队时读 data[front]front。一开始一切正常但当执行了若干次出队后front 会不断后移数组前部的空间明明还空着却永远无法存放新数据。当 rear 走到数组末尾时即使数组前部还有大量空位队列也“装不下”了。这就是假溢出物理空间有剩余逻辑上却无法使用。有人说那我把元素整体往前搬不就完了可以但搬移一次就是 O(n) 的代价。如果队列频繁入队出队这种搬移会导致性能雪崩。循环队列的思路非常直接让 rear 走到数组末尾后通过取模回到起点把数组当成一个首尾相接的环。这样一来出队释放的空间可以被后续入队立刻复用入队出队都保持在 O(1) 时间复杂度。2. 环形结构设计的核心原理2.1 数组怎么“弯”成环取模回绕数组本身是线性连续的想让它在逻辑上成环靠的是一个数学操作——取模。假设数组容量为 n当前尾部指针为 rear那么下一个写入位置是rear (rear 1) % n当 rear n - 1 时rear 1 n对 n 取模后变回 0这就实现了从数组尾端到首端的跳转。你可以把它类比成钟表时针走到 12 点后下一个时刻不是 13而是回到 1。或者类比操场跑道跑完一圈后你回到起点只不过开始了下一圈。逻辑上的“环”并不是空间真的弯曲了而是下标计算规则变了。同理出队操作也使用同样的取模方式front (front 1) % n这里有一个细节容易被忽略访问队尾元素时不能直接取 data[rear]因为 rear 指向的是下一个可用位置而不是最后一个元素的位置。最后一个元素的位置是lastIndex (rear - 1 n) % n之所以要加 n 再取模是因为当 rear 0 时rear - 1 -1直接取模在多数语言里会得到负数或错误的下标。这是新手最容易踩的坑之一。2.2 判空与判满为什么要“浪费”一个存储位一个环形数组如果 front 一直追着 rear 走会出现一个经典难题当 front rear 时队列到底是空还是满假设初始空队列 front rear 0。现在不停入队rear 一路前进直到绕一圈后 rear 再次等于 front。此时数组被填满了但按判空条件 front rear它会被误判为空。等于说“空”和“满”变成了同一个状态完全无法区分。标准的解决方案是在数组中人为保留一个空位让 rear 最多走到 front 前一个位置就停下来强制制造一个“永远不让 rear 追上 front”的边界。于是判空front rear判满(rear 1) % n front也就是说容量为 n 的数组实际最多存储 n - 1 个元素。这个“浪费的一格”不是缺陷而是为了消除状态二义性付出的成本。举个具体例子数组容量为 5初始化 front 0rear 0。陆续入队 A、B、C、D 四个元素后rear 4。此时 (41)%5 0等于 front队列判满。虽然 data[4] 是空的但设计上不会再允许入队除非先出队腾出位置。提示面试时如果你主动说出“这种方案会浪费一个空间”并且紧接着给出“另一种方案是增加 size 计数器”面试官的好感度会明显提升。因为这表明你不仅能实现还能权衡多种设计。2.3 不浪费空间的两种替代设计如果业务场景要求容量必须用满有三种办法绕开“浪费一格”的问题增加 size 字段维护一个整数 count入队加 1出队减 1。判空用 count 0判满用 count capacity。此时 front rear 时根据 count 判断具体状态不再有歧义。增加 boolean 标志位记录最后一次操作是入队还是出队。如果最后一次是入队且 front rear则队满最后一次是出队且 front rear则队空。这种方法不太直观容易出错但可以避免维护计数器。不存储元素借助哨兵节点链表实现时保留一个 dummy 节点也可以消解空满歧义不过数组场景下更常用的是 size 方案。我个人的建议是基础版本用“浪费一格”的方式因为这是教科书标准实现面试官最熟悉升级版本用 size 方案因为后面做动态扩容时count 是必不可少的信息一套代码可以复用。3. 手撕循环队列从基础版到扩容版3.1 面试笔试版固定容量的循环队列面试时最稳妥的做法是先明确告诉面试官你要用“数组 预留空位”的方式实现然后快速写出代码。这里我给出 Java 版本和 Python 版本逻辑完全等价。Java 实现class MyCircularQueue { private int[] data; private int front; private int rear; private int capacity; public MyCircularQueue(int k) { this.capacity k; this.data new int[k]; this.front 0; this.rear 0; } public boolean enQueue(int value) { if (isFull()) { return false; } data[rear] value; rear (rear 1) % capacity; return true; } public boolean deQueue() { if (isEmpty()) { return false; } front (front 1) % capacity; return true; } public int Front() { if (isEmpty()) { return -1; } return data[front]; } public int Rear() { if (isEmpty()) { return -1; } return data[(rear - 1 capacity) % capacity]; } public boolean isEmpty() { return front rear; } public boolean isFull() { return (rear 1) % capacity front; } }Python 实现class CircularQueue: def __init__(self, k: int): self.data [0] * k self.capacity k self.front 0 self.rear 0 def enqueue(self, value: int) - bool: if self.is_full(): return False self.data[self.rear] value self.rear (self.rear 1) % self.capacity return True def dequeue(self) - bool: if self.is_empty(): return False self.front (self.front 1) % self.capacity return True def front_value(self) - int: if self.is_empty(): return -1 return self.data[self.front] def rear_value(self) - int: if self.is_empty(): return -1 last (self.rear - 1 self.capacity) % self.capacity return self.data[last] def is_empty(self) - bool: return self.front self.rear def is_full(self) - bool: return (self.rear 1) % self.capacity self.front这段代码有几个值得在面试中主动讲出来的点enQueue 时先判满入队失败不是抛异常而是返回 false。面试官会问你“失败怎么处理”你要表达出“定长缓冲场景下满了就是满了由调用方决定阻塞、丢弃还是扩容”。deQueue 时只需要移动 front不需要真正删除数组里的元素。旧值会留在原地等后续入队覆盖即可。这一点体现了数组队列的优雅之处。Rear() 的索引要减一再加容量取模防止负数下标这是手写时最容易漏的边界。3.2 升级版带 size 计数器的循环队列如果你觉得浪费一个空间不优雅可以在类里增加一个 count 字段。这个版本在扩容时特别好用因为 resize 过程中需要知道当前元素个数。class CircularQueueWithSize { private int[] data; private int capacity; private int count; private int front; private int rear; public CircularQueueWithSize(int k) { this.capacity k; this.data new int[k]; this.count 0; this.front 0; this.rear 0; } public boolean enQueue(int value) { if (count capacity) { return false; } data[rear] value; rear (rear 1) % capacity; count; return true; } public boolean deQueue() { if (count 0) { return false; } front (front 1) % capacity; count--; return true; } public int Front() { if (count 0) { return -1; } return data[front]; } public int Rear() { if (count 0) { return -1; } return data[(rear - 1 capacity) % capacity]; } public boolean isEmpty() { return count 0; } public boolean isFull() { return count capacity; } }这个版本的核心改动是用 count 变量明确记录队列中的元素数量front rear 时不再有歧义。注意 rear 的移动逻辑没有变仍然是先写后移。面试时如果你想展示自己思考更全面可以主动说“我可以用 size 字段替代预留空位的方案这样容量能 100% 利用而且实现扩容时无需额外判断当前有效元素个数。”这句话一出口基本就和其他候选人拉开差距了。3.3 再进一步支持动态扩容的循环队列如果面试官追问“队列满了怎么办”常规答案是“返回失败”。但进阶答案是“动态扩容”。扩容的思路是当 count capacity 时申请一个容量翻倍的新数组把旧数组中从 front 开始按顺序的 count 个元素搬移到新数组头部然后重置指针。为什么必须从 front 开始搬而不是从下标 0 开始搬因为循环队列中元素在数组里不一定是连续存放的例如 front 3rear 1有效元素位于下标 3、4、0 三个位置。如果直接遍历旧数组会带出脏数据。正确做法是遍历 count 次每次取 data[(front i) % capacity]。private void resize() { int newCapacity capacity * 2; int[] newData new int[newCapacity]; for (int i 0; i count; i) { newData[i] data[(front i) % capacity]; } this.data newData; this.front 0; this.rear count; this.capacity newCapacity; }搬移完成后元素在新数组的 0 到 count - 1 的位置连续存放因此 front 直接置为 0rear 置为 count。此时 count 仍然有效不需要修改。在 enQueue 方法中把“满则返回 false”改成“先扩容再入队”public boolean enQueue(int value) { if (count capacity) { resize(); } data[rear] value; rear (rear 1) % capacity; count; return true; }扩容的时间复杂度是 O(n)但只发生在队列满的瞬间。入队 n 次扩容 O(log n) 次均摊下来每次入队仍然是 O(1)。这就是动态数组的均摊分析和 ArrayList 的扩容原理一致。注意扩容前后队头元素的下标可能发生变化。如果你在外部持有“某个元素的下标”扩容后就会失效。实际应用中环形缓冲区往往会避免扩容而是通过覆盖旧数据或阻塞生产者来处理满状态。3.4 现场测试一步一步模拟运行面试时写完代码最好主动跑一组数据验证。下面我按容量为 5 的“预留空位版”手动走一遍初始化front 0rear 0数组内容 [_, _, _, _, _]enQueue(1)data[0]1rear 1内容 [1, _, _, _, _]enQueue(2)data[1]2rear 2内容 [1, 2, _, _, _]deQueue()front 1内容 [1, 2, _, _, _]逻辑上只剩 2enQueue(3)data[2]3rear 3内容 [1, 2, 3, _, _]enQueue(4)data[3]4rear 4内容 [1, 2, 3, 4, _]enQueue(5)data[4]5rear 0内容 [1, 2, 3, 4, 5]enQueue(6)(rear1)%5 11 ! front1等等这里其实要小心。第 7 步入队 5 后rear 变成 0此时第 8 步 isFull 检查条件变成 (01)%5 1而 front 1所以确实判满返回 false。但如果真的让 rear 又一次撞上 front就无法区分状态了。这个例子正好说明了为什么预留一格是对的如果不留空格第 8 步入队成功会让 rear 变成 1之后你无法判断队列是满还是空。面试时你可以用这类小例子证明代码能处理边界而不是只求“看起来能跑”。4. 面试里的连环追问不要只会背代码4.1 不直接移动数组元素是因为性能吗面试官可能会问“普通数组队列出队后把后面的元素往前搬一步不也能复用空间吗干嘛要搞得这么复杂”答案是移动元素是 O(n) 的操作。如果队列里有 100 万个元素每出队一个就要搬 99 万个元素这在高频读写场景下是不可接受的。循环队列通过指针移动实现 O(1) 出队入队空间换时间的思路在这里体现得很典型。从另一个角度说普通数组队列的“搬移”还破坏了元素的内存连续性吗其实搬移后内存还是连续的但每次搬移的 CPU 开销远大于指针加一的几百纳秒。在延迟敏感的系统里这种差异就是生死线。4.2 链表实现的队列与数组循环队列怎么选这也是高频追问。很多人只知道链表也能实现队列但说不清两者差异。链表队列的入队出队同样是 O(1)且支持无限容量动态增长。它的缺点是每个节点需要额外的指针开销内存占用更大。节点在内存中分散分布遍历时缓存不友好。频繁创建和销毁节点会产生 GC 压力。数组循环队列的优势是内存连续预分配无 GC 压力。通过下标直接定位缓存命中率高。容量可控适合固定大小的缓冲池。数组循环队列的缺点是容量固定需要提前规划。如果生产速率长期大于消费速率队列会持续打满这时要么扩容要么丢弃要么阻塞。所以面试回答可以这样组织“如果数据量波动大、没有明确的容量上限选链表更灵活如果是高频读写、对延迟敏感、容量可预估数组循环队列几乎是不二之选。Netty、Disruptor 这类高性能框架底层用的就是数组环形缓冲区。”4.3 并发场景下循环队列怎么保证线程安全这个问题能直接区分候选人是在“背题”还是在“做系统”。最简单的方案是在 enQueue 和 deQueue 方法上加synchronized让整个方法串行化。优点是正确率高缺点是吞吐量下降锁竞争激烈。更好的方案是结合业务场景单生产者单消费者SPSC生产者只修改 rear消费者只修改 front互不干扰。配合volatile修饰的读写索引和内存屏障可以在无锁情况下安全地读写。这是 Disruptor 框架的核心设计之一。此时要注意的是生产者写入的数据在更新 rear 索引前必须保证对消费者可见通常需要插入内存屏障。多生产者多消费者MPMC索引被多人争用需要使用 CAS 或锁保证原子性。Java 里可以用AtomicInteger配合自旋重试来实现一个 Lock-Free 队列但 ABA 问题和伪共享都需要考虑复杂度很高面试时点到为止即可。如果面试官只是考察基础你可以先给出synchronized版本然后主动说“如果是一读一写场景可以做到无锁核心思路是让读写双方各持有一个索引互不争抢”。这一句话就能体现你有并发意识。4.4 循环队列在真实系统里的影子很多候选人不知道这题学了有什么用。其实循环队列就是环形缓冲区在真实系统里到处都是Java ArrayDeque底层实现就是循环数组用于 deque。NettyRecycler和一些缓冲池设计中使用了环形回收思路。LMAX Disruptor高性能多线程框架核心就是 Ring Buffer。操作系统键盘缓冲区、网络驱动接收队列很多是环形队列。日志系统异步日志的缓冲队列经常设计成环形满了直接丢弃或覆盖旧日志避免阻塞业务线程。面试时如果能举出两三个这样的例子面试官会认为你不仅有代码能力还有系统架构视野。这也是“一面”中区分度很高的加分项。5. 我踩过的坑与实战建议5.1 循环队列实现的高发 Bug 清单这部分内容是我自己手写循环队列时真实踩过、也给同事 code review 时遇到过的坑列成表格帮大家对照。常见问题具体表现解决方案负下标取模错误获取队尾时使用(rear - 1) % n当 rear0 时得到负数统一写成(rear - 1 n) % n判满条件写反用front rear判断满导致空满不分预留空位时用(rear 1) % n front带 size 时用count capacity出队时没有移动 front只返回队头值但指针不动重复读到同一元素deQueue 必须更新 front并考虑是否需要清空旧引用对象类型时帮助 GC扩容时元素顺序错乱直接按数组下标搬运把脏数据也搬进去按 (front i) % capacity 循环取 count 个元素rear 指向最后一个元素还是下一个空位混淆入队写错位置队尾取值错误明确 rear 永远指向“下一个写入位置”队尾元素要减一索引循环计数时忘记取模在 enQueue 后直接 rear数组越界每次移动都用取模或者额外判断后归零5.2 如何用“对拍测试”验证你的实现面试手写代码容易紧张但如果有平时写单元测试的习惯心里会稳很多。我自己调试循环队列用的方法很简单对着标准行为写一个小测试器随机操作 结果比对。思路如下定义一个普通的ArrayDeque或者LinkedList作为“参考答案”。随机执行 10000 次入队/出队操作。每次操作后把参考答案的队列内容和我自己实现的循环队列内容逐一比对。如果中间发现不一致立刻打印当前 front、rear、容量、内部数组和操作序列。用这种“对拍”的方式10 分钟就能发现所有边界问题。写代码时还可以增加一个辅助方法把内部数组和指针状态打印出来def debug_print(self): print(front:, self.front, rear:, self.rear) print(data:, self.data) print(valid:, [self.data[(self.front i) % self.capacity] for i in range(self.count)])面试时虽然没有时间跑完整测试但你可以手动模拟几个典型场景例如队列满时入队队列空时出队绕一圈回到原点队尾元素访问等。把这些边界都说清楚基本就稳了。5.3 面试回答节奏先讲思路再写代码最后主动测试根据我经历过和模拟过的面试一个合格的回答节奏是先说场景“我用数组实现因为数组内存连续、访问快。普通数组队列会有假溢出问题所以我用取模把数组逻辑上变成环。”说明空满策略“我采用预留一个空位的方式rear 追上 front 就判满。如果希望容量完全利用可以加一个 size 计数器。”快速写码先写核心的 enQueue、deQueue再补 isEmpty、isFull、Front、Rear。主动跑数据手动模拟两个用例展示边界处理。应对追问如果面试官问满了怎么办给出扩容方案如果问线程安全给出 synchronized 到无锁优化的思路。这套节奏最实用的地方在于它让面试官始终跟着你的思路走而不是被零散的代码牵着走。哪怕最终代码有小瑕疵你的思维框架也已经加分了。结尾一次真实复盘后的建议说实话循环队列这道题我后来复盘时最大的感受是越是看起来简单的数据结构越能暴露一个人写代码的底层习惯。那些能够在白板上把 front、rear 的关系讲得清清楚楚的人往往不是背过答案而是在纸上画过十几遍环形图亲手推演过指针的每一次移动。所以我的建议是拿到这道题不要只背代码动手画一个容量为 5 的环形数组把入队、出队、再入队的每一步指针变化都写下来直到你能闭着眼睛说出“什么时候 front 会追上 rear什么时候 rear 会追上 front”。如果你能做到这一步循环队列就不再是面试题而是你工具箱里一件随手能用的武器等真正遇到资源控制、缓冲设计之类的场景时你自然会想到它。