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;  // 输出: 10
    std::cout << "Dequeued: " << queue.dequeue() << std::endl;  // 输出: 20
    queue.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容器，同时通过模运算实现了环形队列的特性，避免了普通队列在出队后空间无法再利用的问题。