掌握栈的后进先出特性、基本操作及顺序栈、共享栈和链式栈的实现，明确栈空、栈满与各操作的复杂度边界。
# 一、栈的定义与基本操作
栈（Stack）是只允许在一端进行插入和删除的线性表。允许操作的一端称为栈顶，另一端称为栈底。插入称为进栈或压栈，删除称为出栈或弹栈。
栈遵循后进先出（LIFO, Last In First Out）原则：最后进栈的元素最先出栈。若依次将 a,b,c 压栈，在此期间不出栈，则出栈次序必为 c,b,a。
1
2
3
4
| flowchart BT
B[栈底：a] --> M[元素：b] --> T[栈顶：c]
P[push d] --> T
T --> O[pop 返回 c]
|
栈的抽象操作包括：
| 操作 | 含义 | 失败条件 |
|---|
| InitStack | 初始化为空栈 | 无 |
| StackEmpty | 判断是否为空 | 无 |
| Push(S, x) | 将 x 压入栈顶 | 顺序栈可能栈满；链栈可能内存分配失败 |
| Pop(S, x) | 删除栈顶并用 x 返回其值 | 栈空 |
| GetTop(S, x) | 读取栈顶但不删除 | 栈空 |
| DestroyStack | 释放栈占用资源 | 无 |
只要栈顶位置已知，Push、Pop、GetTop 均为 O(1)；栈不支持按逻辑位置随机访问。
# 二、顺序栈
# 1. 栈顶指针的约定
顺序栈使用连续存储空间。以下约定 top 保存栈顶元素的下标：
- 空栈：top == -1；
- 首元素压入后：top == 0；
- 栈满：top == MAX_SIZE - 1；
- 栈长：top + 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <stdbool.h>
#define MAX_SIZE 100
typedef int ElemType;
typedef struct {
ElemType data[MAX_SIZE];
int top;
} SqStack;
void InitStack(SqStack *S) {
S->top = -1;
}
bool StackEmpty(const SqStack *S) {
return S->top == -1;
}
|
在这种约定下，进栈应先判断满，再递增 top；出栈应先判断空，再读取并递减 top。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| bool Push(SqStack *S, ElemType x) {
if (S->top == MAX_SIZE - 1) {
return false;
}
S->data[++S->top] = x;
return true;
}
bool Pop(SqStack *S, ElemType *x) {
if (S->top == -1) {
return false;
}
*x = S->data[S->top--];
return true;
}
bool GetTop(const SqStack *S, ElemType *x) {
if (S->top == -1) {
return false;
}
*x = S->data[S->top];
return true;
}
|
另一种合法约定是 top 指向 “下一个可写位置”，此时空栈为 top == 0、栈顶为 data [top - 1]。两种定义都可行，但判空、判满和数组下标必须成套使用，不能混搭。
# 2. 共享栈
两个顺序栈若各自预留一半数组空间，可能一边满、另一边空，造成浪费。共享栈让两个栈从数组两端向中间生长：
- 栈 1 初始 top1 == -1，向下标增大方向增长；
- 栈 2 初始 top2 == MAX_SIZE，向下标减小方向增长；
- 当 top1 + 1 == top2 时，整个数组才真正满。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| typedef struct {
ElemType data[MAX_SIZE];
int top1;
int top2;
} ShareStack;
void InitShareStack(ShareStack *S) {
S->top1 = -1;
S->top2 = MAX_SIZE;
}
bool Push1(ShareStack *S, ElemType x) {
if (S->top1 + 1 == S->top2) {
return false;
}
S->data[++S->top1] = x;
return true;
}
bool Push2(ShareStack *S, ElemType x) {
if (S->top1 + 1 == S->top2) {
return false;
}
S->data[--S->top2] = x;
return true;
}
|
共享栈适用于两个栈的容量需求难以预估、但总容量受固定数组限制的场景。
# 三、链式栈
链式栈通常以不带头结点的单链表实现，并让链表头部充当栈顶。这样新增或删除首结点均为 O(1)，不必遍历链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <stdbool.h>
#include <stdlib.h>
typedef struct StackNode {
ElemType data;
struct StackNode *next;
} StackNode, *LinkStack;
void InitLinkStack(LinkStack *S) {
*S = NULL;
}
bool LinkStackEmpty(LinkStack S) {
return S == NULL;
}
bool LinkPush(LinkStack *S, ElemType x) {
StackNode *node = malloc(sizeof(StackNode));
if (node == NULL) {
return false;
}
node->data = x;
node->next = *S;
*S = node;
return true;
}
bool LinkPop(LinkStack *S, ElemType *x) {
if (*S == NULL) {
return false;
}
StackNode *node = *S;
*x = node->data;
*S = node->next;
free(node);
return true;
}
|
链式栈没有固定数组容量造成的 “栈满”，但并非无限大：动态内存耗尽时仍会申请失败；每个结点还额外保存一个指针，空间局部性通常弱于顺序栈。
# 四、顺序栈与链式栈的比较
| 维度 | 顺序栈 | 链式栈 |
|---|
| 栈顶操作 | O(1) | O(1) |
| 容量 | 静态数组时固定；动态数组可扩容 | 随动态内存变化 |
| 栈满条件 | 数组空间用尽 | 内存申请失败 |
| 单元素额外开销 | 无指针域 | 需要指针域 |
| 缓存局部性 | 通常较好 | 通常较差 |
| 实现重点 | top 的边界与约定 | 分配、断链与释放 |
例题 3.1：栈顶指针的状态判断
顺序栈容量为 5，采用 top 指向栈顶元素、空栈 top == -1 的约定。依次执行 Push (1)、Push (2)、Pop、Push (3) 后，top 的值是多少？栈中元素从栈底到栈顶依次为何？
【解】 初始 top == -1。Push (1) 后为 0；Push (2) 后为 1；Pop 后为 0；Push (3) 后为 1。因此栈内从底到顶为 1,3，top == 1。
# 五、考场检查清单
- 栈只有栈顶一端可操作，LIFO 不能写成 FIFO。
- 写顺序栈代码前先写清 top 的含义和空、满条件。
- 进栈和出栈都应先检查边界，避免数组越界或空栈读取。
- 共享栈的满条件是两个栈顶相邻，不是某个栈单独到数组中点。
- 链式栈将链表头设为栈顶，才能使压栈和出栈均为 O(1)。
