C++双端队列详解（从零开始掌握deque的使用与实现）

什么是双端队列？

双端队列（deque）是一种线性数据结构，它结合了栈和队列的优点：

• 可以在前端（front）和后端（back）同时插入或删除元素；
• 支持随机访问（通过下标）；
• 时间复杂度通常为 O(1) 的首尾操作。

C++ STL 中的 deque

C++ 标准模板库（STL）已经为我们提供了高度优化的 std::deque 容器。你不需要自己从头实现，只需包含头文件即可使用。

首先，引入头文件：

#include <deque>#include <iostream>using namespace std;

常用操作示例

下面是一个完整的 C++ STL deque 使用示例，涵盖基本操作：

#include <deque>#include <iostream>using namespace std;int main() {    deque<int> dq;    // 在尾部添加元素    dq.push_back(10);    dq.push_back(20);    // 在头部添加元素    dq.push_front(5);    dq.push_front(1);    // 输出当前deque内容    cout << "Deque elements: ";    for (int x : dq) {        cout << x << " ";    }    cout << endl; // 输出: 1 5 10 20    // 访问首尾元素    cout << "Front: " << dq.front() << ", Back: " << dq.back() << endl;    // 删除首尾元素    dq.pop_front();    dq.pop_back();    cout << "After pop: ";    for (int x : dq) {        cout << x << " ";    }    cout << endl; // 输出: 5 10    return 0;}

为什么选择 deque 而不是 vector 或 list？

- vs vector：vector 在尾部操作高效，但头部插入/删除是 O(n)；而 deque 在两端都是 O(1)。
- vs list：list 支持任意位置 O(1) 插入，但不支持随机访问；deque 支持下标访问（如 dq[2]），且内存更连续，缓存友好。

简单自定义双端队列（教学用途）

虽然实际开发中推荐使用 STL 的 std::deque，但为了加深理解，我们可以用动态数组模拟一个简易版 deque（仅用于学习）：

#include <iostream>#include <vector>using namespace std;class SimpleDeque {private:    vector<int> data;public:    void push_front(int val) {        data.insert(data.begin(), val);    }    void push_back(int val) {        data.push_back(val);    }    void pop_front() {        if (!data.empty())            data.erase(data.begin());    }    void pop_back() {        if (!data.empty())            data.pop_back();    }    int front() { return data.front(); }    int back()  { return data.back();  }    bool empty() { return data.empty(); }    size_t size() { return data.size(); }};// 注意：这个实现效率较低（insert/erase 开销大），仅用于理解概念

⚠️ 提醒：上述自定义版本不推荐用于生产环境，因为 vector::insert 在开头操作的时间复杂度是 O(n)。真正的 std::deque 内部采用分段连续内存块实现，保证两端操作均为 O(1)。

总结

通过本教程，你已经掌握了：

• 什么是 C++双端队列（deque）；
• 如何使用 C++ STL deque 进行常见操作；
• deque 与其他容器（vector、list）的区别；
• 一个教学用的简易 deque 实现（加深理解）。

记住，在实际项目中，请优先使用标准库提供的 std::deque，它经过高度优化，安全且高效。希望这篇 双端队列教程 对你有所帮助！