循环队列的思想

学习目标

本节学习循环队列的基本思想。

如果用普通数组实现队列，随着不断出队，数组前面的空间可能被空出来，但队尾仍然向后移动。循环队列通过让队头和队尾在数组中循环移动，解决这类空间复用问题。

普通数组队列的问题

假设用数组保存队列，并用 front 表示队头位置，用 rear 表示队尾下一个可插入位置。

数组:  A  B  C  _  _
下标:  0  1  2  3  4
front = 0
rear = 3

如果执行两次出队，A 和 B 离开：

数组:  _  _  C  _  _
下标:  0  1  2  3  4
front = 2
rear = 3

此时数组前面有空位，但如果 rear 只会向后移动，后续空间可能很快用完。循环队列的思想就是让下标到达末尾后回到开头，从而复用前面的空位。

循环移动的公式

循环队列常用取模运算让下标回到数组开头。

如果数组容量是 capacity，当前位置是 index，那么下一个位置可以写成：

next = (index + 1) % capacity

例如容量为 5 时，下标变化如下：

0 -> 1 -> 2 -> 3 -> 4 -> 0 -> 1

这个公式让数组在逻辑上变成一个环。

入队和出队过程

循环队列通常维护两个位置：

front：队头元素所在位置。
rear：队尾之后的下一个可插入位置。

入队时，把元素放到 rear，然后让 rear 向后循环移动。

出队时，取出 front 的元素，然后让 front 向后循环移动。

入队时，先判断队列是否已满。
如果未满，把新元素写入 rear 指向的位置。
更新 rear = (rear + 1) % capacity。
出队时，先判断队列是否为空。
如果不为空，取出 front 指向的元素。
更新 front = (front + 1) % capacity。

一个简化的循环队列

下面用固定容量数组实现一个简化循环队列。为了让判空和判满更清晰，这里额外维护 size 表示当前元素数量。

class CircularQueue {
private:
    vector<int> data;
    int frontIndex;
    int sizeValue;

public:
    CircularQueue(int capacity)
        : data(capacity), frontIndex(0), sizeValue(0) {}

    bool enqueue(int value) {
        if (sizeValue == data.size()) {
            return false;
        }

        int rearIndex = (frontIndex + sizeValue) % data.size();
        data[rearIndex] = value;
        sizeValue++;
        return true;
    }

    bool dequeue() {
        if (sizeValue == 0) {
            return false;
        }

        frontIndex = (frontIndex + 1) % data.size();
        sizeValue--;
        return true;
    }
};

class CircularQueue {
    private int[] data;
    private int frontIndex;
    private int size;

    CircularQueue(int capacity) {
        data = new int[capacity];
        frontIndex = 0;
        size = 0;
    }

    boolean enqueue(int value) {
        if (size == data.length) {
            return false;
        }

        int rearIndex = (frontIndex + size) % data.length;
        data[rearIndex] = value;
        size++;
        return true;
    }

    boolean dequeue() {
        if (size == 0) {
            return false;
        }

        frontIndex = (frontIndex + 1) % data.length;
        size--;
        return true;
    }
}

class CircularQueue:
    def __init__(self, capacity):
        self.data = [0] * capacity
        self.front_index = 0
        self.size = 0

    def enqueue(self, value):
        if self.size == len(self.data):
            return False

        rear_index = (self.front_index + self.size) % len(self.data)
        self.data[rear_index] = value
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0:
            return False

        self.front_index = (self.front_index + 1) % len(self.data)
        self.size -= 1
        return True

class CircularQueue
{
    private int[] data;
    private int frontIndex;
    private int size;

    public CircularQueue(int capacity)
    {
        data = new int[capacity];
        frontIndex = 0;
        size = 0;
    }

    public bool Enqueue(int value)
    {
        if (size == data.Length)
        {
            return false;
        }

        int rearIndex = (frontIndex + size) % data.Length;
        data[rearIndex] = value;
        size++;
        return true;
    }

    public bool Dequeue()
    {
        if (size == 0)
        {
            return false;
        }

        frontIndex = (frontIndex + 1) % data.Length;
        size--;
        return true;
    }
}

这个实现不是为了覆盖所有工程细节，而是帮助你理解循环队列的核心：队头可以向后循环移动，队尾也可以通过取模回到数组开头。

循环队列的优点

循环队列的主要优点是复用固定数组空间。

它适合容量固定或容量可控的场景，例如缓冲区、任务队列、简单消息队列等。在这些场景中，我们希望避免频繁移动元素，也不希望每次出队都把后面的元素整体向前搬移。

本节小结

循环队列通过取模运算让数组下标循环移动，从而复用数组前面已经空出的空间。

它适合用固定数组实现队列，能够避免普通数组队列中队头前移后造成的空间浪费。理解循环队列后，你会更清楚队列不仅是一种抽象规则，也可以有不同的底层实现策略。