如何编写包含4种指定首尾操作方法的C++循环队列类

你要求的支持两端插入、删除的循环队列本质是循环双端队列（Circular Deque），以下是完整可运行的实现代码：

完整实现代码 #

#include <iostream>
#include <stdexcept>

template <typename T>
class CircularDeque {
private:
    T* data;          // 底层存储数组
    int front;        // 队首元素下标
    int size;         // 当前元素个数
    int capacity;     // 数组最大容量
    const int DEFAULT_CAPACITY = 8; // 默认初始容量

    // 队满时扩容为原来的2倍
    void resize() {
        int newCapacity = capacity * 2;
        T* newData = new T[newCapacity];
        // 拷贝原有元素到新数组
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % capacity];
        }
        delete[] data;
        data = newData;
        front = 0;
        capacity = newCapacity;
    }

public:
    // 构造函数
    CircularDeque() {
        capacity = DEFAULT_CAPACITY;
        data = new T[capacity];
        front = 0;
        size = 0;
    }

    // 析构函数
    ~CircularDeque() {
        delete[] data;
    }

    // 判断队列是否为空
    bool isEmpty() const {
        return size == 0;
    }

    // 获取当前元素个数
    int getSize() const {
        return size;
    }

    // 队首插入元素
    void insertFirstQ(const T& value) {
        if (size == capacity) {
            resize();
        }
        // 处理负数取模，保证下标合法
        front = (front - 1 + capacity) % capacity;
        data[front] = value;
        size++;
    }

    // 队尾插入元素
    void insertEndQ(const T& value) {
        if (size == capacity) {
            resize();
        }
        int rear = (front + size) % capacity;
        data[rear] = value;
        size++;
    }

    // 删除并返回队首元素
    T removeFirstQ() {
        if (isEmpty()) {
            throw std::out_of_range("Queue is empty, cannot remove from front");
        }
        T res = data[front];
        front = (front + 1) % capacity;
        size--;
        return res;
    }

    // 删除并返回队尾元素
    T removeEndQ() {
        if (isEmpty()) {
            throw std::out_of_range("Queue is empty, cannot remove from end");
        }
        int rear = (front + size - 1) % capacity;
        T res = data[rear];
        size--;
        return res;
    }
};

// 测试示例
int main() {
    CircularDeque<int> q;

    // 插入测试
    q.insertEndQ(1);
    q.insertEndQ(2);
    q.insertFirstQ(0);
    q.insertFirstQ(-1);

    // 当前队列顺序：-1, 0, 1, 2
    std::cout << "Current size: " << q.getSize() << std::endl;

    // 删除测试
    std::cout << "Remove front: " << q.removeFirstQ() << std::endl; // 输出-1
    std::cout << "Remove end: " << q.removeEndQ() << std::endl; // 输出2
    std::cout << "Remove front: " << q.removeFirstQ() << std::endl; // 输出0
    std::cout << "Remove end: " << q.removeEndQ() << std::endl; // 输出1

    std::cout << "Is empty: " << (q.isEmpty() ? "Yes" : "No") << std::endl; // 输出Yes

    return 0;
}

核心方法说明 #

• insertFirstQ：在队列头部插入新元素，队满时自动扩容为原容量的2倍
• insertEndQ：在队列尾部插入新元素，队满时自动扩容为原容量的2倍
• removeFirstQ：删除并返回队列头部元素，队列为空时抛出越界异常
• removeEndQ：删除并返回队列尾部元素，队列为空时抛出越界异常

内容的提问来源于stack exchange，提问作者Mohammad Reza Zolfaghari