什么是循环队列？如何解决「假溢出」并判断队空队满？

简化版

普通数组队列出队后，队头前面的空间没法再用，明明还有空位却提示满了，这叫假溢出。循环队列让队头队尾指针取模回绕（(index + 1) % capacity），把数组当成首尾相接的环，空出来的位置能循环利用。判空判满常用留一个空位：rear == front 为空，(rear + 1) % capacity == front 为满。

详细版

用数组 + 两个指针 front（队头）、rear（队尾），入队写 rear 位置后 rear = (rear+1)%cap，出队读 front 位置后 front = (front+1)%cap。

问题：rear == front 既可能是「空」也可能是「满」，无法区分。三种常见解法：

牺牲一个空位（最常用）：故意不让队列填满，留一格空。
- 队空：front == rear
- 队满：(rear + 1) % cap == front
- 实际能存 cap − 1 个元素。
额外记一个 size 计数：size == 0 为空、size == cap 为满，能存满 cap 个，但多维护一个变量。
加一个布尔标志 / 用 count：思路同上。

class MyCircularQueue {
    int[] a; int front, rear, cap;
    MyCircularQueue(int k) { cap = k + 1; a = new int[cap]; } // 多留一格
    boolean enQueue(int v) {
        if (isFull()) return false;
        a[rear] = v; rear = (rear + 1) % cap; return true;
    }
    boolean deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % cap; return true;
    }
    boolean isEmpty() { return front == rear; }
    boolean isFull()  { return (rear + 1) % cap == front; }
}

完整版教学

一、假溢出是怎么来的

用固定数组做队列，队头出队时如果只是 front++，那么数组左边被出队腾出的格子再也用不到了。反复入队出队后，rear 到了数组末尾、front 前面却空着一堆——这时入队会判「越界/满」，但实际还有空间。这种「有空位却报满」就是假溢出，本质是「线性数组用一次就作废前面的空间」。

二、循环队列如何消除假溢出

把数组想象成一个环：指针走到末尾就用取模 % cap 回到开头。这样队头出队腾出的前面格子，队尾入队时能绕回来复用，空间循环利用，不再有假溢出。核心动作就是指针 +1 后对容量取模。

三、判空判满为什么是难点

回绕之后，front == rear 出现在两种时刻：一开始（空），或者刚好绕一圈填满（满）。同一个条件对应两种状态，必须想办法区分：

留一个空位：让「满」时 rear 停在 front 前一格，于是「满」是 (rear+1)%cap == front，「空」才是 front == rear。代价是浪费一格（能存 cap−1 个）。
额外计数 size：直接判 size==0 / size==cap，不浪费空间但多一个变量要同步维护。

两种都对，面试说清楚你选哪种、以及为什么就行。

四、为什么值得用循环队列

定长、高效：数组连续内存、缓存友好，入队出队都是 O(1)。
常见于底层：环形缓冲区（ring buffer）广泛用于 IO 缓冲、日志、生产者-消费者、网络收发缓冲、音视频流——都是「固定容量、循环复用」的场景。
相比链表队列，省去了频繁分配/回收节点的开销。

五、对比链表实现的队列

链表队列天然不需要处理假溢出（动态分配），但每个节点有指针开销、缓存不友好、频繁 new 节点。循环队列用固定数组，容量上限确定的场景下更快更省。两者按「容量是否固定、是否在意内存/缓存」来选。

六、常见误区与追问

设计方式	判空条件	判满条件	特点
浪费一个槽位	`front == rear`	`(rear + 1) % capacity == front`	逻辑简单，实际容量少 1
维护 `size`	`size == 0`	`size == capacity`	容量可用满，多维护一个变量
维护标志位	看标志	看标志	容易写错，面试较少推荐

易错点：循环队列的数组下标会回绕，但元素顺序没有乱；真正的队头和队尾由 front/rear 语义决定，不由物理下标大小决定。

例如数组容量为 5，采用浪费一个槽位的设计，最多只能放 4 个元素。若 front=3,rear=2，队列并不是空，而是已经发生回绕；此时队列里的逻辑区间可能是 3,4,0,1。判断满要看 (rear+1)%5 == front，而不是看 rear > front。

误区：rear 小于 front 就说明队列错了。 循环队列允许下标回绕，rear < front 只是说明尾部已经绕到数组前面。
误区：数组队列只要 rear 到末尾就满了。 如果前面有出队留下的空位，普通线性队列会假溢出，循环队列可以复用这些位置。
误区：判空和判满都用 front == rear。 这样无法区分空和满，所以要浪费一个槽位、维护 size 或维护额外标志。
追问：为什么循环队列适合固定容量缓冲区？ 它用固定数组复用空间，不需要频繁移动元素或分配节点。
追问：入队和出队为什么是 O(1)？ 只改一个位置和一个指针，取模回绕不依赖元素数量。
追问：链表队列和循环队列怎么选？ 容量固定且追求缓存友好时用循环数组；容量不确定且不想预分配时可用链表。

八、伪代码与不变量

数据结构题最好把操作过程写成伪代码，因为指针、索引或状态变化一旦说不清，就容易在边界用例上出错。以什么是循环队列？如何解决「假溢出」并判断队空队满？为例，可以先固定不变量，再解释每一步为什么保持它。

初始化：维护结构不变量 invariant
遍历/调整：每处理 1 个节点或元素，都只改变必要指针/索引
校验：操作后结构仍满足顺序、连通性或堆/树性质
复杂度：每个元素最多进入/离开结构 O(1) 或 O(log n) 次

九、一步步推演与边界

回答什么是循环队列？如何解决「假溢出」并判断队空队满？时，最好额外走一遍小样例。先用 3～5 个元素演示正常操作，再故意加入空结构、单元素、重复值或极端位置，观察不变量是否仍成立。比如链表题要盯住前驱、当前、后继 3 个指针；树题要说明递归返回值代表什么；堆题要说明上浮/下沉什么时候停止；图题要说明 visited 或入度数组何时更新。

这种推演的价值在于把“我知道算法”变成“我能证明边界也不会错”。很多面试失分不是主流程不会，而是少了空节点、尾节点、重复边、环、K 越界这类边界。把这些点主动讲出来，既能减少代码 bug，也能让复杂度分析更可信。

边界类型	检查方式	容易出错的地方
空结构	输入为空或 root/head 为 null	直接访问属性导致异常
单元素	只有 1 个节点或元素	前驱/后继、左右子树判断错误
重复值	多个元素相等	比较条件写成 < 还是 <=
极端位置	头尾、最大最小、第一层最后一层	更新指针或索引越界

七、加强记忆

假溢出 = 线性数组队列出队后前面空间作废；循环队列用指针 +1 取模回绕复用空间。判空判满要打破 front==rear 的二义性：常用留一格空位（空 front==rear、满 (rear+1)%cap==front）或额外记 size。适合环形缓冲等定长场景。

简化版

详细版