deque 双端队列

读完能做什么

• 能创建 deque，用 push_front、push_back 在两端加入元素，用 pop_front、pop_back 在两端删除元素，并说出每一步之后的内容、size() 和两端分别是哪个值。
• 能用下标和 at() 访问任意位置的元素，并说出 deque 和 vector 在“能不能从头部增删”上的区别。
• 能解释 deque 和普通排队（queue）的区别：一个是能随便操作两端的容器，一个只允许“一头进、一头出”。
• 能说出 deque 没有 capacity() / reserve()，以及空容器不能取端点、不能弹出端点。

为什么需要它

vector 很好用，但只能高效地在尾部增删。如果任务要求“在头部也能加数据”，用 vector 就得写 v.insert(v.begin(), x)：

vector<int> v = {20, 30};
v.insert(v.begin(), 10);        // 片段：头部插入要把所有元素整体右移一格

这是一段片段（省略了头文件与 main）。它没有语法错误，但每次在头部插入，已有的元素全部要往右挪一格，元素越多越慢，是 O(n)。而“头部插入”在竞赛里很常见：滑动窗口、双端队列优化的动态规划、两边都能进出的模拟题……

我们需要的是一种两端都能快速增删、同时还能像数组一样按下标访问的容器，这就是 deque（读作 “deck”，是 double-ended queue 的缩写）。

它是什么

一句话：deque 是标准库提供的双端队列——在头部和尾部都能高效地加入、删除元素，同时支持像数组一样按下标随机访问。

直观模型是一段可以向左、向右延伸的序列，两端都是“开口”的：

graph LR
    L["头部 front：能加入、能删除"] --- M["中间：按下标访问，插删较慢"] --- R["尾部 back：能加入、能删除"]

以 [20, 30] 为例，下标仍然从 0 开始，front() 是头部、back() 是尾部：

deque 和 vector 的区别。 两者都能按下标随机访问，主要差别在头部：deque 的头部增删是高效的，vector 的头部增删要把所有元素整体搬动。反过来说，vector 是一整块连续内存，deque 为了做到两端都能扩展，内部把数据分成若干段管理——这是实现细节，不影响使用，本页只需要记住“两端都快，中间插删慢”。

deque 和 queue 的区别。 名字里都有 “queue”，但完全是两种东西：

queue 只允许“一头进、一头出”，正是为了强制“先来先处理”的规则，细节见 queue 队列。deque 不做这种限制，所以它更自由，也就要自己保证不乱套。

随机访问容器，但没有 capacity() / reserve()。 deque 的迭代器支持 it + n 和相减（这叫随机访问迭代器），所以能 d[2]、也能 d.begin() + 2。但 vector 上的 capacity()、reserve() 在 deque 上不存在：deque 的内存是一段一段申请的，没有“当前这一块能装几个”这个概念。写 d.reserve(10) 会直接编译失败。

模板尖括号。 deque<int> 里的 <int> 表示容器里放什么类型，deque<string> 就是存字符串的双端队列。这是 C++ 的模板语法，只需照着填类型。

适用场景：需要在两端频繁增删、同时又要按下标随机访问的数据。使用时要 #include <deque>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件（这两句的解释在什么是 STL）。

最小可运行示例

数据写在代码里，不需要输入：

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> d = {20, 30};             // 两端都能操作的序列

    cout << "size = " << d.size() << '\n';
    cout << "d[0] = " << d[0] << ", d[1] = " << d[1] << '\n';
    cout << "front = " << d.front() << ", back = " << d.back() << '\n';

    d[0] = 25;                           // 支持像数组一样用下标改写
    cout << "改 d[0] 后：";
    for (int i = 0; i < (int)d.size(); i++) cout << d[i] << ' ';
    cout << '\n';
    return 0;
}

输出：

size = 2
d[0] = 20, d[1] = 30
front = 20, back = 30
改 d[0] 后：25 30 

逐行看：

• deque<int> d = {20, 30}; 创建一个 deque<int>，按顺序放入 2 个元素，下标 0 和 1。
• d.size() 是元素个数 2。循环里写 (int)d.size() 是为了和 int i 比较时不出现“有符号与无符号比较”的警告。
• d[0] 是头部元素、d[1] 是尾部元素；front() 读头部，back() 读尾部。只有两个元素时，d[0] 和 front() 是同一个，d[1] 和 back() 是同一个。
• d[0] = 25 用下标直接改写头部元素，长度仍是 2。

一步步看变化

沿 [20, 30] 这组数据走完“两端加入 → 两端删除”的完整路线：

每一步的“操作后”都对应输出里的一行：

#include <bits/stdc++.h>
using namespace std;

void printDeque(const string& tag, const deque<int>& d) {
    cout << tag << "：[";
    for (int i = 0; i < (int)d.size(); i++) {
        if (i > 0) cout << ",";
        cout << d[i];
    }
    cout << "] size = " << d.size()
         << ", front = " << d.front() << ", back = " << d.back() << '\n';
}

int main() {
    deque<int> d = {20, 30};
    printDeque("初始", d);

    d.push_front(10);
    printDeque("push_front(10) 后", d);

    d.push_back(40);
    printDeque("push_back(40) 后", d);

    d.pop_front();
    printDeque("pop_front() 后", d);

    d.pop_back();
    printDeque("pop_back() 后", d);
    return 0;
}

输出：

初始：[20,30] size = 2, front = 20, back = 30
push_front(10) 后：[10,20,30] size = 3, front = 10, back = 30
push_back(40) 后：[10,20,30,40] size = 4, front = 10, back = 40
pop_front() 后：[20,30,40] size = 3, front = 20, back = 40
pop_back() 后：[20,30] size = 2, front = 20, back = 30

几点说明：

• printDeque 的参数是 const deque<int>&，用引用避免复制整个容器，const 表示函数里不会改动它。这是“只想看一眼内容”的标准写法（引用的解释见 vector 动态数组）。
• 第 1 步的 10 出现在头部：逻辑上下标整体往后一位——原来的 20 变成 d[1]、30 变成 d[2]；元素本身没有被搬动，这正是 deque 头部插入高效（摊还 O(1)）的原因。
• 第 2 步的 40 出现在尾部，前面的元素下标不变，新元素的下标是 size() - 1。
• pop_front() 删掉头部、pop_back() 删掉尾部，两者都不返回被删掉的值。想用这个值就先 front() / back() 取出来再删。
• 两步删除之后回到 [20,30]，和初始状态一样——push_front(10) 加入的 10 和 push_back(40) 加入的 40 都被删掉了。

每一步的头部和尾部各是哪个值，可以只看这张表对照：

逐项扩展核心操作

两端加入：push_front 与 push_back

#include <bits/stdc++.h>
using namespace std;

void printDeque(const deque<int>& d) {
    cout << "[";
    for (int i = 0; i < (int)d.size(); i++) {
        if (i > 0) cout << ",";
        cout << d[i];
    }
    cout << "] size = " << d.size() << '\n';
}

int main() {
    deque<int> d = {20, 30};
    cout << "操作前：";
    printDeque(d);

    d.push_front(10);                    // 从头部加入 10

    cout << "操作后：";
    printDeque(d);
    cout << "front = " << d.front() << ", back = " << d.back() << '\n';
    return 0;
}

输出：

操作前：[20,30] size = 2
操作后：[10,20,30] size = 3
front = 10, back = 30

push_front(10) 把 10 放到头部，长度加 1，新的 front() 变成 10，back() 仍是 30。这正是 vector 做不到的高效操作。

push_back 放在尾部，和 vector 一样：

#include <bits/stdc++.h>
using namespace std;

void printDeque(const deque<int>& d) {
    cout << "[";
    for (int i = 0; i < (int)d.size(); i++) {
        if (i > 0) cout << ",";
        cout << d[i];
    }
    cout << "] size = " << d.size() << '\n';
}

int main() {
    deque<int> d = {10, 20, 30};
    cout << "操作前：";
    printDeque(d);

    d.push_back(40);                     // 从尾部加入 40

    cout << "操作后：";
    printDeque(d);
    cout << "front = " << d.front() << ", back = " << d.back() << '\n';
    return 0;
}

输出：

操作前：[10,20,30] size = 3
操作后：[10,20,30,40] size = 4
front = 10, back = 40

两端删除：pop_front 与 pop_back

#include <bits/stdc++.h>
using namespace std;

void printDeque(const deque<int>& d) {
    cout << "[";
    for (int i = 0; i < (int)d.size(); i++) {
        if (i > 0) cout << ",";
        cout << d[i];
    }
    cout << "] size = " << d.size() << '\n';
}

int main() {
    deque<int> d = {10, 20, 30, 40};
    cout << "操作前：";
    printDeque(d);

    d.pop_front();                       // 删除头部元素 10，不返回它的值

    cout << "操作后：";
    printDeque(d);
    cout << "front = " << d.front() << ", back = " << d.back() << '\n';
    return 0;
}

输出：

操作前：[10,20,30,40] size = 4
操作后：[20,30,40] size = 3
front = 20, back = 40

pop_back() 对称地删掉尾部元素：

#include <bits/stdc++.h>
using namespace std;

void printDeque(const deque<int>& d) {
    cout << "[";
    for (int i = 0; i < (int)d.size(); i++) {
        if (i > 0) cout << ",";
        cout << d[i];
    }
    cout << "] size = " << d.size() << '\n';
}

int main() {
    deque<int> d = {20, 30, 40};
    cout << "操作前：";
    printDeque(d);

    d.pop_back();                        // 删除尾部元素 40

    cout << "操作后：";
    printDeque(d);
    cout << "front = " << d.front() << ", back = " << d.back() << '\n';
    return 0;
}

输出：

操作前：[20,30,40] size = 3
操作后：[20,30] size = 2
front = 20, back = 30

pop_front() 和 pop_back() 都是 void，没有返回值：它们只负责删除，不告诉你删掉了谁。想用被删的值，先取再删：

int x = d.front();      // 先取出来
d.pop_front();          // 再删掉

这是片段，省略了头文件与 main。写成 int x = d.pop_front(); 会编译失败，因为 void 不能赋值给 int。

访问与遍历：下标、at、迭代器

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> d;
    d.push_back(20);
    d.push_back(30);
    d.push_front(10);
    d.push_back(40);

    cout << "遍历（从头部到尾部）：";
    for (int i = 0; i < (int)d.size(); i++) cout << d[i] << ' ';
    cout << '\n';

    cout << "front = " << d.front() << ", back = " << d.back() << '\n';
    cout << "d.at(2) = " << d.at(2) << '\n';       // 带越界检查的访问

    deque<int>::iterator it = d.begin();           // 迭代器也能用
    it = it + 2;                                   // deque 支持随机访问：it + n
    cout << "*(begin() + 2) = " << *it << '\n';
    return 0;
}

输出：

遍历（从头部到尾部）：10 20 30 40 
front = 10, back = 40
d.at(2) = 30
*(begin() + 2) = 30

• d[i] 和 d.at(i) 都能按下标读，区别是 at 会检查越界并在越界时抛异常，[] 不检查。竞赛代码一般用 []，越界责任在自己。
• for (int x : d) 这种范围 for 也能用，效果和下标遍历一样。
• d.begin() 是指向头部的迭代器（表示位置的游标），d.begin() + 2 指向下标 2；*it 取出它指向的元素。deque 支持 it + n 和两个迭代器相减，这叫随机访问迭代器，和 vector、string 一样。迭代器的系统讲解见容器、迭代器与区间。

清空与重新使用

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> d;

    cout << "空容器：size = " << d.size() << ", empty = " << d.empty() << '\n';

    d.push_back(1);
    d.push_front(2);
    d.push_back(3);
    cout << "push_back(1)、push_front(2)、push_back(3) 后：";
    for (int x : d) cout << x << ' ';
    cout << '\n';

    d.clear();                           // 删掉全部元素
    cout << "clear 后：size = " << d.size() << ", empty = " << d.empty() << '\n';

    d.push_front(7);                     // 清空后还能继续用
    cout << "再 push_front(7) 后：front = " << d.front() << ", size = " << d.size() << '\n';
    return 0;
}

输出：

空容器：size = 0, empty = 1
push_back(1)、push_front(2)、push_back(3) 后：2 1 3 
clear 后：size = 0, empty = 1
再 push_front(7) 后：front = 7, size = 1

• 空 deque 的 size() 是 0，empty() 返回 true，打印成 1。
• 三次加入的顺序是“尾、头、尾”，所以最终顺序是 2 1 3：先 push_back(1) 得到 [1]，再 push_front(2) 得到 [2,1]，最后 push_back(3) 得到 [2,1,3]。加入的先后不等于排列的先后，位置由你选的是哪一端决定。
• clear() 一次删掉所有元素，size() 变 0。清空后的容器可以继续使用，不需要重新创建。

空容器不能取端点

// 错误示例：空 deque 既不能取端点，也不能弹出端点
#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> d;                        // d 是空的

    cout << d.front() << '\n';           // 空容器没有首元素，结果不确定
    cout << d.back() << '\n';            // 空容器没有尾元素，结果不确定
    d.pop_front();                       // 空容器没有元素可删，结果不确定
    return 0;
}

这段不能作为程序使用。空容器上调用 front()、back()、pop_front()、pop_back() 都属于越界访问，标准没有规定结果：可能读到垃圾值，也可能直接崩溃（本机实测这份代码以退出码 134 中止）。所以取端点之前先判断非空，固定写法是 while (!d.empty())，或者 if (!d.empty()) { ... }。空容器上可以安全调用的是 size()、empty()、push_front()、push_back()、clear()。

什么时候选它、哪里容易错

空容器不能直接访问或弹出端点。 front()、back()、pop_front()、pop_back() 都要求容器非空。竞赛里最常见的崩溃就是“忘了判空”。判空用 d.empty() 或 d.size() == 0。

两端高效不代表所有位置都同样高效。 在头部、尾部增删是常数时间；在中间 insert、erase 仍然要搬动元素，代价与元素个数成正比（而且要传迭代器，不是下标）。如果任务只是“两端进出”，deque 很合适；如果还要在中间频繁插删，应该考虑 list 链表。

没有 capacity() 和 reserve()。 deque 的内存是分段管理的，没有“当前这一块能放几个”的概念。写 d.capacity() 或 d.reserve(10) 都会编译失败。想预先占好空间是 vector 才有的做法。

按下标访问不检查越界。 d[i] 和 vector 一样不做检查，d[d.size()] 是越界访问，结果不确定。要检查就用 d.at(i)，越界会抛异常。

pop_front() / pop_back() 没有返回值。 它们是 void，取值和删除要分两步。

用 deque 模拟排队时，规则得自己守。 deque 允许从两端任意操作，queue 只允许一头进一头出。如果任务是“先来先处理”，用 queue 队列 更不容易写错；deque 适合“两端都要用”的场景。

复杂度。 头部和尾部的 push_front、push_back、pop_front、pop_back 是摊还常数时间（“摊还”指偶尔一次重新分配比较贵，把开销平摊到很多次操作上，平均仍是常数）；按下标访问 d[i] 是常数时间；中间 insert、erase 是 O(n)。

选读：为什么 queue 默认用 deque 当底座。 容器适配器 queue 的默认底层容器就是 deque，因为它需要“一头进、一头出”，正好用上 deque 两端高效的特点。这里只当作背景了解，不影响使用。

选读：搜索类算法的应用。 如果已经学过图的广度优先搜索，会发现“每次从头部取出一个点、把新发现的点加到尾部”正好是 deque 的两端操作（实际写代码时通常直接用 queue 队列）。本课目前没有图遍历的专页，图论知识不是理解本页的前提；想先看看“探索 + 标记 + 撤销”的写法，可以读 递归的应用：枚举，其余内容等学到时再补。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

deque<int> d = {1, 2};
d.push_front(0);
d.push_back(3);
d.pop_front();
d.push_front(9);

cout << d.front() << ' ' << d.back() << ' ' << d.size() << '\n';

第 2 题：修改代码

下面这段片段模拟“两端都能进出的通道”：请把 5 加入头部，让输出变成 5 1 2 3，长度 4：

deque<int> d = {1, 2, 3};
// 在这里补一行：把 5 加到头部
for (int i = 0; i < (int)d.size(); i++) cout << d[i] << ' ';

验证条件：先说出补完之后 front()、back()、size() 分别是多少，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> d = {1, 2};
    d.push_front(0);
    d.push_back(3);
    d.pop_front();
    d.push_front(9);

    cout << d.front() << ' ' << d.back() << ' ' << d.size() << '\n';
    return 0;
}

9 3 4

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> d = {1, 2, 3};
    d.push_front(5);                     // 加到头部

    cout << "size = " << d.size()
         << ", front = " << d.front() << ", back = " << d.back() << '\n';
    for (int i = 0; i < (int)d.size(); i++) cout << d[i] << ' ';
    cout << '\n';
    return 0;
}

size = 4, front = 5, back = 3
5 1 2 3 

立即练习

做完后请说明：这道题为什么用 deque 比用 vector 更合适？如果所有操作都只发生在尾部，两者还有区别吗？