跳转至

408 高频考点精讲:入栈出栈序列(Stack Push and Pop Sequences / Permutations)

模块归属:数据结构 · 栈、队列及数组
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:4 次(2016~2025 年:2017#2、2018#2、2020#2、2022#2)
  • 历年总考查频次:9 次(含 2009#2、2010#1、2011#2、2013#2、2015#2)
  • 出题形式:单项选择题(分值 2 分),常置于数据结构选择题前列(第 1 题或第 2 题)
  • 命题特点:
  • 考频极高,属于线性结构模块的常考必得分点。
  • 题型覆盖:合法出栈序列判定、卡特兰数(Catalan)计数推导、离散操作序列跟踪、栈与队列复合结构输出序列分析、栈的代数及运行机制辨析。
  • 考查形式兼具纯理论数学推导(反射原理与计数)和工程算法判定(状态机模拟与禁形子模式检验)。
近十年考查年份分布:
2016   2017   2018   2019   2020   2021   2022   2023   2024   2025
 -      √      √      -      √      -      √      -      -      -
       (#2)   (#2)          (#2)          (#2)

二、 具体考察内容

1. 栈的抽象代数性质与操作机理

  • 核心定义:栈(Stack)是受限线性表,仅允许在表的一端进行插入(Push / 入栈)和删除(Pop / 出栈)操作。进行操作的一端称为栈顶(Top),固定闭合的一端称为栈底(Base)。
  • 操作特性:后进先出(LIFO, Last In First Out)。处于栈顶的元素具有最高的弹出优先级,越早压入栈底的元素必须等待位于其上方的所有元素完全弹出后方可出栈。
  • 基本操作约束:
  • 空栈执行出栈操作将引发下溢(Underflow);
  • 连续入栈出栈过程中,出栈操作的总次数在任意中间离散时刻 \(t\) 均不得超过截至该时刻的累计入栈操作总次数。

2. 出栈序列计数问题与卡特兰数(Catalan Number)

(1) 问题形式化定义

设输入序列包含 \(n\)$ \text{个互不相同的元素} $\(\langle a_1, a_2, \dots, a_n \rangle\)$ \text{,按固定次序依次到达栈口。在操作过程中,允许入栈和出栈操作交替进行,求能够输出的合法出栈排列总数} $\(C_n\)。

(2) 递推关系建立(分治法)

考虑序列中第一个入栈的元素 \(a_1\)$ \text{。元素} $\(a_1\)$ \text{可以在第} $\(1\)$ \text{个出栈,也可以在第} $\(k\)$ \text{个出栈(} $\(1 \le k \le n\)): * 若 \(a_1\)$ \text{是第} $\(k\)$ \text{个出栈的元素,则在} $\(a_1\)$ \text{之前出栈的必然是比它后入栈的} $\(k-1\)$ \text{个元素} $\(\langle a_2, a_3, \dots, a_k \rangle\)$ \text{。这} $\(k-1\)$ \text{个元素在} $\(a_1\)$ \text{之上独立完成进栈出栈,其合法序列数为} $\(C_{k-1}\)。 * 在 \(a_1\)$ \text{出栈之后出栈的元素是剩余的} $\(n-k\)$ \text{个元素} $\(\langle a_{k+1}, \dots, a_n \rangle\)$ \text{,其合法序列数为} $\(C_{n-k}\)。 * 由乘法原理与加法原理,得到卡特兰数的一阶非线性递推关系式: $\(C_n = \sum_{k=1}^n C_{k-1} C_{n-k} \quad (n \ge 1), \quad C_0 = 1\)$

(3) 闭式解证明:格路模型与反射原理(Dyck Path & Reflection Principle)

将长度为 \(2n\) 的操作序列映射到直角坐标平面: * 令每一步“入栈”对应向右移动向量 \((1, 0)\); * 令每一步“出栈”对应向上移动向量 \((0, 1)\)。 * 整个过程从原点 \((0, 0)\)$ \text{出发,最终到达终点} $\((n, n)\)$ \text{,共包含} $\(n\)$ \text{步向右与} $\(n\) 步向上。 * 合法性几何条件:出栈次数不能超过入栈次数,即对于路径上的任意整点 \((x, y)\)$ \text{,必须满足} $\(y \le x\)$ \text{。整条路径绝不能穿透对角线} $\(y = x\)$ \text{,即不得触碰非法界线} $\(y = x + 1\)。

y 轴 (出栈)
 ^
 |                · (n,n)
 |             · /|
 |          · /   |
 |       · /      |
 |    · /         |   界线: y = x + 1
 | · /            |   对角线: y = x
 +-------------------> x 轴 (入栈)
(0,0)
  • 组合计数推导:
  • 无约束情况下,从 \((0, 0)\)$ \text{到} $\((n, n)\)$ \text{的单调路径总数为在} $\(2n\)$ \text{步中任选} $\(n\) 步入栈: $\(N_{\text{total}} = \binom{2n}{n}\)$
  • 非法路径必然与直线 \(y = x + 1\)$ \text{至少存在一个交点。设某条非法路径首次触碰该直线的点为} $\(P(x_0, x_0 + 1)\)。
  • 将从原点 \((0, 0)\)$ \text{到接触点} $\(P\)$ \text{的路径段沿直线} $\(y = x + 1\) 作镜像反射变换:
    • 起点 \((0, 0)\)$ \text{经反射后映射为新起点} $\((-1, 1)\);
    • 接触点 \(P\) 位于反射轴上,其坐标保持不变;
    • 从 \(P\)$ \text{到终点} $\((n, n)\) 的剩余路径段保持不变。
  • 任意一条越界的非法路径唯一对应一条从 \((-1, 1)\)$ \text{到} $\((n, n)\)$ \text{的单调路径;反之,从} $\((-1, 1)\)$ \text{到} $\((n, n)\)$ \text{的每条单调路径必穿过直线} $\(y = x + 1\)$ \text{,经过逆反射可唯一还原为一条从} $\((0, 0)\)$ \text{到} $\((n, n)\) 的非法路径。
  • 从 \((-1, 1)\)$ \text{到} $\((n, n)\) 的步数:
    • 向右步数为 \(n - (-1) = n + 1\);
    • 向上步数为 \(n - 1\);
    • 总步数为 \((n + 1) + (n - 1) = 2n\)。
    • 因此非法路径总数为: $\(N_{\text{illegal}} = \binom{2n}{n-1} = \binom{2n}{n+1}\)$
  • 综合得出合法出栈序列总数的闭式通项公式: $\(C_n = N_{\text{total}} - N_{\text{illegal}} = \binom{2n}{n} - \binom{2n}{n-1} = \frac{(2n)!}{n! n!} - \frac{(2n)!}{(n-1)! (n+1)!} = \frac{1}{n+1} \binom{2n}{n}\)$

(4) 经典取值速查

\(n\)$ \text{ 计算展开式 } $\(C_n\) 取值
1 \(\frac{1}{2} \binom{2}{1} = 1\) 1
2 \(\frac{1}{3} \binom{4}{2} = \frac{6}{3}\) 2
3 \(\frac{1}{4} \binom{6}{3} = \frac{20}{4}\) 5
4 \(\frac{1}{5} \binom{8}{4} = \frac{70}{5}\) 14
5 \(\frac{1}{6} \binom{10}{5} = \frac{252}{6}\) 42

3. 出栈序列合法性判定定理(Knuth 栈混洗定理)

(1) 定理表述与数学刻画

设入栈序列为自然升序 \(\langle 1, 2, \dots, n \rangle\)$ \text{。一个由这} $\(n\)$ \text{个元素构成的全排列} $\(P = \langle p_1, p_2, \dots, p_n \rangle\) 是合法出栈序列的充分必要条件是:该排列中不包含 312 禁形子模式(Pattern 312-avoiding Permutation)。

  • 形式化准则:不存在下标三元组 \(i < j < k\),使得: $\(p_j < p_k < p_i\)$
  • 等价实用准则:在出栈序列中,对任意元素 \(p_i\)$ \text{,其后出现的、且在原始入栈顺序中位于} $\(p_i\) 之前的全部元素,在出栈序列中出现的先后次序必须严格单调递减。

(2) 定理证明

  • 必要性: 若在出栈序列中 \(p_i\)$ \text{先于} $\(p_j, p_k\)$ \text{出栈,说明在} $\(p_i\)$ \text{出栈的瞬时时刻,元素} $\(p_j\)$ \text{与} $\(p_k\) 已经在栈内驻留,或者尚未进栈。 若已知 \(p_j < p_i\)$ \text{且} $\(p_k < p_i\)$ \text{,则} $\(p_j\)$ \text{与} $\(p_k\)$ \text{必定先于} $\(p_i\) 入栈。 因为 \(p_j < p_k\)$ \text{,所以入栈时} $\(p_j\)$ \text{先入栈,} $\(p_k\) 后入栈。 当 \(p_i\)$ \text{出栈时,} $\(p_j\)$ \text{与} $\(p_k\)$ \text{仍留在栈中,且} $\(p_k\)$ \text{位于} $\(p_j\) 之上(更靠近栈顶)。 根据 LIFO 原则,后续出栈时 \(p_k\)$ \text{必须先于} $\(p_j\)$ \text{出栈,不可能出现} $\(p_j\)$ \text{先于} $\(p_k\) 出栈的情形。故 312 模式不可能产生。
  • 充分性: 若排列不含 312 禁形模式,可通过下述基于辅助栈的贪心算法在 \(O(n)\) 时间内构造出一组完全合法的 Push/Pop 操作序列。

(3) 判定算法实现(双指针辅助栈法)

  • 算法描述:
  • 维护一个辅助栈 \(S\)$ \text{,双指针} $\(i = 0\)$ \text{(指向入栈序列} $\(I\)),\(j = 0\)$ \text{(指向候选出栈序列} $\(O\));
  • 若栈顶元素等于 \(O[j]\)$ \text{,则执行弹栈,} $\(j\) 自增 1;
  • 若栈顶不匹配,且 \(i < |I|\)$ \text{,则将} $\(I[i]\)$ \text{压入栈} $\(S\),\(i\) 自增 1;
  • 若入栈序列已用尽(\(i = |I|\)$ \text{)且栈顶元素依然不等于} $\(O[j]\),则当前序列非法,算法终止;
  • 循环执行直至匹配完毕。若最终 \(S\)$ \text{为空且} $\(j = |O|\),则判定为合法序列。

4. 极值序列及可逆性分析

  1. 完全同序序列: 每个元素执行“入栈后立即出栈”(Push \(\to\)$ \text{Pop),最终出栈序列与入栈序列完全一致,即} $\(\text{Out} = \text{In}\)。
  2. 完全逆序序列: 全部元素依次连续入栈,中途不执行出栈,全部入栈完成后连续出栈,所得出栈序列为入栈序列的完全逆序,即 \(\text{Out} = \text{In}^R\)。
  3. 判定问题的时间复杂度: 给定长度为 \(n\)$ \text{的输入排列} $\(I\)$ \text{与输出排列} $\(O\)$ \text{,判定} $\(O\)$ \text{是否为} $\(I\)$ \text{的合法出栈序列可以在} $\(O(n)\)$ \text{时间复杂度和} $\(O(n)\) 空间复杂度内精确解决。

三、 近十年真题精讲(2016~2025)


【真题 1】2022 年 408 第 2 题 · 栈序列判定的充要性与极值存在性

题目
给定有限符号集 \(S\),\(in\)$ \text{和} $\(out\)$ \text{均为} $\(S\)$ \text{中所有元素的任意排列。对于初始为空的栈} $\(ST\),下列叙述中,正确的是( )。
A. 若 \(in\)$ \text{是} $\(ST\)$ \text{的入栈序列,则不能判断} $\(out\) 是否为其可能的出栈序列
B. 若 \(out\)$ \text{是} $\(ST\)$ \text{的出栈序列,则不能判断} $\(in\) 是否为其可能的入栈序列
C. 若 \(in\)$ \text{是} $\(ST\)$ \text{的入栈序列,} $\(out\)$ \text{是对应} $\(in\)$ \text{的出栈序列,则} $\(in\)$ \text{与} $\(out\) 一定不同
D. 若 \(in\)$ \text{是} $\(ST\)$ \text{的入栈序列,则对应} $\(in\)$ \text{的出栈序列中一定包含} $\(in\) 的逆序

【解析】

  • A 项错误:根据辅助栈贪心匹配算法,任意给定入栈序列 \(in\)$ \text{和候选出栈序列} $\(out\)$ \text{,均可在} $\(O(n)\)$ \text{时间复杂度内严格判定} $\(out\) 是否为合法出栈序列。因此“不能判断”结论错误。
  • B 项错误:系统操作具有对称性。栈操作时间反转等价于将出栈序列作为输入逆向仿真入栈操作;或直接穷举/判定该组合,完全能够确切判断 \(in\) 是否为合法入栈序列。
  • C 项错误:构造反例。若对 \(in\)$ \text{中的每一个元素,均在其入栈后立即执行出栈操作,所得的} $\(out\)$ \text{序列与} $\(in\)$ \text{序列完全相同(} $\(in = out\)$ \text{)。因此} $\(in\)$ \text{和} $\(out\) 可以完全相同。
  • D 项正确:设入栈序列为 \(in = \langle s_1, s_2, \dots, s_n \rangle\)$ \text{。当操作方案为:将所有元素连续执行入栈(Push} $\(s_1\), Push \(s_2\), ..., Push \(s_n\)$ \text{),然后再连续执行出栈(Pop} $\(s_n\), ..., Pop \(s_1\)$ \text{)时,生成的出栈序列恰好为} $\(\langle s_n, \dots, s_2, s_1 \rangle\)$ \text{,即} $\(in\)$ \text{的完全逆序。由于该出栈方案必然存在,故在所有可能的合法出栈序列构成的集合中,必然包含} $\(in\) 的逆序。

正确答案:D


【真题 2】2020 年 408 第 2 题 · 离散操作序列跟踪

题目
对空栈 \(S\)$ \text{进行 Push 和 Pop 操作,入栈序列} $\(a,b,c,d,e\),经过 Push,Push,Pop,Push,Pop,Push,Push,Pop 操作后得到的出栈序列是( )。
A. \(b,a,c\)          B. \(b,a,e\)          C. \(b,c,a\)          D. \(b,c,e\)

【解析】

设立状态跟踪追踪入栈序列指针、栈内元素状态及输出序列: 1. 初始状态:入栈序列剩余 \(\langle a,b,c,d,e \rangle\)$ \text{,栈} $\(S = [\ ]\)$ \text{,输出序列} $\(O = \langle \rangle\)。 2. 第 1 步 Push:元素 \(a\)$ \text{入栈,栈内为} $\([a]\)。 3. 第 2 步 Push:元素 \(b\)$ \text{入栈,栈内为} $\([a, b]\)(\(b\) 为栈顶)。 4. 第 3 步 Pop:栈顶元素 \(b\)$ \text{出栈,输出} $\(b\)$ \text{,栈内剩余} $\([a]\)$ \text{,输出序列} $\(O = \langle b \rangle\)。 5. 第 4 步 Push:元素 \(c\)$ \text{入栈,栈内为} $\([a, c]\)(\(c\) 为栈顶)。 6. 第 5 步 Pop:栈顶元素 \(c\)$ \text{出栈,输出} $\(c\)$ \text{,栈内剩余} $\([a]\)$ \text{,输出序列} $\(O = \langle b, c \rangle\)。 7. 第 6 步 Push:元素 \(d\)$ \text{入栈,栈内为} $\([a, d]\)。 8. 第 7 步 Push:元素 \(e\)$ \text{入栈,栈内为} $\([a, d, e]\)(\(e\) 为栈顶)。 9. 第 8 步 Pop:栈顶元素 \(e\)$ \text{出栈,输出} $\(e\)$ \text{,栈内剩余} $\([a, d]\)$ \text{,输出序列} $\(O = \langle b, c, e \rangle\)。

最终输出序列严格为 \(b, c, e\)。

正确答案:D


【真题 3】2018 年 408 第 2 题 · 栈与队列复合受限系统

题目
现有队列 \(Q\)$ \text{与栈} $\(S\)$ \text{,初始时} $\(Q\)$ \text{中的元素依次是 1,2,3,4,5,6(1 在队头),} $\(S\) 为空。若仅允许下列 3 种操作:
① 出队并输出出队元素
② 出队并将出队元素入栈
③ 出栈并输出出栈元素
则不可能得到的输出序列是( )。
A. 1, 2, 5, 6, 4, 3          B. 2, 3, 4, 5, 6, 1
C. 3, 4, 5, 6, 1, 2          D. 6, 5, 4, 3, 2, 1

【解析】

  • 系统结构剖析: 队列 \(Q\)$ \text{保持严格的 FIFO 特性,元素离开队列的顺序被锁死为} $\(1 \to 2 \to 3 \to 4 \to 5 \to 6\)。 对于每个离开队列的元素,存在两种分支:
  • 直通模式(操作①):不经过栈直接输出;
  • 栈缓存模式(操作②与③):先进入栈 \(S\)$ \text{,之后再从栈} $\(S\) 弹出输出。 本质规律:未入栈的直通元素可以在任意间隙输出;但一旦元素进入栈 \(S\),后进入的元素必须比先进入的元素先弹出。

  • 选项逐步验证:

  • A 项:1, 2, 5, 6, 4, 3:
    • 1 出队并输出(操作①);2 出队并输出(操作①);
    • 3 出队并入栈(操作②,栈内 \([3]\));
    • 4 出队并入栈(操作②,栈内 \([3, 4]\));
    • 5 出队并输出(操作①);6 出队并输出(操作①);
    • 栈顶 4 出栈输出(操作③);栈顶 3 出栈输出(操作③)。合法。
  • B 项:2, 3, 4, 5, 6, 1:
    • 1 出队并入栈(操作②,栈内 \([1]\));
    • 2, 3, 4, 5, 6 依次执行操作①出队输出;
    • 栈顶 1 出栈输出(操作③)。合法。
  • C 项:3, 4, 5, 6, 1, 2:
    • 考察输出 3 之前:元素 1 和 2 必须先离开队列 \(Q\)$ \text{。由于输出序列开头为 3,说明 1 和 2 没有通过操作①直接输出,因此 1 和 2 必须已通过操作②进入栈} $\(S\)。
    • 按照出队顺序,1 先入栈,2 后入栈,栈内自底向上为 \([1, 2]\)。
    • 后续输出序列尾部若想输出 1 和 2,必须由栈 \(S\) 弹出。
    • 根据栈的 LIFO 规则,栈顶为 2,栈底为 1,弹出顺序必须为先 2 后 1(输出 2, 1)。
    • C 项给出的输出尾部次序为 1, 2,破坏了栈的后进先出约束,不可实现。
  • D 项:6, 5, 4, 3, 2, 1:
    • 1, 2, 3, 4, 5, 6 全部通过操作②依次入栈,随后通过操作③连续出栈,所得即为完全逆序。合法。

正确答案:C


【真题 4】2017 年 408 第 2 题 · 栈的运行机制综合辨析

题目
下列关于栈的叙述中,错误的是( )。
I. 采用非递归方式重写递归程序时必须使用栈
II. 函数调用时,系统要用栈保存必要信息
III. 只要确定了入栈次序,即可确定出栈次序
IV. 栈是一种受限的线性表,允许在其两端进行操作
A. 仅 I          B. 仅 I、II、III          C. 仅 I、III、IV          D. 仅 II、III、IV

【解析】

  • 命题 I 错误:并非所有递归程序改写为非递归时都必须使用栈。
  • 对于尾递归(Tail Recursion)或单向递归(如斐波那契数列、阶乘计算),程序执行状态不依赖历史调用上下文,可直接使用循环迭代结构及若干局部临时变量实现等价改写,完全无需借助辅助栈。
  • 只有在通用非尾递归(如二叉树后序遍历、汉诺塔问题、回溯搜索)中,由于需要暂存回溯点及分支状态,才必须显式使用栈结构。
  • 命题 II 正确:在现代计算机体系结构中,高级程序设计语言的函数嵌套调用机制依赖系统调用栈(Call Stack / 运行时栈帧)。栈帧用于保存函数的返回地址、实参、局部变量以及寄存器恢复上下文。
  • 命题 III 错误:入栈操作与出栈操作的时机是交替且解耦的。即使入栈元素的输入次序完全固定,由于出栈时刻的不确定性,元素进出栈可以产生多种不同的出栈序列。对于长度为 \(n\)$ \text{的固定入栈次序,产生的合法出栈次序种类数由卡特兰数} $\(C_n = \frac{1}{n+1}\binom{2n}{n}\) 决定,并非唯一确定。
  • 命题 IV 错误:栈是一种受限的线性表,但其操作受限的核心特征是仅允许在表的一端(栈顶 Top)进行插入和删除。在两端均可操作的线性表是双端队列(Deque),而非栈。

综上所述,叙述错误的为 I、III、IV。

正确答案:C


四、 核心解题套路与易错陷阱

1. 核心解题套路

套路一:出栈合法性心算法(312 禁形排除法)

在选择题中遇到形如“下列哪一个不可能是出栈序列”的题目: 1. 观察候选序列中的每一个数字 \(p_i\); 2. 扫描排在 \(p_i\)$ \text{右侧且数值比} $\(p_i\) 小的所有元素; 3. 判定准则:这些比 \(p_i\) 小的元素,在右侧出现的次序必须是严格从大到小递减排列。 4. 一旦发现右侧比 \(p_i\) 小的元素出现了“小者在前、大者在后”(即先升后降或升序乱序),立即判定该项非法。

套路二:草稿纸辅助栈仿真法(单步过桩)

对于混合模型或多步操作题目(如 2018 年、2020 年真题): 1. 严格绘制一个垂直向上开口的栈容器框; 2. 按照题设输入流,逐个压入元素; 3. 当且仅当栈顶元素与待输出元素一致时,执行划线出栈; 4. 检查是否出现“必须先弹出栈底元素,才能取出上方元素”的物理冲突。

套路三:卡特兰数首尾元素定位法

若考题要求求解“第 1 个出栈元素为 \(x\) 的出栈序列数”: * 若第 1 个出栈元素为 \(k\)$ \text{(假设入栈为} $\(1, 2, \dots, n\)): * 说明前 \(k\)$ \text{个元素已经全部入栈,并且元素} $\(k\) 进栈后立即出栈; * 此时留在栈内的元素为 \(1, 2, \dots, k-1\)$ \text{(共} $\(k-1\) 个),它们必须在后续过程中合法弹出; * 尚未入栈的元素为 \(k+1, \dots, n\)$ \text{(共} $\(n-k\) 个); * 根据子问题独立性,满足该条件的总序列数为: $\(M = C_{k-1} \times C_{n-k}\)$


2. 易错陷阱防范

  • 陷阱 1:混淆“入栈序列确定”与“出栈序列确定”
    考生易误以为输入序列固定则系统输出唯一。切记出栈时机具有任意性,只要在栈非空时均可执行出栈,出栈种类呈卡特兰数爆发。
  • 陷阱 2:非递归改写的绝对化断言
    看到“必须使用栈”时务必提高警惕。尾递归、单向递归、斐波那契数列等均可直接用 while / for 循环原地消除,无需栈开销。
  • 陷阱 3:混淆双端受限队列与栈的端点限制
    栈仅有一端可操作;若两端均允许插入删除,属于双端队列;若一端允许插入删除、另一端仅允许插入(或仅允许删除),属于输入受限(或输出受限)的双端队列。
  • 陷阱 4:复合结构中忽略前置条件的不可逆性
    在栈与队列组合问题中,直通元素不可逆流,入栈元素不可逾越栈顶。必须先推导出栈元素必须满足的入栈时机,严查逆序约束。

五、 考点速记清单

  1. 基本约束:栈是受限线性表,仅在表的一端(栈顶)执行插入与删除,遵循 LIFO。
  2. 种类计数:\(n\) 个不同元素按固定顺序入栈,合法出栈序列总数为卡特兰数: $\(C_n = \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}\)$ 常记数值:\(C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42\)。
  3. 禁形子模式:自然升序入栈时,合法出栈序列绝不能含有 312 模式。即:出栈元素之后若存在比它更早入栈的元素,这些元素必须保持单调递减出栈。
  4. 两端极值:
  5. 入栈后立即出栈 \(\implies \text{Out} = \text{In}\)(完全同序)。
  6. 全部入栈后再依次出栈 \(\implies \text{Out} = \text{In}^R\)(完全逆序,必存在于合法集)。
  7. 递归消除判据:
  8. 单向递归 / 尾递归:可用循环替代,无需栈。
  9. 通用递归(含回溯与多分枝):必须使用栈。
  10. 判定复杂度:双指针配合辅助栈,\(O(n)\) 时间即可完成任意出栈序列合法性检验。