设计循环队列 图解题解

这道题到底在问什么

构造

MyCircularQueue(4)

操作

enQueue×3, deQueue, enQueue×2 …

关键

队列满后下标要绕回开头

最优解：一步一步想明白

1. 3如果队首死死钉在下标 0,每次出队都得搬动后面一长串元素,出一次队就 O(n),数据一多就慢。
2. 4队首不再钉死在 0:用 head 指队首、用 count 记个数。入队写 (head+count)%cap、出队让 head 前移,都不用搬数据。
3. 5下面用 k=4 的数组演示一整串操作。front 指队首元素,rear 指「下一个要写的空格」。一格一格看它们绕圈走。
4. 6head=0, count=0, cap=4开一个长度 4 的数组,全空。front 和 rear 都指向下标 0:这是空队列的起点。
5. 7写 rear=0,count→1,rear→1入队 10:写进 rear 指的空格(下标 0),count 加 1,rear 前移到 1。front 留在队首。
6. 8写 rear=1,count→2,rear→2入队 20,写到 rear=1,count=2,rear 继续走到 2。队列变 [10,20]。
7. 9写 rear=2,count→3,rear→3入队 30,写到下标 2,count=3,rear 走到下标 3。还剩最后一个空位。
8. 10清空 q[0],head→1,count→2出队:队首 10 拿走(下标 0 清空),front 前移到 1。没搬任何元素,只挪指针——这就是 O(1)。
9. 11写 rear=3,count→3,rear→(1+3)%4=0入队 40,写到 rear=3(最后一格)。新 rear=(1+3)%4=0——绕回开头!这就是「循环」第一次发生。
10. 12写 rear=0,count→4(满),rear→1入队 50,写进绕回后的下标 0(原来 10 待过、被循环利用的格子)。count=4=cap,满了:rear 又追回到 front 头上。
11. 13清空 q[1],head→2,count→3出队 20,下标 1 清空,front 前移到 2。此刻 head=2、rear=1,指针各在一方,队列绕成了环。Front()=30。
12. 14写 rear=1,count→4(满),rear→2入队 60:rear 此刻指下标 1(刚被 20 腾空的格),60 补进去,又满。空格被反复循环利用,一点不浪费。
13. 15清空 q[2],head→3,count→3出队 30,下标 2 清空,front 走到 3。逻辑队列 [40,50,60]:沿环 40(3)→50(0)→60(1)。
14. 16清空 q[3],head→(3+1)%4=0,count→2出队 40,清空下标 3。head 也到了末尾,(3+1)%4=0 绕回开头——头指针同样会循环。逻辑队列 [50,60]。
15. 17写 rear=2,count→3,rear→3入队 70,写到 rear=2,count=3。head 此刻在 0,逻辑队列 [50,60,70]。
16. 18写 rear=3,count→4(满),rear→(0+4)%4=0入队 80,写满四格。新 rear=(0+4)%4=0 绕回,又追上 front=0。这是 head 在 0 时的「满」长相。
17. 19清空 q[0],head→1,count→3出队 50,下标 0 清空,front→1。逻辑队列 [60,70,80]。
18. 20写 rear=0,count→4(满),rear→1入队 90:rear 绕回填下标 0,又满。一进一出之间,数组这块空间被一圈圈反复利用——这正是循环队列省空间的核心。
19. 21清空 q[1],head→2,count→3出队 60,front→2。逻辑队列 [70,80,90]:沿环 70(2)→80(3)→90(0)。
20. 22清空 q[2],head→3,count→2出队 70,front→3。逻辑队列 [80,90]。head 和 rear 又分到两头。
21. 23写 rear=1,count→3,rear→2入队 11,写到 rear=1,count=3。逻辑队列从 head=3 起读:[80,90,11]。
22. 24写 rear=2,count→4(满),rear→3入队 22,写满。rear 又追到 front=3。无论 head 在哪,满时永远是 rear 追上 head。
23. 25清空 q[3],head→0,count→3出队 80,head 又(3+1)%4=0 绕回开头。逻辑队列 [90,11,22]。
24. 26清空 q[0],head→1,count→2出队 90,front→1。逻辑队列 [11,22]。回看这 20 步:从头到尾没搬过一个元素,全靠两个指针绕环。
25. 27循环队列的灵魂:用取模把直线数组首尾接成环,头尾进出只动指针不搬数据,所以每个操作都是干净的 O(1)。
26. 31head=1,count=3,enQueue 时 rear=1+3=4 越界!假如入队时把 rear 写成 head+count=4(忘了 %cap),下标 4 根本不存在,直接越界崩。正确是 %4=0 绕回开头——这就是取模不可省的原因。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class MyCircularQueue:
    def __init__(self, k):
        self.cap = k
        self.q = [None] * k
        self.head = 0
        self.count = 0
    def enQueue(self, value):
        if self.isFull(): return False
        rear = (self.head + self.count) % self.cap
        self.q[rear] = value
        self.count += 1
        return True
    def deQueue(self):
        if self.isEmpty(): return False
        self.q[self.head] = None
        self.head = (self.head + 1) % self.cap
        self.count -= 1
        return True
    def Front(self):
        return -1 if self.isEmpty() else self.q[self.head]
    def Rear(self):
        if self.isEmpty(): return -1
        return self.q[(self.head + self.count - 1) % self.cap]
    def isEmpty(self): return self.count == 0
    def isFull(self): return self.count == self.cap

class MyCircularQueue {
    vector<int> q; int cap, head, cnt;
public:
    MyCircularQueue(int k) : q(k), cap(k), head(0), cnt(0) {}
    bool enQueue(int value) {
        if (isFull()) return false;
        int rear = (head + cnt) % cap;
        q[rear] = value; cnt++; return true;
    }
    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % cap; cnt--; return true;
    }
    int Front() { return isEmpty() ? -1 : q[head]; }
    int Rear() {
        if (isEmpty()) return -1;
        return q[(head + cnt - 1) % cap];
    }
    bool isEmpty() { return cnt == 0; }
    bool isFull() { return cnt == cap; }
};

class MyCircularQueue {
    private int[] q;
    private int cap, head, cnt;
    public MyCircularQueue(int k) {
        q = new int[k]; cap = k; head = 0; cnt = 0;
    }
    public boolean enQueue(int value) {
        if (isFull()) return false;
        int rear = (head + cnt) % cap;
        q[rear] = value; cnt++; return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % cap; cnt--; return true;
    }
    public int Front() { return isEmpty() ? -1 : q[head]; }
    public int Rear() {
        if (isEmpty()) return -1;
        return q[(head + cnt - 1) % cap];
    }
    public boolean isEmpty() { return cnt == 0; }
    public boolean isFull() { return cnt == cap; }
}

复杂度

面试官可能追问