设计循环队列

如果队首死死钉在下标 0,每次出队都得搬动后面一长串元素,出一次队就 O(n),数据一多就慢。

队首不再钉死在 0:用 head 指队首、用 count 记个数。入队写 (head+count)%cap、出队让 head 前移,都不用搬数据。

下面用 k=4 的数组演示一整串操作。front 指队首元素,rear 指「下一个要写的空格」。一格一格看它们绕圈走。

初始化 MyCircularQueue(4)：开一个长度 4 的数组,全空。front 和 rear 都指向下标 0:这是空队列的起点。

① enQueue(10)：入队 10:写进 rear 指的空格(下标 0),count 加 1,rear 前移到 1。front 留在队首。

② enQueue(20)：入队 20,写到 rear=1,count=2,rear 继续走到 2。队列变 [10,20]。

③ enQueue(30)：入队 30,写到下标 2,count=3,rear 走到下标 3。还剩最后一个空位。

④ deQueue():出队 10：出队:队首 10 拿走(下标 0 清空),front 前移到 1。没搬任何元素,只挪指针——这就是 O(1)。

⑤ enQueue(40):填到末尾：入队 40,写到 rear=3(最后一格)。新 rear=(1+3)%4=0——绕回开头!这就是「循环」第一次发生。

⑥ enQueue(50):绕回写下标 0：入队 50,写进绕回后的下标 0(原来 10 待过、被循环利用的格子)。count=4=cap,满了:rear 又追回到 front 头上。

⑦ deQueue():出队 20：出队 20,下标 1 清空,front 前移到 2。此刻 head=2、rear=1,指针各在一方,队列绕成了环。Front()=30。

⑧ enQueue(60):又补满：入队 60:rear 此刻指下标 1(刚被 20 腾空的格),60 补进去,又满。空格被反复循环利用,一点不浪费。

⑨ deQueue():出队 30：出队 30,下标 2 清空,front 走到 3。逻辑队列 [40,50,60]:沿环 40(3)→50(0)→60(1)。

⑩ deQueue():出队 40,head 绕回：出队 40,清空下标 3。head 也到了末尾,(3+1)%4=0 绕回开头——头指针同样会循环。逻辑队列 [50,60]。

⑪ enQueue(70)：入队 70,写到 rear=2,count=3。head 此刻在 0,逻辑队列 [50,60,70]。

⑫ enQueue(80):写满,rear 绕回：入队 80,写满四格。新 rear=(0+4)%4=0 绕回,又追上 front=0。这是 head 在 0 时的「满」长相。

⑬ deQueue():出队 50：出队 50,下标 0 清空,front→1。逻辑队列 [60,70,80]。

⑭ enQueue(90):rear 绕回填 0：入队 90:rear 绕回填下标 0,又满。一进一出之间,数组这块空间被一圈圈反复利用——这正是循环队列省空间的核心。

⑮ deQueue():出队 60：出队 60,front→2。逻辑队列 [70,80,90]:沿环 70(2)→80(3)→90(0)。

⑯ deQueue():出队 70：出队 70,front→3。逻辑队列 [80,90]。head 和 rear 又分到两头。

⑰ enQueue(11):rear 走到 2：入队 11,写到 rear=1,count=3。逻辑队列从 head=3 起读:[80,90,11]。

⑱ enQueue(22):再次写满：入队 22,写满。rear 又追到 front=3。无论 head 在哪,满时永远是 rear 追上 head。

⑲ deQueue():出队 80：出队 80,head 又(3+1)%4=0 绕回开头。逻辑队列 [90,11,22]。

⑳ deQueue():出队 90：出队 90,front→1。逻辑队列 [11,22]。回看这 20 步:从头到尾没搬过一个元素,全靠两个指针绕环。

循环队列的灵魂:用取模把直线数组首尾接成环,头尾进出只动指针不搬数据,所以每个操作都是干净的 O(1)。

雷区实演 · 漏取模会怎样：假如入队时把 rear 写成 head+count=4(忘了 %cap),下标 4 根本不存在,直接越界崩。正确是 %4=0 绕回开头——这就是取模不可省的原因。

边界三连：先想空时读什么(−1)、满时还入队(拒绝)、最小 k=1 三种边界,代码就稳了。

面试追问：把「为何省 O(n)」「count 模型的取舍」「怎么扩双端」讲透,是这题面试的得分点。