Appearance
链栈
为什么需要链栈
顺序栈使用静态数组实现，需要预先分配固定大小的存储空间。当栈的使用量难以预估时，分配过大浪费空间，分配过小则会栈满溢出。
链栈使用链表来实现栈，每次入栈动态申请一个结点，出栈时释放结点，天然不存在栈满上溢的问题。408 考研中，链栈通常作为顺序栈的对比考点出现，需要掌握其基本操作和优缺点。
核心思想
链栈的核心特点：
- 以链表头部作为栈顶：入栈和出栈都在链表头部进行，时间复杂度 O(1)
- 无需预分配空间：每个结点动态分配，不会栈满溢出（除非内存耗尽）
- 不支持随机访问：访问栈中第 i 个元素需要从栈顶依次遍历
结点结构定义：
cpp
typedef struct LinkNode {
int data; // 数据域
struct LinkNode *next; // 指针域，指向下一个结点
} LinkNode, *LinkStack;链栈的逻辑结构：
栈顶 → [a₃|next] → [a₂|next] → [a₁|NULL]栈顶指针 top 始终指向链表的第一个结点（即栈顶元素）。
交互可视化
通过下方的交互动画，你可以逐步观察链栈的执行过程：
操作详解
入栈操作
入栈即在链表头部插入（头插法）一个新结点。
关键步骤：
- 创建新结点，赋值数据域
- 新结点的
next指向当前栈顶 - 更新栈顶指针指向新结点
cpp
// 入栈（不带头结点）
bool Push(LinkStack &top, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
if (s == NULL) return false; // 内存分配失败
s->data = x;
s->next = top;
top = s;
return true;
}链栈入栈不需要判断栈满，只要内存足够就能继续入栈。
出栈操作
出栈即删除链表头结点，并取出其数据。
关键步骤：
- 判断栈是否为空（
top == NULL） - 取出栈顶元素的值
- 栈顶指针后移一位
- 释放原栈顶结点
cpp
// 出栈（不带头结点）
bool Pop(LinkStack &top, int &x) {
if (top == NULL) return false; // 栈空
LinkNode *p = top;
x = p->data;
top = p->next;
free(p);
return true;
}复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 入栈 | O(1) | 头插法，无需移动元素 |
| 出栈 | O(1) | 删除头结点，无需移动元素 |
| 读取栈顶 | O(1) | 直接访问 top 指向的结点 |
| 判空 | O(1) | 判断 top 是否为 NULL |
空间复杂度：每个元素需要额外存储一个指针域，存储密度低于顺序栈。
链栈 vs 顺序栈对比：
| 对比项 | 顺序栈 | 链栈 |
|---|---|---|
| 存储方式 | 静态数组，连续空间 | 链表，离散空间 |
| 栈满溢出 | 可能溢出 | 不会溢出（内存足够时） |
| 空间利用 | 可能浪费（预分配过大） | 按需分配，无浪费 |
| 存储密度 | 高（无指针开销） | 低（每个结点多一个指针） |
| 实现难度 | 简单 | 稍复杂 |
| 缓存性能 | 好（连续存储） | 差（离散存储） |
考研高频考点
- ⭐ 链栈的入栈和出栈操作实现（头插法/删头结点）
- ⭐ 链栈 vs 顺序栈的优缺点对比（简答题高频）
- ⭐ 链栈不存在栈满溢出问题的原因（概念题）
- 带头结点和不带头结点的链栈实现差异
- 共享栈、顺序栈、链栈的适用场景选择