双端队列可通过动态数组实现，支持首尾插入删除。使用循环缓冲与自动扩容，关键操作均摊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 都设为 0size 设为 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++ 实现框架：
template class 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 < 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，它经过高度优化且接口稳定。
以上就是C++如何实现一个双端队列(deque)_C++数据结构与双端队列实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1483397.html
微信扫一扫 
支付宝扫一扫 
