栈 - Shaw 的小屋

p14（8 分钟）、p15（12.7 分钟）、p16（10.6 分钟）、p17（15.8 分钟）、p18（13.7 分钟）

栈 ADT#

三个现实里的例子：一摞餐盘、汉诺塔、只能从一侧开口的网球盒。

共同点是只能从同一端进出，这一端叫栈顶。这不只是个性质，而是硬性约束——只有栈顶能访问。

餐盘那个例子可以抬杠说能抽中间的盘子，但汉诺塔和网球盒不行：要拿一件，得先把压在上面的全移走。

一句话定义：只能从一端插入和删除的列表，那一端就是栈顶。

接口就四个：

1
push     压入一个元素
2
pop      弹出最新的那个
3
top      只看栈顶，不移除
4
isEmpty  是否为空

push/pop 是基本操作，top 和 isEmpty 通常也会有。没有 size / count 这类操作。

这四个操作全是 O(1)。

LIFO：最后压进去的最先弹出来，所以叫「后进先出」。

1
初始        空栈
2
push(2)     [2]
3
push(10)    [2, 10]
4
pop()       弹出 10  →  [2]
5
push(7)     [2, 7]
6
push(5)     [2, 7, 5]
7
top()       返回 5
8
isEmpty()   假
9
pop()       弹出 5

应用场景：

函数调用（前面链表部分讲过）
递归——本质也是一连串函数调用，只是调的都是同一个函数
编辑器撤销（Ctrl+Z）
编译器检查括号是否匹配

数组实现#

术语约定#

1
用数组 A 存栈，约定 A[0] 到 A[top] 这一段属于栈，其余是空闲
2
top 是「栈顶元素的索引」
3
空栈时 top = -1
4
数组大小由宏 MAX_SIZE 定义为 101

代码#

1
#define MAX_SIZE 101
2
int A[MAX_SIZE];
3
int top = -1;
4

5
void push(int x) {
6
    if (top == MAX_SIZE - 1) {          /* 溢出判断 */
7
        printf("Error: stack overflow\n");
8
        return;
9
    }
10
    A[++top] = x;                       /* 前置递增：先递增再赋值 */
11
}
12

13
void pop() {
14
    if (top == -1) {                    /* 空栈判断 */
15
        printf("Error: No element to pop\n");
16
        return;
17
    }
18
    top--;                              /* 本实现不返回元素，只递减 */
19
}
20

21
int Top() {
22
    return A[top];
23
}
24

25
int isEmpty() {
26
    if (top == -1) return 1;
27
    return 0;
28
}

几个要点：

A[++top] = x 用前置递增，等价于 top++; A[top] = x;
判满条件是 top == MAX_SIZE - 1（栈顶索引等于数组最高可用索引）
pop 不返回元素，只是 top--（有些语言的库会把 pop 与 top 合并，即 pop 同时移除并返回）
数组与 top 声明为全局变量，函数内可直接访问，不必传参

演示运行：push 3、5、10 → pop 一次（10 出栈）→ push 12。输出与预期吻合。

弹出后不必清空旧单元：不在栈内的单元格里是什么垃圾数据无所谓，下次 push 会覆盖。

局限与应对#

栈占满整个数组时再 push 会溢出（overflow），push 失败。两种应对：

1
① push 检查并抛错（这并非很好的行为表现）
2
② 用动态数组：溢出时新建更大数组、复制旧内容、删除小数组

复制成本 O(n)，与栈中元素数成正比。

最优扩容策略：新数组大小 = 旧数组的两倍。

摊还分析：

1
N 次 push 总耗时与 N 成正比（O(n)）
2
除以 N → 均摊每次 push 为 O(1)
3
单次 push 最坏 O(n)

「均摊 O(1)」和「单次最坏 O(n)」要一起说。

链表实现#

栈顶就是链表头部#

1
尾部：插入要遍历到最后一个节点，删除要走到倒数第二个节点  →  O(n)  ✗
2
头部：只改常数个链接                                    →  O(1)  ✓

所以：入栈 = 头部插入，出栈 = 头部删除。

栈顶指针宁愿命名为 top，而不是 head。

代码#

1
struct Node {
2
    int data;
3
    struct Node *next;
4
};
5

6
struct Node *top = NULL;        /* 初始化为 NULL */
7

8
void push(int x) {
9
    struct Node *temp = malloc(sizeof(struct Node));
10
    temp->data = x;
11
    temp->next = top;
12
    top = temp;
13
}
14

15
void pop() {
16
    if (top == NULL) {          /* 通过 top 是否为空判断栈空 */
17
        printf("Error: No element to pop\n");
18
        return;
19
    }
20
    struct Node *temp = top;
21
    top = top->next;
22
    free(temp);                 /* 必须释放 */
23
}

演示：push 2（新节点地址 100）→ push 5（新节点地址 250，top 变为 250）。

优势#

不像数组实现，不必担心溢出（除非机器自身内存耗尽）。

每个节点多用一点内存存地址，但按需分配、不用即释放，push/pop 更「优雅」。

复杂度：push / pop 均为 O(1)。

应用一：反转字符串#

用栈的做法#

1
① 从左到右把每个字符压入字符栈
2
② 再从索引 0 开始，把栈顶字符写到数组当前位置，然后 pop
3
③ 循环直到栈空

因为 LIFO，弹出顺序与压入相反，于是完成反转。

1
void reverse(char C[], int n) {
2
    stack<char> S;
3
    for (int i = 0; i < n; i++) S.push(C[i]);
4
    for (int i = 0; i < n; i++) {
5
        C[i] = S.top();
6
        S.pop();
7
    }
8
}

对象是 C 风格字符串（以 \0 结尾）；空字符只标记结尾，不属于字符串内容。

运行验证：输入 hello、my code school 均正确。

复杂度：两个循环各 O(n)，非嵌套（前后串行）→ 时间 O(n)；栈中额外空间与 n 成正比 → 空间 O(n)。

不用栈的更优解#

1
int i = 0, j = n - 1;
2
while (i < j) {
3
    swap(C[i], C[j]);
4
    i++;
5
    j--;
6
}

时间 O(n)、空间 O(1)；交换次数约为 n/2。

因为空间复杂度，双指针法优于栈法。用栈只适合输入量小、时间空间不敏感、图实现直观的场合。

应用二：反转链表#

三种解法：

1
迭代     时间 O(n)  空间 O(1)
2
递归     时间 O(n)  空间 O(n)
3
显式栈   时间 O(n)  空间 O(n)

递归用的是「隐式栈（implicit stack）」——没有显式创建栈，但仍在用栈，也就是函数调用栈。

显式栈算法#

节点地址 100 → 150 → 250 → 300。

1
① 用临时指针遍历链表，把「每个节点的指针/引用」压栈（压的是指针，不是数据）
2
② 全部压完后逐个弹出，得到的就是「逆序的节点引用」
3
③ temp = 栈顶地址；head = 该地址（此时 head = 300，temp 也指向 300）
4
④ 循环 while (!S.empty())：
5
     建立反向链接 temp->next = 栈顶地址
6
     弹出
7
     temp = temp->next（移动到下一个）
8
⑤ 循环退出后，最后一行 temp->next = NULL
9
   ——把反转后最后一个节点的链接置空

结论：用栈使反转链表更简单；仅仅按逆序打印链表元素用栈尤其容易。

应用三：检查括号匹配#

问题：给定只含 ()、{}、[] 的表达式字符串，判断括号是否平衡。括号内的内容无关紧要。这是编译器的常见任务。

平衡的定义#

1
每个开符号都有对应且顺序正确的闭符号
2
类型必须匹配（{ 必须配 }，「两者不会相互抵消」）
3
每个开括号必须在右侧找到匹配的闭括号，每个闭括号必须在左侧找到匹配的开括号
4
一个括号只有当「其后打开的所有括号都已关闭」时才能闭合

核心表述：任何闭合操作都应当针对最后那个未闭合的括号。

一个错误做法#

只统计三种符号的开/闭数量相等。反例：

1
)(       数量相等但不平衡
2
[ ( ] )  与 [ ( ) ] 数量完全相同，但前者不平衡

正确算法#

1
创建字符栈 S，从左到右扫描：
2
  若字符是 ( { [        →  push(S, c)
3
  否则若是三种闭符号之一 → 两种情况判失败：
4
                          ① 栈为空
5
                          ② 栈顶字符与该闭符号不成对
6
                          → 返回 false（不平衡，直接退出）
7
                          否则 pop(S)
8
扫描结束：栈空 → 平衡；栈不空 → 不平衡

三个用例#

1
以闭符号开头（如 `)`）：第一次进入 else 分支，栈为空 → 直接返回 false
2
`[ ( ] ...`：先压 `[`、再压 `(`，遇到 `]` 时栈顶是 `(`，本应是 `[` → false
3
`[ ( ) ]` 型：逐对配对弹出，扫描结束栈为空 → 平衡 ✓

为什么用栈#

整个过程总是在列表的同一端插入/移除，最后进到列表里的都会最先出去，这正是栈的定义；栈的插入/删除是恒定时间。

复杂度（这里没有明确给出，按流程推导）：每个字符一次 push/pop，均为 O(1) → 时间 O(n)、空间 O(n)。

栈的两种实现对比#

	数组实现	链表实现
push	O(1)	O(1)
pop	O(1)	O(1)
容量	固定，会溢出	不固定（除非内存耗尽）
扩容	需要新建 + 复制，均摊 O(1)	按需分配
内存	可能浪费	每节点多一个指针开销
栈顶	`top` 索引（初值 −1）	`top` 指针（初值 NULL）

坑#

数组实现：top 初值 −1，判空 top == -1，判满 top == MAX_SIZE - 1。
push 用 A[++top] = x（前置递增），别写成 A[top++]。
这个实现的 pop 不返回元素，只是 top--。
链表实现：入栈/出栈都在头部，在尾部做就是 O(n)；栈顶指针叫 top，不叫 head。
括号匹配不能只数数量，反例是 )( 和 [(])。