双端队列可通过动态数组实现，支持首尾插入删除。使用循环缓冲与自动扩容，关键操作均摊O(1)，但频繁扩容时性能低于STL的分段存储deque。
双端队列（deque，全称 double-ended queue）是一种可以在两端进行插入和删除操作的线性数据结构。C++ 中标准库已经提供了 std::deque，但理解其底层实现有助于加深对数据结构和内存管理的理解。下面介绍如何手动实现一个简单的双端队列。
基本设计思路
为了高效地在前后两端插入和删除元素，我们可以使用动态数组+循环缓冲或分段连续存储的方式。这里采用简化版的动态数组实现，支持自动扩容。
关键成员变量包括：
- data：指向动态分配的数组
- capacity：当前数组容量
- front_index：指向队首元素的索引
- rear_index：指向队尾下一个空位的索引
- size：当前元素个数
核心操作实现
以下是主要接口的实现逻辑：
立即学习“C++免费学习笔记（深入）”；
1. 构造函数与析构函数
初始化数组空间并设置初始状态：
- 分配初始容量（如 8）的数组
- front_index 和 rear_index 都设为 0
- size 设为 0
2. push_front(T value)
在队首插入元素：
- 检查是否需要扩容
- front_index 向前移动（模运算处理循环）
- 将元素放入 front_index 位置
- size 加一
3. push_back(T value)
在队尾插入元素：
- 检查是否需要扩容
- 将元素放入 rear_index 位置
- rear_index 向后移动（模 capacity）
- size 加一
4. pop_front() 和 pop_back()
分别删除队首和队尾元素：
- 检查队列是否为空
- 移动对应索引（front_index 或 rear_index）
- size 减一
5. front() 和 back()
返回队首或队尾元素的引用：
- 不修改索引，只访问对应位置的数据
6. 扩容机制（resize）
当空间不足时，分配更大的数组（如原容量 × 2），然后将旧数据按顺序复制过去，注意 front_index 到 rear_index 的环绕情况。
代码框架示例
以下是一个简化的 C++ 实现框架：
templateclass Deque { private: T* data; int capacity; int front_index; int rear_index; int size; void resize() { // 扩容并复制数据 int new_capacity = capacity * 2; T* new_data = new T[new_capacity]; int j = 0; for (int i = 0; i zuojiankuohaophpcn size; ++i) { new_data[j++] = data[(front_index + i) % capacity]; } delete[] data; data = new_data; front_index = 0; rear_index = size; capacity = new_capacity; }public: Deque(int cap = 8) : capacity(cap), front_index(0), rear_index(0), size(0) { data = new T[capacity]; }
~Deque() { delete[] data; } void push_front(const T& value) { if (size == capacity) resize(); front_index = (front_index - 1 + capacity) % capacity; data[front_index] = value; ++size; } void push_back(const T& value) { if (size == capacity) resize(); data[rear_index] = value; rear_index = (rear_index + 1) % capacity; ++size; } void pop_front() { if (empty()) throw std::runtime_error("Deque is empty"); front_index = (front_index + 1) % capacity; --size; } void pop_back() { if (empty()) throw std::runtime_error("Deque is empty"); rear_index = (rear_index - 1 + capacity) % capacity; --size; } T& front() { if (empty()) throw std::runtime_error("Deque is empty"); return data[front_index]; } T& back() { if (empty()) throw std::runtime_error("Deque is empty"); return data[(rear_index - 1 + capacity) % capacity]; } bool empty() const { return size == 0; } int get_size() const { return size; }};
使用注意事项
这种实现方式具有较好的时间效率：
- push_front、push_back、pop_front、pop_back 平均 O(1)
- 空间利用率较高，支持自动扩容
- 适合频繁在两端操作的场景
但相比 STL 的
std::deque（通常基于分块链表），此版本在极端情况下可能触发较多内存复制。STL 版本能更均匀地分布内存，减少整体复制开销。基本上就这些。自己实现有助于理解底层机制，实际开发中推荐直接使用
std::deque，它经过高度优化且接口稳定。
