deque的实现

deque的底层和vector是很相似的

T* elements;
size_t frontIndex;
size_t backIndex;
size_t capacity;
size_t current_size;

先介绍一下这四个吧，方便下面介绍deque的原理

elements就和vector的一样
frontIndex：指向队列中第一个有效元素的位置
backIndex：指向下一个可以插入元素的位置，也就是循环数组最后一个元素的下一个位置
capacity：elements的容量
current_size：队列中实际存储的元素数量

deque的原理是基于循环数组实现的，那什么是循环数组呢？

假设说我们有数组

1 2	capacity = 5; elements = [_, _, _, _, _];

逻辑上想象成一个“圆圈”：

1
2
3

[0] → [1] → [2] → [3] → [4] 
 ↑                        ↓
 ←←←←←←←←←←←←←←←←←←←←←←←←←

初始状态（空）

elements = [_, _, _, _, _]
frontIndex = 0
backIndex  = 0
size       = 0

连续 push_back(1), push_back(2), push_back(3)

elements = [1, 2, 3, _, _]
frontIndex = 0
backIndex  = 3
size       = 3

现在 push_front(0)

如果你现在 push_front() 插入了元素，前指针 frontIndex 就会往左移，但如果它已经是 0，就会绕回最后一格（index 4），这就是取模 % capacity 的作用！
减法要+ capacity，因为C++的取模和Python是不一样的，他是和整数除法相关的
- C++ 中，取模结果的符号 跟被除数（左边的数）相同。
- Python 中，取模结果的符号 跟除数（右边的数）相同，且结果总是 非负（如果除数是正数）。

例子：-7 % 3

语言	表达式	结果	解释
C++	`-7 % 3`	-1	结果和 -7 同号（负数）
Python	`-7 % 3`	2	结果和 3 同号（正数）

所以要实现和Python一样的，可以先模完再加一个模数进去即可，也就是(a % b + b) % b

我们把 frontIndex 往前挪：

1	frontIndex = (frontIndex - 1 + capacity) % capacity;

所以

1	frontIndex = (0 - 1 + 5) % 5 = 4

现在数组变成：

elements = [1, 2, 3, _, 0]
frontIndex = 4
backIndex  = 3
size       = 4

逻辑顺序其实是：0, 1, 2, 3

如果再插一个元素（push_back(4)）

现在队列满了，这时候就会进行扩容

扩容为 capacity = 10，并把旧数据按逻辑顺序（从 frontIndex 开始）复制过去，变成：

elements = [0, 1, 2, 3, 4, _, _, _, _, _]
frontIndex = 0
backIndex  = 5
size       = 5
capacity   = 10

介绍完大致原理，现在就可以继续动手实现了

首先的话肯定是构造函数和析构函数

myDeque() : elements(nullptr), frontIndex(0), backIndex(0), capacity(0), current_size(0) {}
~myDeque(){
    clear();
    delete[] elements;
}

然后是扩容函数

void reserve(size_t newCapacity){
    T* newElement = new T[newCapacity];

    size_t temp = frontIndex;
    for (size_t i = 0; i < current_size; i++){
        newElement[i] = elements[temp];
        temp = (temp + 1) % capacity;
    }

    delete[] elements;
    elements = newElement;
    capacity = newCapacity;
    frontIndex = 0;
    backIndex = current_size;
}

也是两倍扩容，队列满的时候
从第一个有效元素开始向后遍历，遍历次数根据current_size即可
取模实现对循环数组的遍历
因为扩容是开辟新空间，所以记得修改frontIndex和backIndex

push_back的实现

void push_back(const T& val){
    if (current_size == capacity) capacity ? reserve(2 * capacity) : reserve(1);
    elements[backIndex] = val;
    backIndex = (backIndex + 1) % capacity;
    current_size++;
}

尾部加入元素的时候，只要更新backIndex就行了，同时注意取模
尺寸+1

push_front的实现

void push_front(const T& val){
    if (current_size == capacity) capacity ? reserve(2 * capacity) : reserve(1);
    frontIndex = ((frontIndex - 1) % capacity + capacity) % capacity;
    elements[frontIndex] = val;
    current_size++;
}

头部加入元素的时候，只要更新frontIndex就行了，同时注意遵循(a % b + b) % b
注意是先更新frontIndex，再进行赋值，而backIndex是先赋值再更新的
尺寸-1

pop_front和pop_back的实现

void pop_back(){
    if (current_size == 0) throw out_of_range("此时队列为空");
    backIndex = ((backIndex - 1) % capacity + capacity) % capacity;
    current_size--;
}

void pop_front(){
    if (current_size == 0) throw out_of_range("此时队列为空");
    frontIndex = (frontIndex + 1) % capacity;
    current_size--;
}

一样的逻辑，没什么好说的

重载[]

T& operator[] (size_t index){
    if (index < 0 || index >= current_size) throw out_of_range("越界访问");
    return elements[(frontIndex + index) % capacity];
}

注意越界检测
利用frontIndex获取在循环数组中的位置

STL库中Deque有两种访问方式，一种是使用符号[]，另一种是使用at()
区别在于遇到Index越界的情况

at()会抛出异常，告诉我们下标越界了，而[]不会，它会导致未定义行为

所以at()更安全，但是效率比[]低一些，需要看代码运行的具体任务进行取舍

size获取长度

1
2
3

size_t size(){
    return current_size;
}

clear的实现

void clear(){
    while (current_size){
        pop_front();
    }
}

这个的begin和end不好实现，需要用到iterator，后续再补充，累了

对应完整代码如下

#include <cstddef>
#include <stdexcept>
using namespace std;

template <typename T>
class myDeque{
private:
    T* elements;
    size_t frontIndex;
    size_t backIndex;
    size_t capacity;
    size_t current_size;

public:
    myDeque() : elements(nullptr), frontIndex(0), backIndex(0), capacity(0), current_size(0) {}
    ~myDeque(){
        clear();
        delete[] elements;
    }

    void reserve(size_t newCapacity){
        T* newElement = new T[newCapacity];

        size_t temp = frontIndex;
        for (size_t i = 0; i < current_size; i++){
            newElement[i] = elements[temp];
            temp = (temp + 1) % capacity;
        }

        delete[] elements;
        elements = newElement;
        capacity = newCapacity;
        frontIndex = 0;
        backIndex = current_size;
    }

    void push_back(const T& val){
        if (current_size == capacity) capacity ? reserve(2 * capacity) : reserve(1);
        elements[backIndex] = val;
        backIndex = (backIndex + 1) % capacity;
        current_size++;
    }

    void push_front(const T& val){
        if (current_size == capacity) capacity ? reserve(2 * capacity) : reserve(1);
        frontIndex = ((frontIndex - 1) % capacity + capacity) % capacity;
        elements[frontIndex] = val;
        current_size++;
    }

    void pop_back(){
        if (current_size == 0) throw out_of_range("此时队列为空");
        backIndex = ((backIndex - 1) % capacity + capacity) % capacity;
        current_size--;
    }

    void pop_front(){
        if (current_size == 0) throw out_of_range("此时队列为空");
        frontIndex = (frontIndex + 1) % capacity;
        current_size--;
    }

    T& operator[] (size_t index){
        if (index < 0 || index >= current_size) throw out_of_range("越界访问");
        return elements[(frontIndex + index) % capacity];
    }

    size_t size(){
        return current_size;
    }

    void clear(){
        while (current_size){
            pop_front();
        }
    }


};

测试用例如下

#include <iostream>
#include <string>


// 这里假设你已经把 myDeque 的实现放在上面或头文件中

int main() {
    myDeque<int> dq;

    // 测试 push_back
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);
    cout << "After push_back: ";
    for (size_t i = 0; i < dq.size(); ++i) {
        cout << dq[i] << " ";
    }
    cout << endl;

    // 测试 push_front
    dq.push_front(0);
    dq.push_front(-1);
    cout << "After push_front: ";
    for (size_t i = 0; i < dq.size(); ++i) {
        cout << dq[i] << " ";
    }
    cout << endl;

    // 测试 pop_back
    dq.pop_back();
    cout << "After pop_back: ";
    for (size_t i = 0; i < dq.size(); ++i) {
        cout << dq[i] << " ";
    }
    cout << endl;

    // 测试 pop_front
    dq.pop_front();
    cout << "After pop_front: ";
    for (size_t i = 0; i < dq.size(); ++i) {
        cout << dq[i] << " ";
    }
    cout << endl;

    // 测试 operator[]
    cout << "Element at index 1: " << dq[1] << endl;

    // 测试 size
    cout << "Current size: " << dq.size() << endl;

    // 测试 clear
    dq.clear();
    cout << "After clear, size: " << dq.size() << endl;

    // 测试异常 pop
    try {
        dq.pop_front();
    } catch (const exception& e) {
        cout << "Caught exception (pop_front): " << e.what() << endl;
    }

    try {
        dq.pop_back();
    } catch (const exception& e) {
        cout << "Caught exception (pop_back): " << e.what() << endl;
    }

    // 测试异常 operator[]
    try {
        cout << dq[0] << endl;
    } catch (const exception& e) {
        cout << "Caught exception (operator[]): " << e.what() << endl;
    }

    return 0;
}

输出如下：

After push_back: 1 2 3 
After push_front: -1 0 1 2 3 
After pop_back: -1 0 1 2 
After pop_front: 0 1 2 
Element at index 1: 1
Current size: 3
After clear, size: 0
Caught exception (pop_front): 此时队列为空
Caught exception (pop_back): 此时队列为空
Caught exception (operator[]): 越界访问
Process exited with status 0