在 C++ STL 中，deque 是一个非常重要的顺序容器。它的全称是 double-ended queue，中文通常翻译为 双端队列。

所谓“双端”，指的是它可以在容器的头部和尾部都进行高效的插入和删除操作。相比 vector、queue、list 等容器，deque 的使用场景更加灵活，尤其适合处理滑动窗口、单调队列、广度优先搜索等问题。

---

一、什么是 deque？

deque 是 C++ 标准模板库 STL 提供的一种容器，定义在头文件：

#include <deque>

它可以像数组一样存储一组连续逻辑上的元素，也可以像队列一样在两端进行操作。

定义一个 deque：

deque<int> dq;

这个 dq 表示一个存储 int 类型数据的双端队列。

deque 的最大特点是：

可以在队头插入元素
可以在队尾插入元素
可以从队头删除元素
可以从队尾删除元素

也就是说，deque 既不像普通队列那样只能一端进、一端出，也不像 vector 那样主要适合在尾部操作。

---

二、deque 的基本特点

deque 主要有以下几个特点：

第一，支持随机访问。

cout << dq[0] << endl;
cout << dq[1] << endl;

这点和 vector 类似。

第二，支持头尾高效插入和删除。

dq.push_front(10);
dq.push_back(20);

dq.pop_front();
dq.pop_back();

第三，不适合在中间频繁插入和删除。

虽然 deque 支持在中间插入元素，但效率通常不如 list。

第四，空间结构不是完全连续的。

vector 底层通常是一整块连续内存，而 deque 底层一般是由多段连续内存组成。因此，deque 的随机访问效率略低于 vector，但它在头部插入和删除方面比 vector 更有优势。

---

三、deque 的常用操作

下面介绍 deque 最常用的几个成员函数。

---

1. push_back：尾部插入元素

dq.push_back(10);
dq.push_back(20);
dq.push_back(30);

此时队列内容为：

10 20 30

push_back 表示从队尾加入元素。

---

2. push_front：头部插入元素

dq.push_front(5);

如果原来队列是：

10 20 30

插入后变成：

5 10 20 30

这就是 deque 相比 vector 的优势之一。

vector 如果在头部插入元素，后面的元素通常都要整体后移，效率较低。而 deque 在头部插入元素效率较高。

---

3. pop_back：删除尾部元素

dq.pop_back();

如果队列原来是：

5 10 20 30

执行后变成：

5 10 20

注意，pop_back() 只删除元素，不返回被删除的值。

如果想先获取尾部元素再删除，需要这样写：

int x = dq.back();
dq.pop_back();

---

4. pop_front：删除头部元素

dq.pop_front();

如果队列原来是：

5 10 20

执行后变成：

10 20

同样，pop_front() 只删除元素，不返回元素值。

如果需要获取队头元素：

int x = dq.front();
dq.pop_front();

---

5. front：访问队头元素

cout << dq.front() << endl;

front() 用来访问队列最前面的元素。

例如：

deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);

cout << dq.front() << endl;

输出：

10

---

6. back：访问队尾元素

cout << dq.back() << endl;

例如：

deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);

cout << dq.back() << endl;

输出：

30

---

7. empty：判断是否为空

if (dq.empty()) {
    cout << "deque 为空" << endl;
}

在使用 front()、back()、pop_front()、pop_back() 之前，最好先判断队列是否为空。

错误写法：

deque<int> dq;
cout << dq.front() << endl;

如果 dq 是空的，直接访问 front() 会导致未定义行为。

正确写法：

if (!dq.empty()) {
    cout << dq.front() << endl;
}

---

8. size：获取元素个数

cout << dq.size() << endl;

例如：

deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_back(3);

cout << dq.size() << endl;

输出：

3

---

9. clear：清空 deque

dq.clear();

清空后：

dq.size() == 0
dq.empty() == true

---

10. 使用下标访问元素

deque 支持像数组一样通过下标访问元素：

deque<int> dq = {10, 20, 30, 40};

cout << dq[0] << endl;
cout << dq[2] << endl;

输出：

10
30

不过要注意，下标不能越界。

例如：

cout << dq[100] << endl;

这是错误的。

---

四、deque 的完整基础示例

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

int main() {
    deque<int> dq;

    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);

    dq.push_front(5);
    dq.push_front(1);

    cout << "当前 deque 中的元素：" << endl;
    for (int i = 0; i < dq.size(); i++) {
        cout << dq[i] << " ";
    }
    cout << endl;

    cout << "队头元素：" << dq.front() << endl;
    cout << "队尾元素：" << dq.back() << endl;

    dq.pop_front();
    dq.pop_back();

    cout << "删除队头和队尾之后：" << endl;
    for (int x : dq) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

运行结果：

当前 deque 中的元素：
1 5 10 20 30
队头元素：1
队尾元素：30
删除队头和队尾之后：
5 10 20

---

五、deque 和 vector 的区别

vector 和 deque 都属于顺序容器，都可以用下标访问元素。

但是它们的使用场景不同。

1. vector 的特点

vector 适合：

尾部插入
随机访问
数据连续存储

例如：

vector<int> v;
v.push_back(10);
v.push_back(20);

vector 在尾部插入效率很高，但是在头部插入和删除效率较低。

比如：

v.erase(v.begin());

这个操作会导致后面的元素整体向前移动。

---

2. deque 的特点

deque 适合：

头部插入
尾部插入
头部删除
尾部删除
随机访问

例如：

deque<int> dq;
dq.push_front(10);
dq.push_back(20);
dq.pop_front();
dq.pop_back();

如果程序中需要频繁操作容器两端，那么 deque 通常比 vector 更合适。

---

3. vector 和 deque 对比表

对比项	vector	deque
头部插入	慢	快
尾部插入	快	快
头部删除	慢	快
尾部删除	快	快
随机访问	快	较快
内存连续性	完全连续	分段连续
适合场景	动态数组	双端队列、滑动窗口

---

六、deque 和 queue 的区别

queue 是普通队列，遵循先进先出原则。

queue<int> q;
q.push(10);
q.push(20);
q.pop();

queue 只能从队尾插入，从队头删除。

但是 deque 可以从两端插入和删除：

deque<int> dq;
dq.push_front(10);
dq.push_back(20);
dq.pop_front();
dq.pop_back();

所以，deque 比 queue 更灵活。

实际上，在 C++ STL 中，queue 默认底层容器就是 deque。

也就是说，普通队列 queue 很多时候是基于 deque 实现的。

---

七、deque 的时间复杂度

deque 常见操作的时间复杂度如下：

操作	时间复杂度
push_back()	O(1)
push_front()	O(1)
pop_back()	O(1)
pop_front()	O(1)
front()	O(1)
back()	O(1)
operator[]	O(1)
中间插入	O(n)
中间删除	O(n)

从这个表可以看出，deque 最擅长的就是两端操作。

但是如果经常在中间插入或删除元素，deque 并不是最好的选择。

---

八、deque 的底层原理简单理解

从逻辑上看，deque 像是一个可以从两端扩展的数组。

但是从底层实现上看，deque 通常不是一整块连续内存，而是由多个小块连续内存组成。

可以简单理解为：

deque = 多个小数组拼接起来

例如：

[块1] [块2] [块3] [块4]

每个块内部是连续的，但是整个 deque 不一定是完全连续的。

这样设计的好处是：

头部扩展方便
尾部扩展方便
不需要像 vector 那样频繁整体搬迁数据

这也是为什么 deque 可以高效地在头部和尾部插入、删除元素。

但是因为它不是完全连续内存，所以在访问速度和缓存友好性方面，通常不如 vector。

---

九、deque 的典型应用场景

1. 普通双端队列

当我们需要两端都可以进出时，可以使用 deque。

例如：

deque<int> dq;

dq.push_back(1);
dq.push_back(2);
dq.push_front(0);

dq.pop_front();
dq.pop_back();

---

2. 滑动窗口最大值

这是 deque 最经典的算法应用。

题目要求：

给定一个数组 nums 和窗口大小 k，窗口每次向右移动一位，求每个窗口中的最大值。

例如：

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3

窗口变化：

[1, 3, -1]      最大值 3
[3, -1, -3]     最大值 3
[-1, -3, 5]     最大值 5
[-3, 5, 3]      最大值 5
[5, 3, 6]       最大值 6
[3, 6, 7]       最大值 7

结果：

[3, 3, 5, 5, 6, 7]

这个问题可以用 deque 维护一个单调递减队列。

---

十、结合滑动窗口理解 deque

下面是滑动窗口最大值的核心代码：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;

        for (int i = 0; i < nums.size(); i++) {
            while (!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }

            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }

        return result;
    }
};

这段代码中：

deque<int> dq;

保存的不是元素值，而是元素下标。

也就是说，dq 里面存的是：

0, 1, 2, 3 ...

而不是：

nums[0], nums[1], nums[2] ...

为什么要存下标？

因为下标可以判断元素是否已经离开窗口。

例如当前窗口范围是：

[i - k + 1, i]

如果队头下标小于窗口左边界：

dq.front() < i - k + 1

说明这个元素已经不在窗口中了，需要删除：

dq.pop_front();

---

十一、单调队列思想

在滑动窗口最大值中，deque 维护的是一个单调递减队列。

也就是说，队列中下标对应的元素值满足：

nums[dq[0]] >= nums[dq[1]] >= nums[dq[2]]

这样一来，队头元素永远是当前窗口中的最大值。

例如：

nums = [1, 3, -1]

处理完这个窗口后，队列中可能保存：

dq = [1, 2]

对应的值是：

nums[1] = 3
nums[2] = -1

由于 3 在队头，所以当前窗口最大值就是：

nums[dq.front()] = 3

---

十二、为什么要从队尾删除较小元素？

看这段代码：

while (!dq.empty() && nums[dq.back()] < nums[i]) {
    dq.pop_back();
}

含义是：

如果当前元素 nums[i] 比队尾元素大，那么队尾元素以后不可能再成为最大值。

原因有两个：

第一，当前元素比它大。

第二，当前元素比它更靠右，会更晚离开窗口。

所以队尾这个较小元素已经没有价值，可以直接删除。

例如：

nums = [1, 3]

当遍历到 3 的时候，前面的 1 就没有必要保留。

因为只要 3 还在窗口中，1 永远不可能是最大值。

---

十三、为什么时间复杂度是 O(n)？

虽然代码中有 while 循环：

while (!dq.empty() && dq.front() < i - k + 1) {
    dq.pop_front();
}

while (!dq.empty() && nums[dq.back()] < nums[i]) {
    dq.pop_back();
}

但是每个元素最多只会：

入队一次
出队一次

一个下标进入 deque 后，之后要么从队头弹出，要么从队尾弹出，不会反复进出。

所以总时间复杂度是：

O(n)

空间复杂度是：

O(k)

因为队列中保存的是当前窗口附近的元素下标。

---

十四、deque 的优点

deque 的主要优点包括：

第一，头尾操作效率高。

push_front()
push_back()
pop_front()
pop_back()

这些操作通常都是 O(1)。

第二，支持随机访问。

dq[i]

第三，比 queue 更灵活。

queue 只能队尾进、队头出，而 deque 两端都可以进出。

第四，适合实现单调队列。

在滑动窗口问题中，deque 是非常常用的容器。

---

十五、deque 的缺点

deque 也不是万能的。

它有几个缺点：

第一，缓存性能通常不如 vector。

因为 vector 是连续内存，而 deque 是分段连续内存。

第二，中间插入和删除效率不高。

例如：

dq.insert(dq.begin() + 2, 100);
dq.erase(dq.begin() + 3);

这类操作可能需要移动元素，时间复杂度通常是 O(n)。

第三，使用上比 vector 稍微复杂。

尤其是在算法题中，deque 经常和下标、窗口边界、单调性结合使用，对初学者来说需要多练习。

---

十六、deque 适合什么时候使用？

如果你的程序需要频繁在两端进行插入和删除操作，优先考虑 deque。

适合使用 deque 的情况：

需要从队头删除元素
需要从队尾删除元素
需要从队头插入元素
需要从队尾插入元素
需要维护滑动窗口
需要维护单调队列

不太适合使用 deque 的情况：

只需要尾部插入和随机访问
需要极高的遍历效率
需要连续内存
需要频繁在中间插入和删除

如果只是在尾部插入、遍历和随机访问，一般 vector 更合适。

如果需要频繁在中间插入和删除，一般 list 更合适。

如果需要普通先进先出队列，可以使用 queue。

如果需要两端操作，就使用 deque。

---

十七、常见易错点

1. 空队列不能直接访问 front 和 back

错误写法：

deque<int> dq;
cout << dq.front() << endl;

正确写法：

if (!dq.empty()) {
    cout << dq.front() << endl;
}

---

2. pop_front 和 pop_back 不返回元素

错误理解：

int x = dq.pop_front();

这是错误的。

正确写法：

int x = dq.front();
dq.pop_front();

---

3. 下标访问不能越界

错误写法：

cout << dq[100] << endl;

如果 dq 没有这么多元素，会发生错误。

---

4. 滑动窗口中通常存下标，不是存值

在滑动窗口最大值中，建议存下标：

deque<int> dq;

因为下标可以判断元素是否过期。

如果只存值，很难判断某个值是否已经离开窗口。

---

十八、总结

deque 是 C++ STL 中非常重要的容器，它的核心特点是：

可以在头部和尾部高效插入、删除元素
支持随机访问
适合实现双端队列和单调队列

与 vector 相比，deque 的头部操作更高效。

与 queue 相比，deque 的操作更加灵活。

在算法题中，deque 最经典的应用就是滑动窗口最大值。通过维护一个单调递减队列，可以把原本 O(n * k) 的暴力算法优化为 O(n)。

可以用一句话概括 deque：

deque 是一种既像数组、又像队列的 STL 容器，它兼具随机访问能力和双端高效操作能力，特别适合处理滑动窗口、单调队列等问题。