困难通用8 分钟2,870 字

deque双端队列详解

开场白:这是什么神奇队列?

你见过那种两边都能开门的地铁车厢​吗?乘客可以从左边门上车,也可以从右边门下车,非常灵活。在编程中,也有这样一种容器,它允许你在开头​和结尾​都以极快的速度添加或删除元素——这就是 deque​​(读作“deck”),全称 double-ended queue(双端队列)。

想象一下你的零食盒​​:你可以从前面拿刚买的薯片,也可以从后面塞进新买的糖果,两头都能操作。当你只从一头操作时,它就像普通的队列或栈;但当你需要两头操作时,它就是你的最佳选择。

如果你学过 vector(动态数组)和 list(链表),那么 deque 就像它们的“合体版”:既有 vector 的随机访问能力,又有 list 的前后快速插入能力(但中间插入还是慢)。接下来我们就一步步揭开它的神秘面纱。

一、deque 的核心特点

  • 两端快速插入/删除​​:push_front(头插)、pop_front(头删)、push_back(尾插)、pop_back(尾删)的时间都是 O(1)​​,超级快。
  • 随机访问​​:可以通过 [索引] 或 at(索引) 直接访问任意位置的元素,也是 O(1)​​,但比 vector 稍慢一点点(因为内部需要多一次跳转)。
  • 逻辑连续​​:看起来像一条完整的队伍,但实际上底层由多块小内存(缓冲区)拼接而成。这样,在两端添加新元素时,只需要分配新的小块,不用像 vector 那样把整条队伍的人全部往后搬。
  • 没有 reserve​​:deque 不需要像 vector 那样提前预留空间,因为它是按需分配小块的。

生活中的对照​​:

  • 学校的值日安排​​:你可以在周一早上把新同学安排到队首,也可以在周五下午把表现不好的同学放到队尾。
  • 游戏的技能快捷键​​:你可以把紧急技能(如回血)放在技能栏最左边(头),普通技能放在右边(尾),随时可以在两头调整。

二、常见操作与语法(C++)

1. 头文件与创建

cpp
#include <deque>   // 使用deque需要包含头文件

deque<int> dq;                // 创建一个空的int型双端队列
deque<string> names(5);       // 创建包含5个空字符串的双端队列
deque<double> scores(3, 0.0); // 创建3个0.0的双端队列

2. 添加元素

cpp
dq.push_back(10);   // 在尾部添加10
dq.push_front(20);  // 在头部添加20
dq.push_back(30);   // 现在队列为:20, 10, 30

注意​​:没有 insert 的演示?其实 deque 也有 insert 可以在中间插入,但速度很慢(O(n)),所以很少用。我们重点掌握头尾操作。

3. 删除元素

cpp
dq.pop_back();   // 删除尾部元素(30),剩下20,10
dq.pop_front();  // 删除头部元素(20),剩下10

小心:如果队列是空的,调用 pop_back 或 pop_front 会导致程序崩溃(未定义行为),所以要先用 empty() 判断。

4. 访问元素

cpp
int first = dq.front();   // 返回第一个元素(不删除)
int last = dq.back();     // 返回最后一个元素
int pos = dq[0];          // 通过下标访问,不检查越界
int safe = dq.at(0);      // 通过at访问,越界会抛出异常

5. 大小与清空

cpp
int n = dq.size();    // 返回元素个数
bool empty = dq.empty(); // 是否为空
dq.clear();           // 清空所有元素
dq.resize(10);        // 调整为10个元素,如果变长则用默认值填充

三、内部原理(用“教室”比喻)

很多同学问:为什么 deque 两端操作这么快?我们来打个比方。

想象你有一排教室(缓冲区)​​​,每个教室里有固定数量的座位(比如4个座位)。这些教室之间通过一条走廊(中控数组)​​连接。当你要在队伍头部插入一个人时:

  • 如果头部的教室还有空座位,直接坐进去,O(1)。
  • 如果头部的教室满了,就在走廊最前面接一个新教室,让人坐进去,也是O(1)。

当你要随机访问第5个人时:

  • 先通过走廊找到是第几个教室(比如第2个教室)。
  • 再在该教室里找到具体的座位(比如座位1)。 所以比直接在一个大教室(vector)里找多了一步,但还是很快。

而 vector 则像一个大礼堂,所有人必须按顺序坐。如果在最前面加一个人,所有人都要往后挪一个位置,非常慢(O(n))。但 vector 的随机访问就像直接报座位号,一步到位,超级快。

所以 deque 在两端操作上完胜 vector,在随机访问上稍逊一筹,但在中间插入上两者都很慢(都要搬动很多元素)。

四、常见错误(新手必看)

错误1:在中间频繁插入(以为和list一样快)

cpp
deque<int> dq = {1,2,3,4,5};
for (int i = 0; i < 100000; i++) {
    dq.insert(dq.begin() + dq.size()/2, i);  // 每次都在中间插入
}

后果​​:每次插入都需要移动一半的元素,慢到爆炸。如果你需要频繁在中间插入,请使用 list。

错误2:对空deque调用pop_front或pop_back

cpp
deque<int> empty;
empty.pop_front();  // 崩溃!因为队列为空

正确做法​​:先判断 if (!empty.empty()) empty.pop_front();

错误3:把deque当作vector来reserve

cpp
deque<int> dq;
dq.reserve(100);  // 编译错误!deque没有reserve函数

因为 deque 不需要预先分配连续空间,所以没有 reserve。

错误4:误以为deque的随机访问和vector一样快

虽然都是O(1),但 deque 的常数更大。如果你要写一个需要超级大量随机访问的程序(比如图形处理),vector 更合适。

错误5:在Python中使用list当双端队列

python
queue = []
queue.insert(0, "小明")   # 头部插入,list是O(n)
queue.pop(0)              # 头部删除,list是O(n)

正确做法:使用 collections.deque。

五、完整可运行示例(C++)

下面是一个完整的程序,用“电影院卖爆米花”的场景,展示 deque 的各种操作。每一行变量定义都加了中文注释。

cpp
#include <iostream>
#include <deque>       // 双端队列头文件
#include <algorithm>   // sort函数
#include <string>      // string类型
using namespace std;

int main() {
    // 创建一个双端队列,存放顾客的名字(string类型)
    deque<string> customer_queue;

    // 尾部添加:三个人依次买爆米花
    customer_queue.push_back("小明");
    customer_queue.push_back("小红");
    customer_queue.push_back("小刚");
    cout << "初始排队顺序: ";
    for (const string& name : customer_queue) cout << name << " ";
    cout << endl;

    // 头部插队:小明妈妈来了,要求排到最前面
    customer_queue.push_front("小明妈妈");
    cout << "小明妈妈插队后: ";
    for (const string& name : customer_queue) cout << name << " ";
    cout << endl;

    // 访问队头和队尾
    cout << "现在队头是: " << customer_queue.front() << endl;  // 小明妈妈
    cout << "队尾是: " << customer_queue.back() << endl;       // 小刚

    // 队头离开(小明妈妈买完走了)
    customer_queue.pop_front();
    cout << "小明妈妈离开后队头变成: " << customer_queue.front() << endl; // 小明

    // 队尾离开(小刚等不及走了)
    customer_queue.pop_back();
    cout << "小刚离开后队尾变成: " << customer_queue.back() << endl; // 小红

    // 随机访问:通过下标获取第二个人(索引1)
    cout << "现在队列中第2个人是: " << customer_queue[1] << endl; // 现在只有小明(0)和小红(1),所以是小红

    // 使用at安全访问(越界会抛出异常)
    try {
        cout << "尝试访问索引5(越界): " << customer_queue.at(5) << endl;
    } catch (const out_of_range& e) {
        cout << "访问越界, 异常信息: " << e.what() << endl;
    }

    // 修改元素:把小明改名为“大明”
    customer_queue[0] = "大明";
    cout << "修改后队列为: ";
    for (const string& name : customer_queue) cout << name << " ";
    cout << endl;

    // 清空队列
    customer_queue.clear();
    cout << "清空后队列大小: " << customer_queue.size() << endl; // 0

    // ---------- 下面用整数演示排序 ----------
    // 创建一个整型双端队列
    deque<int> score_queue;
    score_queue.push_back(85);    // 尾部添加85
    score_queue.push_back(92);    // 尾部添加92
    score_queue.push_front(78);   // 头部添加78
    score_queue.push_front(88);   // 头部添加88
    // 现在队列: 88, 78, 85, 92
    cout << "排序前数字: ";
    for (int v : score_queue) cout << v << " ";
    cout << endl;

    // 排序:deque的迭代器是随机访问迭代器,可以直接用sort
    sort(score_queue.begin(), score_queue.end());
    cout << "排序后数字: ";
    for (int v : score_queue) cout << v << " ";
    cout << endl;

    return 0;
}

运行结果:

初始排队顺序: 小明 小红 小刚
小明妈妈插队后: 小明妈妈 小明 小红 小刚
现在队头是: 小明妈妈
队尾是: 小刚
小明妈妈离开后队头变成: 小明
小刚离开后队尾变成: 小红
现在队列中第2个人是: 小红
访问越界, 异常信息: deque::_M_range_check: __n (which is 5) >= this->size() (which is 2)
修改后队列为: 大明 小红
清空后队列大小: 0
排序前数字: 88 78 85 92
排序后数字: 78 85 88 92

六、Python中的双端队列(collections.deque)

Python标准库的 collections.deque 和C++的 deque 几乎一模一样,也是两端O(1)操作。下面是对应的代码,每行也有中文注释:

python
from collections import deque

# 创建一个空双端队列,存放顾客名字
customer_queue = deque()

# 尾部添加
customer_queue.append("小明")
customer_queue.append("小红")
customer_queue.append("小刚")
print("初始排队顺序:", list(customer_queue))

# 头部插队
customer_queue.appendleft("小明妈妈")
print("小明妈妈插队后:", list(customer_queue))

# 访问队头和队尾(用索引0和-1)
print("队头:", customer_queue[0])   # 小明妈妈
print("队尾:", customer_queue[-1])  # 小刚

# 头部离开
customer_queue.popleft()
print("小明妈妈离开后队头:", customer_queue[0])  # 小明

# 尾部离开
customer_queue.pop()
print("小刚离开后队尾:", customer_queue[-1])    # 小红

# 随机访问:通过索引
print("第2个人:", customer_queue[1])  # 现在只有小明(0)和小红(1),所以是小红

# 修改元素
customer_queue[0] = "大明"
print("修改后队列:", list(customer_queue))

# 清空
customer_queue.clear()
print("清空后长度:", len(customer_queue))

# ---------- 整数排序演示 ----------
score_queue = deque()
score_queue.append(85)
score_queue.append(92)
score_queue.appendleft(78)
score_queue.appendleft(88)
print("排序前:", list(score_queue))  # [88, 78, 85, 92]

# 排序:deque没有sort方法,需要转成list排序再转回deque
sorted_scores = deque(sorted(score_queue))
print("排序后:", list(sorted_scores))  # [78, 85, 88, 92]

Python的特别提醒​​:

  • deque 也支持 rotate(n) 方法,可以把元素循环左移或右移,比如 dq.rotate(1) 相当于把最后一个元素放到开头。C++的deque没有这个功能。
  • 虽然 deque 支持通过索引随机访问,但底层也是分段存储,速度比list慢一点点(但差别不大,一般场景感觉不到)。
  • 不要用 list 来模拟双端队列的头插头删,因为list是数组,头部插入是O(n)。

七、实战应用:滑动窗口最大值

这是一个很经典的算法题,特别适合用 deque 解决。比如你有一串数字,要找出每个长度为k的子数组中的最大值。用 deque 维护窗口内可能有用的索引,效率超级高。

(这里简单提一下,不展开代码,作为相关指引)

八、总结与相关指引

什么时候该用deque?

  • 双端操作频繁​​:比如任务队列,紧急任务插队到队头,普通任务放到队尾。
  • 需要偶尔随机访问​​:比如要查看队伍中第几个人的名字。
  • 不需要在中间插入/删除​​:如果中间操作很多,用 list 更好。
  • 不想预先分配空间​​:deque 不需要 reserve。

和vector、list的对比

操作 deque vector list
头插/头删 O(1) O(n) O(1)
尾插/尾删 O(1) 均摊O(1) O(1)
随机访问 O(1)(稍慢) O(1) O(n)
中间插入 O(n) O(n) O(1)(需先找到位置)
内存占用 中 小(连续) 大(每个节点额外指针)

你还可以学习

  • stack和queue​​:它们都是基于 deque 的容器适配器(默认底层就是deque),所以如果你只需要栈或队列的功能,直接用它们更简单。
  • priority_queue​​:优先级队列,底层是堆,适合需要按优先级取出的场景。
  • 算法题中的滑动窗口​​:这是deque的经典应用。

现在你已经完全掌握了双端队列!下次写程序时,如果需要两头操作,别犹豫,直接用 deque 吧。它就像你的多功能工具箱,随手可得,又快又方便。

同类知识点