循环队列——让数组空间不再浪费
较难4语言版本：通用
概述：循环队列通过将数组首尾相接，避免普通数组队列的“假溢出”问题，实现空间的高效利用。本文用生活例子和ASCII图讲解循环队列原理，并给出C++和Python实现。
循环队列——让数组空间不再浪费
为什么需要循环队列？从排队打饭说起
学校食堂打饭窗口前，同学们排成一队。新来的同学站到队伍末尾，打完饭的同学从前面离开。这就是一个典型的队列（先进先出）。计算机里用数组实现队列时，我们也有两个指针：front（队头，指向第一个离开的人）和 rear（队尾，指向下一个空位）。入队（新同学加入）时 rear++，出队（同学打完饭离开）时 front++。
但是，如果同学们打完饭离开后，空出来的位置就永远空着，队伍只能往后延长。比如食堂只有5个窗口位（数组大小5），一开始队伍从位置0、1、2、3排到4，等前两个人打完饭，位置0和1空出来了，但新同学来的时候，rear 已经指向数组末尾（下标5），无法再往后移动——尽管前面还有空位。这就是假溢出：数组尾部满了，但头部还有很多空间被浪费。
怎么能像环形跑道一样，让队伍首尾相连，空出来的位置能再次利用？循环队列就解决了这个问题。
生活中的循环：环形跑道、圆桌座位、公交环线
- 环形跑道：跑步时没有终点，跑完一圈回到起点，可以无限跑下去。循环队列的数组也是逻辑上首尾相连的环。
- 圆桌座位：10个座位围成一个圈，第一个人坐1号，第二个人坐2号……第10个人坐10号。第11个人来时，如果1号位的人已经离开，他就坐1号位。座位可以循环使用。
- 公交车环线：公交车从起点出发，绕一圈回到起点，再继续下一圈。乘客可以在任意站上车或下车，只要没坐满，就能一直运行。
这些例子都说明：循环结构能高效利用空间，让“用完”的位置重新变为“可用”。
循环队列的原理：取模运算让指针转圈
逻辑结构
循环队列的底层还是一个普通的数组，但通过取模运算 % 让指针能在数组范围内循环。假设数组容量为 capacity，那么：
- 入队时：
rear = (rear + 1) % capacity - 出队时：
front = (front + 1) % capacity
比如数组长度5，当 rear 从4再往后移动时，(4+1)%5 = 0，直接跳回开头。这样数组就变成了一个环。
物理存储（数组下标0~4）：
0 1 2 3 4
┌───┬───┬───┬───┬───┐
│ D │ E │ │ A │ B │
└───┴───┴───┴───┴───┘
↑ ↑
front=3 rear=2 （指向下一个空位）
逻辑环形：
rear(2)
│
↓
2 → 3 → 4 → 0 → 1 → 2 ...
↑
front(3)
如何判断队列空和满？
因为指针在环里转，空和满的条件需要小心区分。
- 空队列：
front == rear。表示没有元素。 - 满队列：如果也允许
front == rear表示满，那空和满就分不清了。所以经典做法是牺牲一个存储单元：让队列最多只存capacity-1个元素（数组实际有capacity个格子），满的条件是(rear + 1) % capacity == front，即rear再走一步就追上front了。
另一种方法是用一个额外变量 count 记录元素个数，但牺牲一个空间更省内存，也更常见。
基本操作
| 操作 | 条件 | 步骤 |
|---|---|---|
| 入队 | 先判满 (rear+1)%capacity == front | 若不满：data[rear]=x，rear = (rear+1)%capacity |
| 出队 | 先判空 front == rear | 若不空：front = (front+1)%capacity |
| 查看队头 | 判空 | 返回 data[front] |
| 获取大小 | 无 | (rear - front + capacity) % capacity |
注意：size 公式中的 +capacity 是为了防止 rear - front 为负数（因为指针循环可能导致 rear 小于 front）。
新手最容易犯的错
错误1：忘记取模，导致数组越界
// 错误写法
rear++; // 如果rear等于capacity，就超出数组范围了
// 正确写法
rear = (rear + 1) % capacity;
错误2：判空判满条件搞反
- 空：
front == rear - 满：
(rear + 1) % capacity == front有些同学会把满的条件写成rear + 1 == front，但没考虑循环，在边界会出错。
错误3：计算size时忘记取模
// 错误
int size = rear - front; // 当rear < front时得到负数
// 正确
int size = (rear - front + capacity) % capacity;
错误4：入队/出队时先移动指针再操作
比如入队时，先 rear++ 再赋值，会导致第一个元素放到错误位置。正确的顺序是：先赋值再移动指针。
完整代码示例（C++ + Python）
C++ 完整实现（每行变量加注释）
#include <iostream>
using namespace std;
class CircularQueue {
private:
int* data; // 指向存放队列元素的数组
int capacity; // 数组的总容量（包括牺牲的那个格子）
int front; // 队头指针：指向队列第一个有效元素
int rear; // 队尾指针：指向下一个空闲位置
public:
// 构造函数：用户传入希望存储的最大元素个数 maxSize
// 实际数组大小 = maxSize + 1（牺牲一个格子）
CircularQueue(int maxSize) {
capacity = maxSize + 1; // 多分配一个空间
data = new int[capacity];
front = 0;
rear = 0;
}
~CircularQueue() {
delete[] data;
}
// 入队：将元素 x 放入队尾
bool enqueue(int x) {
if (isFull()) {
cout << "队列已满，无法入队 " << x << endl;
return false;
}
data[rear] = x; // 在rear位置放入元素
rear = (rear + 1) % capacity; // 循环移动rear
return true;
}
// 出队：移除队头元素（不返回值）
bool dequeue() {
if (isEmpty()) {
cout << "队列为空，无法出队！" << endl;
return false;
}
front = (front + 1) % capacity; // 循环移动front
return true;
}
// 获取队头元素（不出队）
int getFront() {
if (isEmpty()) {
cout << "队列为空！" << endl;
return -1; // 应使用异常处理，这里简化
}
return data[front];
}
// 判断队列是否为空
bool isEmpty() {
return front == rear;
}
// 判断队列是否已满（牺牲一个格子的经典方法）
bool isFull() {
return (rear + 1) % capacity == front;
}
// 返回当前队列中的元素个数
int size() {
// (rear - front + capacity) 确保结果为非负数，再取模
return (rear - front + capacity) % capacity;
}
// 打印队列所有元素（调试用）
void print() {
if (isEmpty()) {
cout << "队列为空。" << endl;
return;
}
cout << "队列内容：";
int i = front;
while (i != rear) {
cout << data[i] << " ";
i = (i + 1) % capacity;
}
cout << endl;
}
};
// 测试代码
int main() {
// 创建一个最多可存4个元素的队列（用户说容量5，实际最多4）
CircularQueue q(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.print(); // 输出：10 20 30 40
cout << "队头元素: " << q.getFront() << endl; // 10
q.dequeue(); // 移除10
q.dequeue(); // 移除20
q.print(); // 输出：30 40
q.enqueue(50);
q.enqueue(60);
q.print(); // 输出：30 40 50 60
cout << "队列大小: " << q.size() << endl; // 4
cout << "是否已满? " << (q.isFull() ? "是" : "否") << endl; // 是
q.enqueue(70); // 输出“队列已满”提示
// 清空队列
while (!q.isEmpty()) {
cout << q.getFront() << " ";
q.dequeue();
}
cout << endl; // 输出：30 40 50 60
return 0;
}
Python 完整实现（每行变量加注释）
class CircularQueue:
"""循环队列（牺牲一个存储单元）"""
def __init__(self, max_size):
# 用户希望最多存 max_size 个元素，实际数组多一个格子
self.capacity = max_size + 1 # 数组总容量（包含牺牲格）
self.data = [None] * self.capacity # 存放元素的列表
self.front = 0 # 队头指针
self.rear = 0 # 队尾指针（指向下一个空位）
def enqueue(self, item):
"""入队：将item放入队尾，成功返回True，失败返回False"""
if self.is_full():
print(f"队列已满，无法入队 {item}")
return False
self.data[self.rear] = item # 在rear位置放入元素
self.rear = (self.rear + 1) % self.capacity # 循环移动rear
return True
def dequeue(self):
"""出队：移除队头元素，成功返回True"""
if self.is_empty():
print("队列为空，无法出队！")
return False
self.front = (self.front + 1) % self.capacity # 循环移动front
return True
def get_front(self):
"""查看队头元素（不出队）"""
if self.is_empty():
raise IndexError("队列为空")
return self.data[self.front]
def is_empty(self):
"""判断队列是否为空"""
return self.front == self.rear
def is_full(self):
"""判断队列是否已满（牺牲一格）"""
return (self.rear + 1) % self.capacity == self.front
def size(self):
"""返回队列中有效元素个数"""
return (self.rear - self.front + self.capacity) % self.capacity
def print_queue(self):
"""打印队列所有元素"""
if self.is_empty():
print("队列为空。")
return
i = self.front
elements = []
while i != self.rear:
elements.append(str(self.data[i]))
i = (i + 1) % self.capacity
print("队列内容:", " ".join(elements))
# 测试代码
if __name__ == "__main__":
q = CircularQueue(5) # 最多存4个元素
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.enqueue(40)
q.print_queue() # 输出：10 20 30 40
print("队头元素:", q.get_front()) # 10
q.dequeue() # 移除10
q.dequeue() # 移除20
q.print_queue() # 输出：30 40
q.enqueue(50)
q.enqueue(60)
q.print_queue() # 输出：30 40 50 60
print("队列大小:", q.size()) # 4
print("是否已满?", q.is_full()) # True
q.enqueue(70) # 输出“队列已满”提示
# 清空队列
while not q.is_empty():
print(q.get_front(), end=" ")
q.dequeue()
print() # 输出：30 40 50 60
循环队列的实用价值
- 解决假溢出：这是循环队列最大的意义。比如学校机房的上机排队系统，用循环队列可以循环使用座位，不会因为前面同学离开就浪费空位。
- 时间复杂度 O(1)：入队、出队、判空、判满、查看队头都是常数时间，非常适合实时系统。
- 应用场景：
- 操作系统的进程就绪队列（轮流使用 CPU）
- 网络数据包缓冲（网卡接收数据后放入循环队列，等待应用处理）
- 打印机任务队列（多台电脑共享一台打印机）
- 游戏中的技能冷却队列（比如技能释放后需要冷却5秒，用循环队列记录冷却时间）
- 与链式队列比较：数组实现的循环队列对缓存更友好（连续内存），而链式队列可以动态扩展。如果队列大小固定且频繁使用，循环队列效率更高。
相关知识点指引
- 普通队列：掌握用数组和链表实现的基本队列，理解“先进先出”原则。
- 双端队列（deque）：允许从两端入队和出队，循环队列是它的基础。
- 单调队列：用于滑动窗口最值问题（比如求子数组的最大值），常基于双端队列实现。
- 循环缓冲（Circular Buffer）：与循环队列本质相同，常用于工控、音频流等场景。
- Python 的
collections.deque：内置双端队列，底层就是循环数组，建议直接使用。
建议同学们在本地运行上面的代码，修改容量大小，试着入队出队多次，观察指针如何循环。理解了循环队列，再学双端队列和单调队列就会轻松很多。
例题精讲
1单选题
循环队列中，判断队列为满的条件是（假设front指向队头元素，rear指向队尾元素的下一个位置，队列容量为maxsize）
A(rear+1)%maxsize == front
Brear == front
C(front+1)%maxsize == rear
Drear == maxsize-1
2判断题
循环队列通过将数组视为环状结构，克服了普通队列的假溢出问题，从而充分利用了数组空间。
3填空题
以下循环队列入队操作的代码片段，请补充完整。
int enQueue(int queue[], int maxsize, int *front, int *rear, int value) {
if (___ == *front) {
return 0; // 队列满
}
*rear = (*rear + 1) % maxsize;
queue[*rear] = value;
return 1;
}4单选题
一个循环队列的数组容量为10，当前front=2，rear=8，则该队列中元素的个数为？
A6
B5
C7
D8
5判断题
在循环队列中，执行出队操作时，front指针的移动方式为 front = (front + 1) % maxsize。