C++ STL 环形队列模拟实现

C++ STL 环形队列模拟实现

下面是一个使用C++ STL实现的环形队列（Circular Queue）的完整示例：

#include <iostream>
#include <vector>
#include <stdexcept>template <typename T>
class CircularQueue {
private:std::vector<T> data;  // 使用vector作为底层存储size_t front;         // 队头指针size_t rear;          // 队尾指针size_t currentSize;    // 当前队列中元素数量size_t capacity;       // 队列容量public:// 构造函数，初始化队列容量explicit CircularQueue(size_t size) : data(size), front(0), rear(0), currentSize(0), capacity(size) {}// 判断队列是否为空bool isEmpty() const {return currentSize == 0;}// 判断队列是否已满bool isFull() const {return currentSize == capacity;}// 获取队列当前元素数量size_t size() const {return currentSize;}// 入队操作void enqueue(const T& item) {if (isFull()) {throw std::overflow_error("Queue is full");}data[rear] = item;rear = (rear + 1) % capacity;++currentSize;}// 出队操作T dequeue() {if (isEmpty()) {throw std::underflow_error("Queue is empty");}T item = data[front];front = (front + 1) % capacity;--currentSize;return item;}// 查看队首元素T peek() const {if (isEmpty()) {throw std::underflow_error("Queue is empty");}return data[front];}// 打印队列内容（用于调试）void print() const {if (isEmpty()) {std::cout << "Queue is empty" << std::endl;return;}std::cout << "Queue contents: ";size_t i = front;for (size_t count = 0; count < currentSize; ++count) {std::cout << data[i] << " ";i = (i + 1) % capacity;}std::cout << std::endl;}
};int main() {// 创建一个容量为5的环形队列CircularQueue<int> queue(5);// 测试入队操作queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);queue.enqueue(40);queue.enqueue(50);queue.print();  // 输出: 10 20 30 40 50// 测试队列已满try {queue.enqueue(60);} catch (const std::overflow_error& e) {std::cout << "Error: " << e.what() << std::endl;}// 测试出队操作std::cout << "Dequeued: " << queue.dequeue() << std::endl;  // 输出: 10std::cout << "Dequeued: " << queue.dequeue() << std::endl;  // 输出: 20queue.print();  // 输出: 30 40 50// 测试环形特性queue.enqueue(60);queue.enqueue(70);queue.print();  // 输出: 30 40 50 60 70// 测试查看队首元素std::cout << "Front element: " << queue.peek() << std::endl;  // 输出: 30// 测试队列空的情况while (!queue.isEmpty()) {queue.dequeue();}try {queue.dequeue();} catch (const std::underflow_error& e) {std::cout << "Error: " << e.what() << std::endl;}return 0;
}

实现说明

1. 底层存储：使用std::vector作为底层容器存储队列元素。

2. 关键指针：

   • front：指向队列第一个元素
   • rear：指向队列下一个插入位置
   • currentSize：记录当前队列中元素数量
   • capacity：队列的总容量

3. 环形特性：通过模运算实现指针的循环移动：

   rear = (rear + 1) % capacity;
   front = (front + 1) % capacity;
   

4. 主要操作：

   • enqueue()：向队尾添加元素
   • dequeue()：从队首移除元素
   • peek()：查看队首元素但不移除
   • isEmpty()/isFull()：检查队列状态

5. 异常处理：当队列满时入队或队列空时出队会抛出相应异常。

这个实现充分利用了STL的vector容器，同时通过模运算实现了环形队列的特性，避免了普通队列在出队后空间无法再利用的问题。