C++ STL 双端队列 deque 详细介绍

在 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 对比表

六、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常见操作的时间复杂度如下：

从这个表可以看出，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 容器，它兼具随机访问能力和双端高效操作能力，特别适合处理滑动窗口、单调队列等问题。