3.1 栈

后进先出的线性表：顺序栈、共享栈与链栈的实现，以及出栈序列的合法性判断与卡特兰数。

栈的定义

栈的操作特性可以概括为后进先出（Last In First Out，LIFO）。生活中的例子：一摞盘子、浏览器的”后退”按钮、函数调用。

基本操作：InitStack(&S)、StackEmpty(S)、Push(&S, x)、Pop(&S, &x)、GetTop(S, &x)、DestroyStack(&S)。

顺序栈

采用顺序存储的栈称为顺序栈，用一组地址连续的存储单元存放自栈底到栈顶的元素，并附设一个指针 top 指示当前栈顶元素的位置。

1// 判断 out[] 是否为入栈序列 1..n 的合法出栈序列
2bool IsValid(int out[], int n) {
3    SqStack S; InitStack(S);
4    int next = 1;               // 下一个待入栈的元素
5    for (int k = 0; k < n; k++) {
6        while (StackEmpty(S) || GetTop(S) != out[k]) {
7            if (next > n) return false;   // 无元素可入栈
8            Push(S, next++);
9        }
10        Pop(S, x);              // 栈顶恰为 out[k]，出栈
11    }
12    return true;
13}

两种栈顶指针约定

共享栈

利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间：两个栈的栈底分别设在共享空间的两端，两个栈顶向共享空间的中间延伸。

• 0 号栈为空：top0 == -1；1 号栈为空：top1 == MaxSize。
• 栈满条件：top1 - top0 == 1（两个栈顶相邻）。
• 0 号栈进栈时 top0 先加 1 再赋值，1 号栈进栈时 top1 先减 1 再赋值。
• 共享栈能更有效地利用存储空间，存取数据的时间复杂度均为 $O(1)$。

链栈

采用链式存储的栈称为链栈。通常用单链表实现，并规定所有操作都在单链表的表头进行（表头即栈顶）。

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode, *LiStack;

链栈的优点是便于多个栈共享存储空间、提高效率，且不存在栈满上溢的情况。入栈就是头插，出栈就是删除第一个结点。

出栈序列

当元素以固定顺序进栈、而出栈可以穿插在进栈之间时，会产生不同的出栈序列。这是 408 选择题的高频题型。

快速判断法

对出栈序列中的每一个元素 x，在它之后出栈的、且比 x 先进栈的元素，必须按逆序出现（因为它们在 x 出栈时都还压在栈里，越晚进栈越在上面）。

例如进栈序列 1 2 3 4：

• 3 2 4 1 合法：3 之后比它先进栈的有 2、1，按 2 → 1 的逆序出现 ✓。
• 3 1 4 2 不合法：3 出栈时 1、2 都在栈中且 2 在 1 上面，1 不可能先于 2 出栈 ✗。

在上面的动画中选择”判断出栈序列”，输入不同的序列试一试。

有多少种出栈序列？

$n$ 个不同元素进栈，出栈元素不同排列的个数为卡特兰数（Catalan number）：

即时练习