环形队列利用固定数组和取模操作实现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 的更新都通过取模完成循环，逻辑清晰。基本上就这些，不复杂但容易忽略边界判断。