CC++ & Algorithm

Python循环队列

较难3
语言版本：C++Python
概述：循环队列像一个环形跑道，能重复利用存储空间，避免普通队列的“假溢出”。

循环队列：让空间像环形跑道一样循环利用

你有没有遇到过这样的问题：在食堂排队打饭，队伍很长，但前面的人打完后离开，空出的位置却不能排新人，因为新人只能排在队伍最后面。如果队伍是一条直线，前面的空位就浪费了。在编程中，普通队列用数组实现时也有同样的问题：元素出队后，数组前面的位置就空着，无法再使用，这就是“假溢出”。

循环队列就像一条环形跑道，跑完一圈还能接着跑，空间可以重复利用。它把数组的首尾连接成一个环，让队列的存储空间“活”起来。下面我们就来学习循环队列的原理和Python实现。

什么是循环队列

循环队列（Circular Queue）是一种线性数据结构，它使用固定大小的数组，并通过两个指针（front和rear）来管理元素的入队和出队。与普通队列不同，当指针到达数组末尾时，它会绕回到数组开头，就像时钟的指针一样。这样，即使数组前面有位置，也能被重新使用，避免了空间浪费。

生活中的循环队列

想象一个环形跑道（比如学校操场上的跑道）。如果让你在跑道上排队，你可以从起点开始跑，跑完一圈后还能继续跑，不会因为起点被人占了就不能用。循环队列就像这个跑道：数组的每个位置相当于跑道上的一个点，front指向队首（当前第一个人的位置），rear指向队尾（下一个空位的位置）。当rear跑到数组末尾时，它会回到数组开头（取模运算），继续放新的人。

再比如，你在游乐场玩一个旋转木马，座位是固定的循环排列。如果当前有一个空座位，新来的小朋友可以直接坐上去，而不需要等所有人都走光。

核心概念

1. 数组和两个指针

我们用固定大小的数组（比如长度为5）来存储队列元素，并定义两个索引：

  • front：指向队首元素（第一个要出队的元素）
  • rear：指向队尾元素的下一个空位（下一个入队的位置）

初始化时，front和rear都等于0，表示队列为空。

2. 取模运算（绕圈）

当rear或front移动到数组末尾（比如索引4）后，下一个位置应该是索引0。取模运算（index + 1） % 容量就能实现这个绕圈效果。例如：

  • 容量=5，当前rear=4，要后移一位：(4 + 1) % 5 = 0，就回到了开头。

3. 队空和队满的判断

循环队列需要区分“队空”和“队满”。因为两个指针相等时，可能表示队列为空，也可能表示队列满了（如果不用特殊方法）。经典的做法是：故意浪费一个存储单元，让队满条件为(rear + 1) % 容量 == front。也就是说，当rear再往后移一位就要追上front时，我们认为队列已满。这样，队列最多能存储容量 - 1个元素。

  • 队空：front == rear
  • 队满：(rear + 1) % 容量 == front

4. 入队（enqueue）操作

  1. 先检查队列是否已满。
  2. 如果未满，将新元素放入rear指向的位置。
  3. 然后rear向后移动一位（取模）。

5. 出队（dequeue）操作

  1. 先检查队列是否为空。
  2. 如果不空，取出front指向的元素。
  3. 将front向后移动一位（取模），返回取出的元素。

Python 实现（含详细注释）

下面我们实现一个循环队列，并用生活中的例子（零食排队）来测试。

class CircularQueue:
    """循环队列，用固定大小数组实现"""
    def __init__(self, capacity):
        self.capacity = capacity          # 队列容量（实际存储 capacity-1 个元素）
        self.queue = [None] * capacity    # 存储元素的列表
        self.front = 0                    # 队首索引（指向第一个元素）
        self.rear = 0                     # 队尾索引（指向下一个空位）

    def enqueue(self, item):
        """入队：将元素添加到队尾"""
        # 检查是否队满：rear再后移一位就追上front
        if (self.rear + 1) % self.capacity == self.front:
            print("队列已满，不能放入", item)
            return
        self.queue[self.rear] = item      # 在rear位置放入元素
        self.rear = (self.rear + 1) % self.capacity  # rear后移（绕圈）

    def dequeue(self):
        """出队：移除并返回队首元素"""
        if self.front == self.rear:       # 队空
            print("队列为空，没有元素可出队")
            return None
        item = self.queue[self.front]     # 取出队首元素
        self.queue[self.front] = None     # 可选：清空该位置（便于调试）
        self.front = (self.front + 1) % self.capacity  # front后移
        return item

    def display(self):
        """显示队列中所有元素（从头到尾）"""
        if self.front == self.rear:
            print("队列为空")
            return
        i = self.front
        while i != self.rear:
            print(self.queue[i], end=" ")
            i = (i + 1) % self.capacity
        print()

# 测试：模拟三个小朋友排队领零食
queue = CircularQueue(4)   # 容量为4，但只能存3个元素（浪费一个位置）
queue.enqueue("小明")
queue.enqueue("小红")
queue.enqueue("小刚")
print("当前队列：", end="")
queue.display()   # 输出：小明 小红 小刚

# 出队两位同学
queue.dequeue()   # 小明离开
queue.dequeue()   # 小红离开
print("出队后队列：", end="")
queue.display()   # 输出：小刚

# 再入队两位新同学
queue.enqueue("小华")
queue.enqueue("小李")
print("再次入队后：", end="")
queue.display()   # 输出：小刚 小华 小李

# 尝试再多放一个（队列已满）
queue.enqueue("小张")   # 输出：队列已满，不能放入 小张

运行这段代码，你会看到循环队列如何重复使用前面的空间。

常见错误与注意事项

错误1：忘记取模运算

新手常常会直接写self.rear += 1，而不对容量取模，导致rear超出数组范围（索引越界）。一定要用(self.rear + 1) % self.capacity。

错误2：混淆队空和队满的判断

错误地认为front == rear既是队空又是队满，导致入队和出队都出问题。记住我们采用“浪费一个空间”的策略：

  • front == rear → 只有队空
  • (rear + 1) % capacity == front → 队满

如果你想用计数器（count）来记录元素个数，也可以，但浪费一个空间是更经典、更简单的方法。

错误3：遍历时忘了绕圈

在display中，如果直接用for i in range(self.front, self.rear):，当front > rear（因为绕圈）时会出错。必须用while循环加取模的方式正确遍历。

错误4：忘记初始化或重置指针

创建队列后，要确保front和rear都初始化为0。如果后来清空队列，也要重置这两个指针（或者用self.front = self.rear = 0）。

完整示例：考试座位循环排队

假设老师让同学轮流回答问题，同学们按学号排队。我们用循环队列模拟：先入队5名同学（学号1~5），然后依次叫座，每次叫完的同学再回到队尾（模拟“循环”效果）。这个例子能更直观地展示循环队列的“绕圈”特性。

class CircularQueue:
    # （代码同上，复制即可）
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0

    def enqueue(self, item):
        if (self.rear + 1) % self.capacity == self.front:
            print("队列已满，", item, "无法加入")
            return
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity

    def dequeue(self):
        if self.front == self.rear:
            print("队列为空")
            return None
        item = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.capacity
        return item

    def display(self):
        if self.front == self.rear:
            print("队列为空")
            return
        i = self.front
        while i != self.rear:
            print(self.queue[i], end=" ")
            i = (i + 1) % self.capacity
        print()

# 测试：循环提问
queue = CircularQueue(6)  # 容量6，实际存5个学生
# 初始5个学生学号
for num in range(1, 6):
    queue.enqueue(f"学生{num}")
print("最初排队：", end="")
queue.display()

# 模拟3轮提问：叫一个学生，回答完再排到队尾
for round_num in range(1, 4):
    print(f"\n第{round_num}轮提问：")
    student = queue.dequeue()           # 叫出队首学生
    print(f"  {student} 回答问题")
    queue.enqueue(student)              # 回答完，再排到队尾
    print("  当前队列：", end="")
    queue.display()

运行结果可以看到，学号1、2、3依次被提问后又回到队尾，队列里始终是那5个学生，并没有减少。

总结

循环队列通过取模运算把数组首尾相连，让空间像环形跑道一样循环使用，非常适合那些需要固定存储空间、频繁入队出队的场景，比如操作系统中的任务调度、网络数据包缓冲等。在GESP考试中，循环队列是常考知识点，你需要掌握：

  • 用front和rear两个指针管理队列
  • 取模运算实现绕圈
  • 分清队空和队满的条件
  • 能够手写入队、出队和遍历代码

相关指引

学完循环队列，你还可以继续了解：

  • 普通队列（链式队列）：用链表实现的队列，没有容量限制，但每次插入和删除需要分配内存。
  • 栈：另一种线性结构，后进先出（LIFO），与队列形成对比。
  • 双端队列：两端都可以入队和出队，更加灵活。
  • 优先队列：元素带有优先级，出队时优先级最高的先出。

如果你想深入练习，可以尝试用循环队列实现“约瑟夫环”问题（一群人围成一圈报数，数到某个数的人出列）。这是循环队列的一个经典应用！

现在，拿起键盘，自己动手写一个循环队列吧！

例题精讲

1单选题

在采用牺牲一个存储单元来区分队空和队满的循环队列中，若队列容量为N（数组大小为N），则队满的条件是（）。

A(rear + 1) % N == front
Brear == front
C(rear - front + N) % N == N - 1
D(front + 1) % N == rear
2单选题

一个循环队列的数组容量为6，初始状态front=rear=0。经过一系列入队和出队操作后，front=2，rear=5，则此时队列中的元素个数为（）。

A2
B3
C4
D5
3判断题

循环队列通过首尾相接的存储结构，可以完全避免普通队列的“假溢出”现象，并且不需要牺牲任何存储空间。

4填空题
以下是用Python列表模拟循环队列的入队操作函数，请补全空缺处代码。假设队列容量为size，采用牺牲一个存储单元的方式，队空条件为self.rear == self.front，队满条件为(self.rear + 1) % self.size == self.front。

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = 0
        self.rear = 0

    def enqueue(self, value):
        if (self.rear + 1) % self.size == self.front:
            print("队列已满")
            return False
        self.queue[self.rear] = value
        ___
5填空题
以下是用Python列表模拟循环队列的出队操作函数，请补全空缺处代码。队列采用牺牲一个存储单元的方式，队空条件为self.rear == self.front。

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = 0
        self.rear = 0

    def dequeue(self):
        if self.rear == self.front:
            print("队列已空")
            return None
        value = self.queue[self.front]
        self.front = (self.front + 1) % self.size
        ___