考研笔记

双端队列与受限序列判定

这一节的题型和 3.1.1 出栈序列同源：给一个输入序列和一种受限结构，问哪个输出序列得不到。 教材【命题追踪】列了「双端队列出队/入队操作模拟」（2010、2021），两道都是输出受限的双端队列；另有 2018 一道「队列 + 栈」的组合。教材提示框原话：「实际双端队列的考题不会这么复杂，通常仅判断序列是否满足题设条件，代入验证即可。」

机制

双端队列是指允许两端都可以进行插入和删除操作的线性表。两端的地位是平等的，为了方便理解，左端也视为前端，右端也视为后端。

  • 入队时：前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在前端进的元素的后面。
  • 出队时：无论前端还是后端出队，先出的元素排列在后出的元素的前面。
受限方式定义
输出受限的双端队列允许在一端进行插入和删除，但另一端只允许插入
输入受限的双端队列允许在一端进行插入和删除，但另一端只允许删除

若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。

教材例：输入序列

结构可得到的输出序列数独有的 / 得不到的
栈14（卡特兰数 ）—
输入受限的双端队列22独有
输出受限的双端队列22独有
两者都得不到—

输入受限：设 end1 端可进可出、end2 端只能出。从 end1 输入、end1 输出相当于栈（14 种）；从 end2 输出相当于队列。两端混合输出可以再得到剩下 10 种中的 8 种。输出受限的分析类似。上表已用程序穷举复核。

手算模板

看第一个输出的元素 。 出队时，所有比它先入队的元素都还在队中，它们之后的相对出队次序已经被队内的排列锁死：

结构比 先入队的元素在队中的排列这些元素之后的出队次序必须满足
输入受限（一端入，两端出）保持入队顺序排成一列每次取的都是剩下的元素中最早或最晚入队的那个（从两端取）
输出受限（两端入，一端出）左入的在左、逆序；右入的在右、顺序。从出口端看，入队序号先减后增，最早入队的在谷底按排列从出口端依次出队，即先减后增
栈按入栈顺序叠放逆序（即 3.1.1 的判定准则）

这是必要条件： 时它恰好就是充要条件； 时通过检查的序列仍可能得不到（ 时有 6 个），需要继续往后模拟。真题的错误选项都能在这一步排除。

2010：元素 依次进入一个两端都能入队、只能一端出队的队列（输出受限），不可能得到的是 C：。 最先出队， 都在队中，之后按 出队。入队序号为 ，先增后减，不是先减后增。 其余三项： 是 左入、 左入后依次出； 中 为 ，先减后增； 中 为 ，先减后增。

2021：一端仅能入队、另一端既能入队又能出队（仍是输出受限），入队序列 ，不能得到的是 D：。 最先出队，之后 的序号先增后减，不合法。

3.2.5 第 19 题：既不能由输入受限、也不能由输出受限的双端队列得到的是 C：。 输入受限： 出队后 按序排列，下一个要出 ，但两端是 和 。输出受限： 先增后减。

其他组合结构

同一个思路适用于任何「几个容器组合」的题：先写出每个容器内部的顺序规则（栈逆序、队列顺序），再看第一个输出的元素迫使哪些元素留在哪个容器里。

题结构不能得到理由
2018队列 Q 中依次为 （1 在队头），栈 S 初始为空；只允许：① 出队并输出，② 出队并入栈，③ 出栈并输出C：首先输出 3，说明 1 和 2 已先后入栈，此后 2 一定比 1 先输出
3.2.5 第 18 题输入 ，两个队列B：5 最先输出，它所在的队列必须为空；而 1、2 已入队，1 最后输出又要求 2、3、4 都不和 1 同队，两个队列都不空，矛盾

边界

说法判断说明
「输出受限就是一端只能出队」❌是一端可进可出、另一端只能入。出口只有一个
「输入受限就是一端只能入队」❌是一端可进可出、另一端只能出。入口只有一个
「2010 和 2021 分别考输出受限和输入受限」❌两道都是输出受限：2010 两端都能入队、只有一端能出队；2021 一端只能入队、另一端可进可出
「双端队列能得到全部 种序列」❌受限的双端队列不能， 时各得到 22 种
「双端队列两端插入删除的规则不同」❌两端地位平等；受限的双端队列才有区别
「限定从某端插入的元素只能从该端删除，双端队列仍是队列」❌蜕变为两个栈底相邻接的栈

考点

  • 输入受限 / 输出受限的定义，不要按字面反过来理解。
  • 第一个输出元素的检查：输入受限从两端取、输出受限先减后增。
  • 2010、2021：输出受限；2018：队列 + 栈。
  • 考题一般只要求代入验证，不要求像教材例题那样列出全部序列。

链接

反向链接