Appearance
双端队列
为什么需要双端队列
栈只能在一端操作，队列只能一端入、另一端出——两者的限制都比较强。在某些场景下，我们希望两端都能灵活地插入和删除，这就产生了双端队列（Deque, Double-Ended Queue）。
双端队列是栈和队列的推广形式。408 考研中，双端队列本身的代码实现考得少，但输出序列的判断是选择题的高频考点。
核心思想
双端队列的核心特点：
- 两端均可操作：前端（front）和后端（rear）都允许插入和删除
- 栈和队列都是它的特例：若限制只从一端插入和删除，就退化为栈；若限制一端只插入、另一端只删除，就退化为队列
- 受限双端队列：对某一端的操作加以限制，可得到输入受限双端队列和输出受限双端队列
双端队列的逻辑结构：
前端 front 后端 rear
↕ ↕
┌──────┬──────┬──────┬──────┬──────┐
│ a₁ │ a₂ │ a₃ │ a₄ │ a₅ │
└──────┴──────┴──────┴──────┴──────┘
可插入/删除 可插入/删除三种双端队列的对比：
| 类型 | 前端 | 后端 |
|---|---|---|
| 双端队列 | 可插入、可删除 | 可插入、可删除 |
| 输入受限双端队列 | 只能删除 | 可插入、可删除 |
| 输出受限双端队列 | 可插入、可删除 | 只能删除 |
注意：输入受限是限制"输入"只能从一端进行，两端都能输出；输出受限是限制"输出"只能从一端进行，两端都能输入。
输入受限 vs 输出受限双端队列对比
关键区别：
- 输入受限：输入只能从一端进行，输出可以从两端进行
- 输出受限：输出只能从一端进行，输入可以从两端进行
- 两者能产生的合法输出序列都是栈的合法序列的超集
交互可视化
通过下方的交互动画，你可以逐步观察双端队列的执行过程：
操作详解
输入受限双端队列
输入受限双端队列：只允许从一端插入，但两端都可以删除。
cpp
// 输入受限双端队列——只能从 rear 端插入，front 和 rear 端都可删除
#define MaxSize 50
typedef struct {
int data[MaxSize];
int front, rear; // front 指向队头，rear 指向队尾的下一个位置
} InputRestrictedDeque;
// 从 rear 端插入（唯一的插入方式）
bool InsertRear(InputRestrictedDeque &dq, int x) {
if ((dq.rear + 1) % MaxSize == dq.front) return false; // 队满
dq.data[dq.rear] = x;
dq.rear = (dq.rear + 1) % MaxSize;
return true;
}
// 从 front 端删除
bool DeleteFront(InputRestrictedDeque &dq, int &x) {
if (dq.front == dq.rear) return false; // 队空
x = dq.data[dq.front];
dq.front = (dq.front + 1) % MaxSize;
return true;
}
// 从 rear 端删除
bool DeleteRear(InputRestrictedDeque &dq, int &x) {
if (dq.front == dq.rear) return false; // 队空
dq.rear = (dq.rear - 1 + MaxSize) % MaxSize;
x = dq.data[dq.rear];
return true;
}关键理解：输入受限 ≠ 栈也 ≠ 队列。因为删除可以在两端进行，所以它能产生的输出序列比栈和队列都多，但比一般双端队列少。
输出受限双端队列
输出受限双端队列：两端都可以插入，但只允许从一端删除。
cpp
// 输出受限双端队列——front 和 rear 端都可插入，只能从 front 端删除
typedef struct {
int data[MaxSize];
int front, rear;
} OutputRestrictedDeque;
// 从 rear 端插入
bool InsertRear(OutputRestrictedDeque &dq, int x) {
if ((dq.rear + 1) % MaxSize == dq.front) return false;
dq.data[dq.rear] = x;
dq.rear = (dq.rear + 1) % MaxSize;
return true;
}
// 从 front 端插入
bool InsertFront(OutputRestrictedDeque &dq, int x) {
if ((dq.rear + 1) % MaxSize == dq.front) return false;
dq.front = (dq.front - 1 + MaxSize) % MaxSize;
dq.data[dq.front] = x;
return true;
}
// 从 front 端删除（唯一的删除方式）
bool DeleteFront(OutputRestrictedDeque &dq, int &x) {
if (dq.front == dq.rear) return false;
x = dq.data[dq.front];
dq.front = (dq.front + 1) % MaxSize;
return true;
}关键理解：输出受限 ≠ 栈也 ≠ 队列。因为插入可以在两端进行，元素可以"插队"到前端，所以它能产生比栈更多的输出序列。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 前端插入 | O(1) | 修改 front 指针 |
| 后端插入 | O(1) | 修改 rear 指针 |
| 前端删除 | O(1) | 修改 front 指针 |
| 后端删除 | O(1) | 修改 rear 指针 |
空间复杂度：O(n)，需要存储 n 个元素。所有操作只需常数级辅助空间。
考研高频考点
- ⭐ 输出序列判断（选择题最高频）：给定输入序列 1, 2, 3, 4，判断某个输出序列能否由输入受限/输出受限双端队列产生。解题方法——逐个元素模拟，检查每次操作是否符合受限规则
- ⭐ 与栈的输出序列对比：栈合法的输出序列，输入受限和输出受限双端队列一定也合法；但反过来不成立。即：栈的合法序列 ⊂ 受限双端队列的合法序列 ⊂ 一般双端队列的合法序列
- ⭐ 概念辨析：区分输入受限和输出受限的定义（哪一端受限、受限的是插入还是删除）
- 双端队列与栈、队列的包含关系（栈和队列都是双端队列的特例）
- 判断一个序列"既不能由输入受限产生，也不能由输出受限产生"的情况（较少见但偶尔考）