P622 循环队列 · null 哨兵实现 —— 逐步演示文字稿

对应代码：top.vission.problems.impl.P622.MyCircularQueue

核心规则（与 Java 代码逐行一致）：

• enQueue(v)：list[in] = v，然后 in = (in + 1) % size
• deQueue()：list[out] = null，然后 out = (out + 1) % size
• isEmpty() ⇐ list[out] == null（只看 out 这一格）
• isFull() ⇐ list[in] != null（只看 in 这一格）
• Front() = list[out]；Rear() = list[(size + in - 1) % size]（先加 size 再取模，因为 Java 中 -1 % 3 == -1）

图中约定：■ 表示有值（非 null）的槽，· 表示 null 空槽。in 指向下一个写入位置，out 指向队头。

场景一：填满 → 满员拒绝入队（run() 里注释掉的那段）

第 0 帧：new MyCircularQueue(3)

        index     0     1     2
                  ·     ·     ·
                out               
                in

in = out = 0。isEmpty() 看 list[0] == null → true；isFull() 看 list[0] != null → false。

第 1 帧：enQueue(1) → 写 list[0]，in → 1

                  0     1     2
                  ■     ·     ·
                out           (in 移到 1)

第 2 帧：enQueue(2) → 写 list[1]，in → 2

                  0     1     2
                  ■     ■     ·
                out                 (in 移到 2)

第 3 帧：enQueue(3) → 写 list[2]，in = 3 % 3 = 0（回绕！）

                  0     1     2
                  ■     ■     ■
               in/out

关键帧：in 回绕追上了 out，两者同格。此时队列是满的，不是空的！
isFull() 看 list[in=0] = 1 ≠ null → true。这就是 null 哨兵不浪费槽位的原因。

第 4 帧：enQueue(4) → isFull() 为 true，直接 return false，状态零改动

第 5 帧：Rear() = list[(3 + 0 - 1) % 3] = list[2] = 3

对比：若写成 (in - 1) % size，in = 0 时得 -1 % 3 = -1 → 下标越界。这是本题最常见的崩溃点。

场景二：出队空槽 → 回绕入队（指针交叉，最容易藏 bug 的区间）

第 6 帧接场景一：deQueue() → list[0] = null，out → 1

                  0     1     2
                  ·     ■     ■
                      out  in(=0)

队列剩 [2, 3]。isEmpty() 看 list[out=1] = 2 ≠ null → false，正确。

第 7 帧：enQueue(5) → 写 list[0]（回绕前的空槽！），in → 1

                  0     1     2
                  ■     ■     ■
                      in/out

关键帧：队列内容是 [2, 3, 5]（逻辑顺序：out=1 → 2 → 回绕 → 0），5 号槽是"尾巴"。
in == out == 1 又一次出现——和第 0 帧同样的指针位置，这次却是满。两者靠什么区分？null 版靠 list[in] 是否为 null；经典 count 版靠 count == size vs count == 0。

第 8 帧：Front() = list[out=1] = 2

第 9 帧：Rear() = list[(3 + 1 - 1) % 3] = list[0] = 5

尾巴不在 in - 1 的"表面位置"吗？在——in 指向的是下一个待写位置，所以真正的队尾永远是它前面一格，回绕时就落到 0 号槽。

场景三：全部出队 → 空队列守卫

第 10~12 帧：连续三次 deQueue()

[2,3,5] 出队2 →  0     1     2      out: 1→2     队列 [3, 5]
                 ■     ·     ■

[3,5] 出队3   →  0     1     2      out: 2→0     队列 [5]
                 ■     ·     ·

[5] 出队5     →  0     1     2      out: 0→1     队列 []
                 ·     ·     ·
                 in/out(都在1)

注意两点：

1. out 每走一步都恰好停在第一个 null 上，所以 isEmpty() 永远一眼成立；
2. 清空后 in = out = 1 而不是回到 (0, 0)——指针从不"归零重置"，判空完全不依赖指针位置，只依赖 list[out] 的内容。这是 null 哨兵写法的自洽之处，也是它和 count 写法（清空时 count 归 0、指针可停在任意处）的区别。

第 13 帧：再 deQueue() → isEmpty() 为 true，return false，不动 out

第 14 帧：Front() → 队空，return -1（不是抛异常；(int)null 会 NPE，守卫必须在前）

一张表总览全程

边界清单（自查用）

1. 空/满同形：in == out 既可能是空（第 0 帧）也可能是满（第 3、7 帧），必须有额外判据（你的 null 哨兵 / count 计数器 / 浪费一格）。
2. Rear 负索引：(in - 1 + size) % size，先加再模；Java 负数取模结果带符号。
3. 指针回绕：++ 之后必须 % size，漏了就是 ArrayIndexOutOfBoundsException。
4. 失败操作零副作用：满时 enQueue、空时 deQueue 直接 return false，指针不许动。
5. 空时 Front/Rear 返回 -1，守卫放在取值之前。
6. k = 1：每步指针都原地回绕到 0，单独测一条 enQ → isFull → deQ → isEmpty → enQ 链。
7. k = 0：% size 除零（题目保证 k ≥ 1，防御性写法可把 size 钳到 ≥ 1）。
8. null 哨兵的适用前提：value 是 int 装箱后永不为 null，判据才成立；换成可存 null 的对象队列就失效，需改用 count 方案。