考研笔记

出栈序列：合法性判定与卡特兰数计数

这是第 3 章唯一一块值得展开讲的内容。 教材正文只用两行给出卡特兰数公式，却在本节习题里配了 19 道出栈序列题，其中 6 道是统考真题（2009、2010、2011、2013、2020、2022），另有 2 道在 3.3 节（2016、2017）。王道在 3.1.1 一口气挂了三条命题追踪——「栈的特点（2017）」「入栈序列和出栈序列之间的关系（2022）」「特定条件下的出栈序列分析（2010、2011、2013、2018、2020）」。

整块内容其实只有三个问题：给定一个序列，它合法吗（判定）；一共有多少个（计数）；要多大的栈才装得下（深度）。判定和深度是手工模拟，计数才是卡特兰数。真题里计数只考过带条件的小规模穷举，从没有直接让你代公式算 ——公式的真正用处是给穷举提供一个「一共几个」的校验值。

机制

3.1.1 栈的定义与基本操作

栈（Stack）是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

术语定义
栈顶（Top）线性表允许进行插入和删除操作的那一端
栈底（Bottom）固定的、不允许进行插入和删除操作的另一端
空栈不含任何元素的空表

设栈 ，则 为栈底元素、 为栈顶元素。入栈次序依次为 ，而出栈次序为 ——栈的操作特性概括为后进先出（Last In First Out，LIFO）。

教材以严蔚敏编写的教材为准给出基本操作，解答算法题时若题干未做限制，可直接使用这些函数：

操作语义
InitStack(&S)初始化一个空栈 S
StackEmpty(S)判断一个栈是否为空，若 S 为空则返回 true，否则返回 false
Push(&S,x)入栈，若栈 S 未满，则将 x 加入使之成为新栈顶
Pop(&S,&x)出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回
GetTop(S,&x)读栈顶元素，但不出栈，若栈 S 非空，则用 x 返回栈顶元素
DestroyStack(&S)销毁栈，并释放栈 S 占用的存储空间

顺序栈与链栈的判空判满、两种 top 约定、共享栈的栈满条件收在 速查：栈与队列的判空判满，此处不重复。

合法出栈序列的判定准则

判定的全部依据只有一条，王道把它写在第 14 题的解析里：

对于某个出栈的元素，在它之前入栈却晚出栈的元素必定是按逆序出栈的。

这条准则有一个更好用的等价形式，也是第 19 题【另解】给出的：

若某个元素 已经出栈，则 前面尚未出栈的元素一定逆置有序地出栈。

据此可以在 内否掉大多数选项，不必真的去模拟：

  • 入栈 ，出栈以 开头 出栈序列只能是 （ 是最后入栈的，它先出意味着 全在栈中）。
  • 入栈 ，问 是否合法：第一个出栈元素是 ，则 必停留在栈中，它们出栈的相对顺序只能是 ；而给定序列里 在 前面，所以 错误。

还有一条更快的切入口，王道在第 22 题【另解】里点名：

解答此类题时，一定要注意出栈序列中的「最后一个入栈元素」。 它一旦出栈，栈里剩下的元素就被完全锁死成逆序，后面的自由度全部消失。

判定操作序列（由 I 表示入栈、O 表示出栈）是否合法，则是另一条准则——这是综合应用题第 3 题的考法：

  • 过程中：任意前缀里 入栈次数 出栈次数（即 O 的个数不能多于 I 的个数）；
  • 结束时：入栈次数 出栈次数，栈一定为空。

【另解】把 I 记作 、O 记作 ，则合法 任意前缀子序列的累加和不小于 ，且总和为 。这正是下面折线模型的由来。

卡特兰数：出栈序列的总数

教材原文：当 个不同元素入栈时，出栈元素不同排列的个数为这个公式称为卡特兰数（Catalan）公式，可采用数学归纳法证明。

1234567
1251442132429

时 ，即 ——唯独 不可能（ 先出意味着 在栈中，只能逆序出， 不可能早于 ）。

考场上真正要记的是 和 这两个值。相邻两项的递推 比阶乘好算： 是 ， 是 。

折线模型与反射法： 是从哪来的

把一个出入栈操作序列画成折线：入栈向上走一格，出栈向下走一格，纵坐标就是栈内元素个数。于是

  • 一共 步，其中 步向上、 步向下，不加限制的折线共 条；
  • 合法 折线自始至终不跌破 （出栈次数不超过入栈次数）。

非法折线一定会碰到 。把它第一次碰到 之后的部分整体关于 翻折，终点就从 变成 ；反过来，任何终点为 的折线都必然穿过 ，翻折回去就得到一条非法折线。两者一一对应，而终点为 的折线有 条，于是这段推导不是考点，但它解释了两件考点上的事：折线模型本身就是综合应用题第 3 题的「另解」，而「 是一个减法的结果」能让人记住这个系数不是拍脑袋来的。

带条件计数：穷举才是正确姿势

王道对这类题的定性很明确：

考题中给出的 值不会很大……在一些考题中可能会问符合某个特定条件的出栈序列有多少种，比如问以 开头的出栈序列有几种，这种类型的题目一般都使用穷举法。

穷举不是瞎试，先用判定准则把栈的状态锁死，再数剩下的自由度。以 2011 真题为例（ 入栈，问以 开头的序列个数）：

首先出栈 此刻 自底向上停在栈中， 还没入栈。 的相对出栈顺序已经被锁死，唯一的自由度是 插在哪个位置：

4 个空位 4 个序列：、、、。「锁死 + 数空位」是这类题的通法，比逐个模拟快得多。

同样的方法处理 、以 开头的情形： 先出时 在栈中， 紧接着出栈意味着 入栈后立即出栈，此后只剩 逆序出栈——没有任何自由度，答案是 1 个（）。

栈的深度与容量

所谓栈的深度，是指栈中的元素个数，通常是给出入栈和出栈序列，求最大深度；栈的容量应大于或等于最大深度。

王道给了一个不用画表的算法（2009 真题【另解】）：

初始所需容量为 0，每做一次 Push 操作容量加 1，每做一次 Pop 操作容量减 1，记录容量的最大值。

即折线模型里的最高点。2009 真题中元素经栈 S 再入队列 Q，队列不改变顺序，所以出队序列 就是出栈序列，还原出的操作序列是 Push(a) Push(b) Pop Push(c) Push(d) Pop Pop Push(e) Push(f) Pop Pop Pop Push(g) Pop，折线最高点为 3，栈 S 的容量至少是 3。

王道提醒：有时会间接给出入栈和出栈序列，例如以中缀表达式和后缀表达式的形式给出——那是 3.3 栈和队列的应用 里 2012、2014 两道真题的考法。

手算模板

判定一个出栈序列是否合法（，不用画栈）

  1. 找出序列中最后一个入栈的元素在哪个位置；它之前尚未出栈的元素此后必须严格逆序出现。
  2. 从左到右扫描，每遇到一个元素 ，检查所有比 晚入栈且还没出栈的元素——它们都不可能排在 之后按入栈序出现。
  3. 只要发现某两个「同时在栈中」的元素按入栈顺序（而非逆序）出栈，立刻判非法。

数「符合某条件的出栈序列有几个」

  1. 用条件把某一时刻的栈内容确定下来（哪些元素在栈里、自底向上是什么）。
  2. 栈内元素的出栈相对顺序已被锁死，只数还没入栈的元素有几个插入位置。
  3. 用 （、、）反查总数，确认没有数漏。

求栈的最大深度

  1. 把出入栈过程还原成 I/O 串（已知入栈序和出栈序时是唯一的）。
  2. I 记 、O 记 ，逐位累加，记录最大值——那就是所需容量。

边界

错题复盘：栈顶指针的定义不唯一，做题时必须先读约定

王道 3.1.5 在第 25 题后专门加了注意框：「栈顶、队头与队尾的指针的定义是不唯一的，做题时务必仔细审题和思考。」 第 4 题（top=-1，下标 ）答案是 a[++top]=x；第 5 题（top=1，下标 ，top 指向栈顶元素的下一个位置）答案是 data[top++]=x； 第 6 题（top=n+1，栈向低地址方向增长）答案是 data[--top]=x。三题的答案两两不同，差别全在题干的一句约定上。

错题复盘：确定了入栈次序并不能确定出栈次序

王道 3.3.6 第 17 题（2017 统考真题）：下列关于栈的叙述中，错误的是（　）。答案 C（仅 I、III、IV 错）。

  • III「只要确定了入栈次序，即可确定出栈次序」错——入栈序列 ，Push,Push,Pop,Pop 得 ；Push,Pop,Push,Pop 得 。
  • I「采用非递归方式重写递归程序时必须使用栈」错——斐波那契数列的迭代实现只需要一个循环。
  • IV「栈允许在其两端进行操作」错——栈只允许在栈顶一端操作；允许两端操作的是双端队列。
  • II「函数调用时，系统要用栈保存必要的信息」正确。

错题复盘：入栈序列与出栈序列可以互为倒序，也可以完全相同

王道 3.1.4 第 31 题（2022 统考真题）：in 和 out 均为符号集 S 中所有元素的任意排列，对于初始为空的栈 ST，下列叙述正确的是（　）。答案 D。

  • D 正确：若所有元素都入栈后才依次出栈，则 in 与 out 互为倒序。
  • C「in 与 out 一定不同」错：若每个元素入栈后立即出栈，则两者完全相同——这两个极端情形正是折线模型的两条边界折线（一路上到 再一路下来 / 一直贴着 锯齿形）。
  • A、B 都错：通过模拟出入栈操作即可判定，已知 in 能判断 out 是否可能，已知 out 也能判断 in 是否可能。

错题复盘： 个元素的出栈序列共有 个， 时是 5 而不是 6

王道 3.1.4 第 13 题：3 个不同元素依次入栈，能得到（　）种不同的出栈序列。答案 B（5）。 全排列有 个，唯独 不可能—— 最先出栈说明 都还在栈中，而 先于 入栈，必须晚于 出栈。 同理第 14 题（ 入栈）答案 D（ 不可能），理由一模一样： 先出，栈内 只能出成 。

错题复盘：以 开头的出栈序列只有 1 个

王道 3.1.4 第 15 题：4 个元素依次入栈 ，以 开头的出栈序列个数是（　）。答案 A（1）。 出栈序列形如 操作序列被完全锁死： 入、 入、 入、 出、 入、 出，此后只能 出、 出，出栈序列只有 。 对照综合应用题第 1 题（5 个元素 ，以 开头）： 出栈后 在栈中、 未入栈， 有 3 个插入位置，得 、、 三个。 两题的差别只在于「还有没有元素没入栈」—— 时 已经用掉了，自由度归零。

错题复盘： 不可能是

王道 3.1.4 第 22 题：入栈序列 ，出栈序列为 ，则 不可能是（　）。答案 C（4,3）。 说明 第二个出栈，此时 都已入过栈，栈中还剩两个且按入栈顺序有序，只能是 、、： 若是 ，则 已在 出栈，不可能再在 出栈；若是 或 ，则 是栈顶，一定是下一个出栈元素，即 。 【另解】 是最后一个入栈元素 ，则只有 或 有可能是 ， 绝不可能是 。

错题复盘：输出第一个元素是 则全逆序；是 则后续不确定

王道 3.1.4 第 17、18 题。第 17 题（第一个输出是 ）答案 D（）：第 个元素第一个出栈说明前 个都已按序入栈，输出序列一定是输入序列的逆序。 第 18 题（第一个输出是 ）答案 D（不确定）： 之前的元素可以依次排在 之后出栈，但剩余的元素可以在此时入栈并排在它们之前出栈，所以第 个输出元素不确定。 区别就在于 是最后一个元素、后面没有新元素可入栈了；而 时还有 这些自由元素。

错题复盘： 时 不可能是 2； 时 可能是 2

王道 3.1.4 第 20、21 题，两题题面几乎一样，答案不同。入栈序列 ，出栈序列固定为 。 第 20 题 答案 C（不可能是 2）： 连续入栈后 第一个出栈，则 必在 之前出栈；第二个出栈的是 ，而此时 不是栈顶，所以 。 第 21 题 答案 A（可能是 2）： 各自入栈后立即出栈可以； 依次入栈后全部出栈、 入后即出也可以， 既可能是 1 又可能是 2。

错题复盘： 时 可取 个值

王道 3.1.4 第 29 题（2013 统考真题）：入栈序列 ，出栈序列 ，若 ，则 可能取值的个数是（　）。答案 C（）。 之后的 都可取（一直入栈直到该数入栈后马上出栈）。再看 和 ： 可以是 之前入栈的数（ 或 ），也可以是 ；当 时 可取 ，当 时 可取 。 因此 可取除 以外的所有数，个数为 。唯一取不到的是 自己——它已经被 用掉了。

错题复盘：不允许连续 3 次出栈 ⟹ 出栈序列里不能有长度 的连续逆序段

王道 3.1.4 第 27 题（2010 统考真题）： 依次入栈，允许入栈出栈交替进行，但不允许连续 3 次出栈，不可能得到的出栈序列是（　）。答案 D（）。 四个选项单看合法性全都成立，卡的是附加条件。【另解】给出秒杀：入栈顺序是字母表顺序，连续出栈时产生的子序列必然按字母表逆序，所以只要出栈序列里出现长度 的连续逆序子序列，就一定用了连续 3 次出栈。 中的 是长度 5 的逆序段 选 D；A 的 、B 的 、C 的 都只有长度 2。 这条对偶关系值得单独记：连续出栈段 逆序段，一旦题目限制连续出栈次数，直接去数逆序段长度。

错题复盘： _n1 不是合法的出栈序列

王道 3.1.4 第 23 题：字符序列 n1_ 作为栈的输入，输出长度为 3 且可用作 C 语言标识符的序列有（　）个。答案 C（3）。 标识符只能以英文字母或下画线开头，不能以数字开头，所以由 n、1、_ 组成的候选是 n1_、n_1、_1n、_n1 四种。前三种都能构造出操作序列，而 _n1 根据栈的操作特性不可能出现——_ 最后入栈却第一个出栈，说明 n、1 都在栈中，只能出成 1n。 这道题是「先按题意筛选，再按栈的合法性筛选」的两段式，漏掉任何一段都会错。

口径差异：卡特兰数在教材里只是一个结论，别按组合数学的深度去准备

教材口径：3.1.1 用两行给出公式并注明「可采用数学归纳法证明，有兴趣的读者可以参考组合数学教材」，此外不作任何展开。 本页的折线模型与反射法是补充，用来解释系数 和综合应用题第 3 题的【另解】，不是考纲要求。 考场上只需要：记住 、；知道带条件计数一律穷举；知道 I/O 序列合法 前缀和恒 且总和为 。

超纲但值得知道：2016 那道火车题是「最长递减子序列」

王道 3.3.6 第 16 题（2016 统考真题）： 条轨道（每条是一个队列），驶入次序 ，要求驶出次序为 ，问 至少是多少。答案 C（4）。 教材的解法是逐条构造并说明「要确保①队列中后面的元素大于前面的元素；②占用最少的队列」。 组合上的说法：每条轨道内必须是递增序列，所以问题等价于「把输入划分成最少多少个递增子序列」，由 Dilworth 定理，答案 最长递减子序列的长度。 长度为 4，故 。 考试按教材的构造法答即可，这条只是用来快速验算。

对照速查

说法判断说明
「 个元素的出栈序列有 个」❌是 ； 时 5 个不是 6 个
「」✅依次为 1, 2, 5, 14, 42, 132, 429
「确定了入栈次序就确定了出栈次序」❌2017 真题 III；同一入栈序列可有多个出栈序列
「入栈序列与出栈序列一定不同」❌2022 真题 C；每个元素入栈后立即出栈时两者相同
「入栈序列与出栈序列可能互为倒序」✅2022 真题 D；全部入栈后再依次出栈
「给了出栈序列无法反推入栈序列是否合法」❌2022 真题 B；模拟即可判定，两个方向都能判
「第一个出栈的是最后入栈的元素 ⟹ 全序列逆序」✅第 17 题；此时前 个已全部按序入栈
「第一个出栈的是第 个元素 ⟹ 后续顺序确定」❌第 18 题； 仍可随时入栈插队
「同时在栈中的元素只能逆序出栈」✅全章判定题的唯一依据
「I/O 序列合法只要 I 和 O 的总数相等」❌还需每个前缀里 O 的个数不超过 I 的个数
「栈的容量必须等于元素个数」❌只需 最大深度（折线最高点），2009 真题中 7 个元素只要容量 3
「栈顶指针一定指向栈顶元素」⚠️定义不唯一，王道注意框明确提醒审题（第 4/5/6 题答案各不相同）

考点

年份考法落点
2009元素出栈后立即入队，由出队序列求栈的最小容量折线最高点 = 3
2010附加「不允许连续 3 次出栈」，找不可能的出栈序列逆序段长度
2011求以 开头的出栈序列个数锁死 + 数空位 = 4
2013 时 的可能取值个数（取不到 3）
2017关于栈的四条叙述判错III「入栈序定出栈序」是经典错项
2020给定 Push/Pop 操作串求出栈序列逐步画栈，得
2022in 与 out 的关系（四选一）两个极端：相同 / 互为倒序

复习动作：① 把 的 5 个序列和被排除的 默写一遍；② 用「锁死 + 数空位」重做 2011 和综合应用题第 1 题；③ 用「 前缀和」重做综合应用题第 3 题的四个选项；④ 用「折线最高点」重做 2009。

链接

反向链接