C++实现一个deque

deque（双端队列）是一种数据结构，可以在队列两端进行插入和删除操作。在C++ STL中，deque也是一个标准库容器，可以直接使用。下面是一个简单的C++实现deque的代码，供参考：

#include <iostream>
#include <stdexcept>

template <typename T>
class deque {
private:
    T *arr;          // 存储元素的数组
    int front_idx;   // 队头索引
    int rear_idx;    // 队尾索引
    int capacity;    // 容量
    int sz;          // 当前元素个数

public:
    deque(int capacity = 10) {
        this->capacity = capacity;
        arr = new T[capacity];
        front_idx = rear_idx = capacity / 2;
        sz = 0;
    }

    ~deque() {
        delete[] arr;
    }

    bool empty() const {
        return sz == 0;
    }

    int size() const {
        return sz;
    }

    void push_front(const T &val) {
        if (sz == capacity) {
            throw std::out_of_range("deque is full");
        }
        front_idx--;
        arr[front_idx] = val;
        sz++;
    }

    void push_back(const T &val) {
        if (sz == capacity) {
            throw std::out_of_range("deque is full");
        }
        arr[rear_idx] = val;
        rear_idx++;
        sz++;
    }

    void pop_front() {
        if (empty()) {
            throw std::out_of_range("deque is empty");
        }
        front_idx++;
        sz--;
    }

    void pop_back() {
        if (empty()) {
            throw std::out_of_range("deque is empty");
        }
        rear_idx--;
        sz--;
    }

    T &front() const {
        if (empty()) {
            throw std::out_of_range("deque is empty");
        }
        return arr[front_idx];
    }

    T &back() const {
        if (empty()) {
            throw std::out_of_range("deque is empty");
        }
        return arr[rear_idx - 1];
    }
};

int main() {
    deque<int> dq(5);
    dq.push_front(1);
    dq.push_back(2);
    dq.push_front(3);
    dq.push_back(4);
    dq.push_front(5);
    //dq.push_back(6);  // 抛出异常：deque is full
    std::cout << dq.front() << " " << dq.back() << std::endl;  // 输出 5 4
    dq.pop_front();
    dq.pop_back();
    std::cout << dq.front() << " " << dq.back() << std::endl;  // 输出 3 2
    return 0;
}

这里使用数组存储元素，使用front_idx和rear_idx分别表示队头和队尾的索引，使用sz表示当前元素个数。push_front和pop_front操作会改变队头索引front_idx，push_back和pop_back操作会改变队尾索引rear_idx。注意，在push_front和pop_front操作时，要先检查队列是否已满或为空，否则会抛出异常。deque的容量可以在构造函数中指定，默认为10。