环形队列利用固定数组和取模操作实现FIFO，通过front和rear指针循环移动，采用浪费一个空间的方法区分空满状态，代码简洁高效。
环形队列（也叫循环队列）是一种线性数据结构，它通过固定大小的数组实现队列的先进先出（FIFO）特性，并利用“取模”操作让队尾和队头在数组中循环移动，避免普通队列中因频繁出队导致的空间浪费。
环形队列的基本原理
使用一个固定大小的数组存储元素，配合两个指针（实际是整型索引）：
- front：指向队列第一个元素的位置
- rear：指向下一个插入位置的索引（即队尾的后一位）
通过 (index + 1) % capacity 实现索引的循环跳转。当 rear == front 时，队列可能为空或为满，因此需要额外处理以区分这两种状态。
如何区分空与满
常见方法有三种：
立即学习“C++免费学习笔记（深入）”；
- 使用一个额外的变量记录当前元素个数
- 浪费一个数组空间（最常用）
- 添加一个标志位标记最后一次操作是入队还是出队
下面采用“浪费一个空间”的方式实现，即队列满的条件是 (rear + 1) % capacity == front。
C++ 实现代码
#include <iostream>
using namespace std;
<p>class CircularQueue {
private:
int* arr; // 存储数据的数组
int front; // 队头索引
int rear; // 队尾后一个位置
int capacity; // 容量</p><p>public:
// 构造函数
CircularQueue(int size) {
capacity = size + 1; // 多分配一个空间用于判断满
arr = new int[capacity];
front = 0;
rear = 0;
}</p><pre class='brush:php;toolbar:false;'>// 析构函数
~CircularQueue() {
delete[] arr;
}
// 判断是否为空
bool isEmpty() {
return front == rear;
}
// 判断是否为满
bool isFull() {
return (rear + 1) % capacity == front;
}
// 入队
bool enqueue(int value) {
if (isFull()) {
cout << "队列已满，无法入队\n";
return false;
}
arr[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
// 出队
bool dequeue(int& value) {
if (isEmpty()) {
cout << "队列为空，无法出队\n";
return false;
}
value = arr[front];
front = (front + 1) % capacity;
return true;
}
// 获取队头元素
bool getFront(int& value) {
if (isEmpty()) {
cout << "队列为空\n";
return false;
}
value = arr[front];
return true;
}
// 获取当前元素个数
int size() {
return (rear - front + capacity) % capacity;
}};
// 使用示例 int main() { CircularQueue q(5); // 创建容量为5的队列（实际数组大小6）
q.enqueue(10); q.enqueue(20); q.enqueue(30); int val; q.getFront(val); cout << "队头元素: " << val << endl; q.dequeue(val); cout << "出队元素: " << val << endl; cout << "当前大小: " << q.size() << endl; return 0;
}
这个实现简洁高效，适合嵌入式、实时系统等对性能要求较高的场景。front 和 rear 的更新都通过取模完成循环，逻辑清晰。基本上就这些，不复杂但容易忽略边界判断。
