Appearance
双端队列
松开限制，能产生的序列就变多
栈和队列的基本概念那一篇讲过一条主线：限制越多，能产生的输出序列越少。双端队列走的是反方向——它前端和后端都允许插入和删除，限制最松，所以序列集合最大。
在它和栈之间，还有两种"半松"的形式：
| 类型 | 前端 front | 后端 rear |
|---|---|---|
| 双端队列 | 可插入、可删除 | 可插入、可删除 |
| 输入受限双端队列 | 只能删除 | 可插入、可删除 |
| 输出受限双端队列 | 可插入、可删除 | 只能插入 |
🔴 受限的是"动作"，不是"端"。 输入受限 = 插入只能在一端（所以插入只能在 rear、删除两端都行）；输出受限 = 删除只能在一端（所以删除只能在 front、插入两端都行）。自检办法：受限的那种动作，在权限表里只应出现一次。
栈和队列都是它的特例：只在一端插删就是栈，一端只插、另一端只删就是队列。
先看一眼
试着从前端插入一个元素——这个"插队"动作是队列做不到的，也正是双端队列比队列强的全部来源。
输出序列判定：两条现场方法
408 关心的不是 deque 怎么实现（实现就是循环队列的两端版），而是"某个序列能不能由某种受限双端队列产生"。方法与出栈序列判定同源，仍是模拟，只是每种受限形式的可用动作集不同。
不过这两种受限形式各有一条能省力的性质：
输入受限：队内元素永远按编号递增。 因为只能从 rear 插入，元素按编号顺序进入，所以 front 端最小、rear 端最大，而还没入队的元素都比队内所有元素大。既然删除只能在两端发生，每一步能输出的就只有队内的最小值或最大值。拿这条扫一遍目标序列，找那个"既不是当时的最小、也不是当时的最大"的元素，就是失败点。
输出受限：没有这条捷径，因为可以从前端插队，队内不再有序。 但有另一个办法——倒着剥端点：把目标序列从后往前看，检查每一步"最后插入的那个元素是否位于当时的某一端"。插入只能发生在两端，所以一旦发现某个元素必须待在中间，就矛盾。
三个用来定性的序列（输入均为
| 序列 | 栈 | 输入受限 | 输出受限 |
|---|---|---|---|
| ✗ | ✓ | ✗ | |
| ✗ | ✗ | ✓ | |
| ✗ | ✓ | ✓ |
三个判别序列的逐步模拟与失败点（第一次学、或想手动走一遍时展开）
输入受限 ·
| 步 | 动作 | 队列（front→rear） | 输出 |
|---|---|---|---|
| 1 | 1、2、3、4 依次从 rear 入队 | 1 2 3 4 | — |
| 2 | 从 rear 删除 | 1 2 3 | 4 |
| 3 | 从 front 删除 | 2 3 | 1 |
| 4 | 从 rear 删除 | 2 | 3 |
| 5 | 从任一端删除 | 空 | 2 |
注意这个序列栈是产生不了的（栈弹出 4 之后栈顶是 3，取不到 1）。
输出受限 ·
| 步 | 动作 | 队列（front→rear） | 输出 |
|---|---|---|---|
| 1 | 1 从 rear 入 | 1 | — |
| 2 | 2 从 rear 入 | 1 2 | — |
| 3 | 3 从 front 入（插队） | 3 1 2 | — |
| 4 | 从 front 删 3 次 | 空 | 3, 1, 2 |
| 5 | 4 入队后删除 | 空 | 4 |
输出受限 ·
| 步 | 动作 | 队列（front→rear） | 输出 |
|---|---|---|---|
| 1 | 1 从 rear 入 | 1 | — |
| 2 | 2 从 front 入 | 2 1 | — |
| 3 | 3 从 rear 入 | 2 1 3 | — |
| 4 | 4 从 front 入 | 4 2 1 3 | — |
| 5 | 从 front 连删 4 次 | 空 | 4, 2, 1, 3 |
两个失败的例子更值得单独看，因为它们正是两条现场方法各自的用法。
输入受限产生不了 1 2 3 4；从 rear 删掉 4 之后队内剩 1 2 3。这时需要输出 2，可队内最小是 1、最大是 3，2 夹在中间，两端都够不着——递增规则一句话判死。
输出受限产生不了 4 1 3 2。倒着剥端点：4 是最后插入的、位于 front 端，合法；剥掉它剩下 1 3 2，而其中最后插入的是 3，它却位于中间——插入只能发生在两端，不可能把 3 放到中间，矛盾。
把这两条对照着看就很清楚：同一个序列
前两行说明两个集合各自有对方没有的元素，谁也不包含谁——"输入受限比输出受限强"或反过来的说法都是错的。第三行说明两者都严格强于栈（
于是四个集合的关系是：
其中中间两项之间无包含关系。三条依据分别是：栈只用"可插可删"的那一端就能被两种受限 deque 模拟出来（所以是包含），上表前两行给出了严格更大的证据（所以是真包含），而队列只能产生恒等序列
这条关系能省掉一半工作量：栈能产生的序列，两种受限 deque 一定也能产生，不必再逐个模拟。反过来则不成立。
六种基本操作与结构示意（想看清哪些操作被禁用就展开）
text
前端 front 后端 rear
↕ ↕
┌──────┬──────┬──────┬──────┬──────┐
│ a₁ │ a₂ │ a₃ │ a₄ │ a₅ │
└──────┴──────┴──────┴──────┴──────┘
可插入/删除 可插入/删除
图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图3.27 双端队列的基本操作，p127
图里六个操作两两成对：EnQueueHead / EnQueueTail 是两端插入， DeQueueHead / DeQueueTail 是两端删除，getHead / getTail 是两端读取（不改变队列）。 把其中若干个操作"禁用"，就得到本篇讨论的各种受限形式。
实现：就是循环队列的两端版
两种受限 deque 都用循环数组实现，指针移动完全沿用循环队列的取模口径：front 指向队头元素，rear 指向队尾元素的下一个位置，判空 front == rear，判满 (rear + 1) % MaxSize == front（牺牲一个单元）。所以这一节没有新东西要学，唯一的新问题是"多出来的那两个端点操作，指针该怎么动"。
两种受限 deque 的完整代码（写代码题时展开）
输入受限双端队列：只允许从 rear 插入，两端都可删除。
c
#define MaxSize 50
typedef struct {
int data[MaxSize];
int front, rear; // front 指向队头元素，rear 指向队尾元素的下一个位置
} InputRestrictedDeque;
void InitDeque(InputRestrictedDeque *dq) { dq->front = dq->rear = 0; }
// 唯一的插入方式：从 rear 端插入
bool InsertRear(InputRestrictedDeque *dq, int x) {
if ((dq->rear + 1) % MaxSize == dq->front) return false; // 队满
dq->data[dq->rear] = x; // rear 指的是空位，先写入
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 端删除：rear 要先后退一格才指到有效元素
bool DeleteRear(InputRestrictedDeque *dq, int *x) {
if (dq->front == dq->rear) return false; // 队空
dq->rear = (dq->rear - 1 + MaxSize) % MaxSize; // 先退，+MaxSize 防负数
*x = dq->data[dq->rear]; // 再取值
return true;
}输出受限双端队列：两端都能插入，只能从 front 删除。
c
typedef struct {
int data[MaxSize];
int front, rear;
} OutputRestrictedDeque;
// 从 rear 端插入
bool InsertRear2(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 端插入：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 DeleteFront2(OutputRestrictedDeque *dq, int *x) {
if (dq->front == dq->rear) return false;
*x = dq->data[dq->front];
dq->front = (dq->front + 1) % MaxSize;
return true;
}四个端点操作、判空判满全是 MaxSize - 1。
上面代码里四个端点操作的指针方向是镜像的：front 端插入让 front 减小、删除让它增大；rear 端插入让 rear 增大、删除让它减小。至于"先移指针还是先读写"，判据仍是那条贯穿本章的老规矩——指针指着有效元素就"先腾位再写"，指着空位就"先写再移"。所以 front 端插入要先退一格再写，rear 端删除要先退一格再取。
⚠️ 指针减小时的取模必须写成
(x - 1 + MaxSize) % MaxSize。rear为 0 时(0-1) % MaxSize在 C 中得到，直接当下标就越界了。
考点速记
三条会被反复调用的结论：
- 栈的序列集合真包含于两种受限双端队列各自的集合，而两种受限形式互不包含。
- 输入受限的队内元素始终递增，于是每步只能输出队内的最小值或最大值——这条把判定变成一眼可查；输出受限没有这条捷径，要倒着剥端点。
- 指针指有效元素就"先腾位"，指空位就"先写入"——这条规则贯穿顺序栈、循环队列和本篇。
这一节在真题里被考过的形式（下方「真题练习」逐题对应）：给一种受限方式，问哪个出队序列得不到。题面通常不出现"双端队列"四个字，而是用一句话描述权限，所以第一步永远是把那句话翻译成权限表：
- "允许在两端入队，仅允许在一端出队"——插入两端、删除一端，是输出受限。
- "一端仅能入队，另一端既能入队又能出队"——插入仍是两端、删除仍是一端，同样是输出受限，只是换了个说法。
- 翻译完再套方法：输出受限用倒着剥端点，输入受限用递增规则。
易错：把"输入受限"和"输出受限"认反。 记住受限的是动作：输入受限 = 插入受限，输出受限 = 删除受限。看到"两端都能入队"就该立刻判定为输出受限。
易错：以为两种受限形式有强弱之分。 它们互不包含，各有对方产生不了的序列（
与 正是这一对反例）。
易错：用栈的禁用模式去判 deque。 栈的"大、小、中"禁用模式对双端队列不成立——
栈产生不了，两种受限 deque 都能产生。
教材出处
- 队列的抽象数据类型定义（本篇 deque 的操作集是它的推广）： 严蔚敏《数据结构（C 语言版）》（第 2 版）p69「3.5.1 队列的类型定义」
- 循环队列的入队、出队与取模指针移动（本篇代码沿用其口径）：同书 p71–p72
- 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版） 图3.27 双端队列的基本操作，p127
说明：严蔚敏《数据结构（C 语言版）》（第 2 版）正文未单列双端队列一节， 本篇的定义与操作权限表以殷人昆书的双端队列操作集为依据（见上图）， 输出序列的判定与包含关系则由本篇自行推导并给出了可复核的具体序列，不附会页码。
相关知识
栈和队列的基本概念（合法出栈序列的模拟法与禁用模式，本篇判定方法由此推广）｜ 顺序栈（只用一端插删就退化为它）｜ 循环队列（本篇代码的取模写法全部来自该篇）｜ 链式队列（双端队列同样可以用双链表实现，两端插删都是