c++实现deque

### C++ 实现 `deque` 数据结构

在 C++ 中，标准模板库（STL）已经提供了高效的双端队列实现——`std::deque`。此容器支持快速的随机访问迭代、常数时间内的前端和后端插入/删除操作。

#### 创建并初始化 `deque`

可以使用多种方法来创建和初始化一个 `deque` 对象：

#include <iostream>
#include <deque>

using namespace std;

int main() {
    // 初始化 deque 并赋初值
    deque<int> d = {1, 2, 3};
    
    // 输出初始状态下的 deque 元素
    cout << "Initial elements are: ";
    for (auto& elem : d) {
        cout << elem << ' ';
    }
    cout << endl;
}

上述代码展示了如何通过列表初始化语法定义一个新的整型 `deque`[^1]。

#### 插入元素到 `deque`

为了向 `deque` 添加新项，可利用成员函数如 `push_back()` 或者更高效的方式是采用 `emplace_*` 方法直接构建对象而无需先创建临时变量再复制或移动它们:

void addElements(deque<int>& dq) {
    // 使用 push_back/push_front 来添加单个元素
    dq.push_back(4);
    dq.push_front(-1);

    // 利用 emplace 在指定位置构造新元素而非拷贝已有实例
    dq.emplace(dq.end(), 5);      // 等价于 push_back(5)，但在内部调用了构造函数
    dq.emplace(dq.begin(), -2);   // 类似地，在最前面增加一项
}

// 打印当前 deque 的全部内容
template<typename T>
void printDeque(const deque<T>& deq) {
    for (const auto& item : deq){
        cout << item << " ";
    }
    cout << "\n";
}

这段程序片段说明了怎样运用不同的插入技术扩展现有的 `deque` 结构体[^3]。

#### 遍历 `deque`

由于 `deque` 支持基于索引的操作，因此可以直接像处理数组那样对其进行遍历；另外也能够借助迭代器完成同样的工作：

void traverseByIndex(const deque<int>& dataQueue) {
    size_t sz = dataQueue.size();
    for(size_t idx = 0 ;idx != sz;++idx){
        cout<<dataQueue[idx]<<" ";  
    }
    cout<<"\n";
}

void iterateWithIterator(const deque<int>& iteratedDQ) {
    for(auto itr = iteratedDQ.cbegin();itr!=iteratedDQ.cend();++itr){
        cout<<*itr<<" ";
    }
    cout<<"\n";
}

这里给出了两种不同风格的遍历模式：一种是指针式的下标访问形式，另一种则是更加泛化的迭代器机制[^2]。