双端队列（Deque，Double-Ended Queue）是一个既支持从头部又支持从尾部高效插入和删除元素的数据结构。它比普通队列更加灵活，常见于任务调度、双向遍历等场景。本文将演示如何使用C++模板编写一个轻量级的双端队列实现，并讨论其设计细节与性能优化。
1. 设计目标
- 通用性：使用模板实现，支持任意类型的元素。
- 高效：在常数时间内完成插入、删除以及访问操作。
- 简洁：代码保持易读易维护，采用标准库工具而非裸指针。
- 可扩展：易于在未来添加迭代器、异常安全和多线程支持等功能。
2. 基本思路
我们采用循环缓冲区（circular buffer）实现，内部使用 `std::vector
` 存储元素。通过维护 **front index**（表示队列首部的位置）和 **size**（当前元素数）即可完成所有操作。该方式的优点是： – **连续内存**：更好的缓存友好性，减少内存碎片。 – **无额外分配**：所有空间一次性预留，避免频繁 `new`/`delete`。 ### 2.1 关键成员 | 成员 | 类型 | 说明 | |——|——|——| | `std::vector data_` | vector | 真实存储区 | | `size_t front_` | size_t | 当前队首索引 | | `size_t size_` | size_t | 当前元素数量 | | `size_t capacity_` | size_t | 容量（等于 `data_.size()`） | ### 2.2 辅助函数 – `index(size_t pos)`：将逻辑位置映射到实际缓冲区索引，使用 `(front_ + pos) % capacity_`。 – `grow()`：当容量已满时，扩容为原来的两倍并重新布局元素。 ## 3. 代码实现 “`cpp #pragma once #include #include #include #include #include template class Deque { public: // 默认构造，容量 8 Deque() : data_(8), front_(0), size_(0), capacity_(8) {} // 通过范围初始化 template Deque(InputIt first, InputIt last) { for (auto it = first; it != last; ++it) push_back(*it); } // 初始化列表构造 Deque(std::initializer_list init) { for (const auto& v : init) push_back(v); } // 访问大小 size_t size() const noexcept { return size_; } bool empty() const noexcept { return size_ == 0; } // 随机访问（不建议频繁使用，O(n)） T& operator[](size_t idx) { if (idx >= size_) throw std::out_of_range(“Index out of range”); return data_[index(idx)]; } const T& operator[](size_t idx) const { if (idx >= size_) throw std::out_of_range(“Index out of range”); return data_[index(idx)]; } // 前端操作 void push_front(const T& val) { insert_at_front(val); } void push_front(T&& val) { insert_at_front(std::move(val)); } T pop_front() { if (empty()) throw std::out_of_range(“Deque is empty”); T val = std::move(data_[front_]); front_ = (front_ + 1) % capacity_; –size_; return val; } // 后端操作 void push_back(const T& val) { insert_at_back(val); } void push_back(T&& val) { insert_at_back(std::move(val)); } T pop_back() { if (empty()) throw std::out_of_range(“Deque is empty”); size_t idx = (front_ + size_ – 1) % capacity_; T val = std::move(data_[idx]); –size_; return val; } // 访问首尾元素 T& front() { return data_[front_]; } const T& front() const { return data_[front_]; } T& back() { return data_[(front_ + size_ – 1) % capacity_]; } const T& back() const { return data_[(front_ + size_ – 1) % capacity_]; } private: std::vector data_; size_t front_; size_t size_; size_t capacity_; size_t index(size_t pos) const noexcept { return (front_ + pos) % capacity_; } void grow() { size_t new_cap = capacity_ * 2; std::vector new_data(new_cap); for (size_t i = 0; i #include “deque.hpp” int main() { Deque dq{1, 2, 3}; dq.push_front(0); // 0 1 2 3 dq.push_back(4); // 0 1 2 3 4 std::cout