# 栈

> 计算机科学 · CIE A-Level 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u10-stacks/

本模块讲解栈这一抽象数据类型的结构、性质和操作。你将学习栈的常见实现和实际应用，包括CIE 9618考试要求的表达式处理。

**先修:** [数组](https://www.owlsprep.com/zh/study/cie-9618-u10-arrays/); [链表](https://www.owlsprep.com/zh/study/cie-9618-u10-linked-lists/); [抽象数据类型](https://www.owlsprep.com/zh/study/cie-9618-u10-abstract-data-types/)

## 学习目标

- 描述栈数据结构的结构和核心性质
- 实现基于数组和链表的栈的入栈、出栈和查看栈顶操作
- 识别并处理栈溢出和栈下溢错误
- 将栈应用到包括后缀表达式求值在内的常见问题

## 栈的结构与核心性质

**栈** — 一种线性抽象数据类型（ADT），所有插入（入栈）和删除（出栈）操作都在同一端执行，该端称为*栈顶*。另一端固定称为栈底。

*例:* 现实中的类比就是一叠盘子：你只能添加或拿走最顶部的盘子

栈的核心规则是**后进先出（LIFO）**顺序，即最后加入栈的元素永远是第一个可以被移除的元素。这个性质让栈非常适合需要反转顺序或撤销最近操作的任务。

> **mnemonic**
>
> LIFO = 后进先出：你最后放进去的元素第一个拿出来，就像餐厅里的一叠盘子一样。

**例题:** 栈初始为空，展示每次操作后栈的状态：`push(5)`，`push(12)`，`pop()`，`push(7)`，`peek()`

1. 1. `push(5)`后：栈有1个元素，栈顶 = 5，栈：`[5 (栈顶/栈底)]`
2. 2. `push(12)`后：新元素添加到栈顶，栈：`[5 (栈底), 12 (栈顶)]`
3. 3. `pop()`后：栈顶元素12被移除，栈回到`[5 (栈顶/栈底)]`
4. 4. `push(7)`后：新栈顶是7，栈：`[5 (栈底), 7 (栈顶)]`
5. 5. `peek()`返回7，栈保持不变。

## 栈的实现

栈可以通过两种常见方式实现：固定大小数组或动态链表。两种实现在性能、内存使用和错误条件上各有取舍。

**方法对比**

两种实现方式的核心区别：

- **基于数组的栈** — 使用连续数组存储栈元素，用整数`top`指针记录当前栈顶的索引。初始化时定义固定的最大容量。
  - 优点: 所有操作时间复杂度均为常数O(1); 内存开销低
  - 缺点: 栈超过容量时存在溢出风险; 小栈可能会浪费内存

- **基于链表的栈** — 每个节点存储一个栈元素和一个指向当前栈顶下方下一节点的指针。`top`指针指向链表的第一个节点。
  - 优点: 动态大小，按需扩容缩容; 无固定容量限制
  - 缺点: 节点指针带来更高的内存开销; 访问速度略慢于数组

**例题:** 为固定大小基于数组的栈编写入栈操作的伪代码，包含错误处理。

1. 1. 首先定义栈结构：大小为`maxSize`的数组`stack`，`top`初始化为-1（表示空栈）。
2. 2. 添加新元素前先检查栈是否已满：
3. $$top = maxSize - 1$$
4. 3. 如果栈已满，输出溢出错误并退出。如果未满，递增栈顶指针，然后将新值赋值给数组中新栈顶的索引位置。
5. 4. 最终伪代码：
```
PROCEDURE push(value)
  IF top = maxSize - 1 THEN
    PRINT "Overflow Error"
  ELSE
    top = top + 1
    stack[top] = value
  ENDIF
ENDPROCEDURE
```

## 栈的常见应用

栈的LIFO性质使其适用于许多计算机科学核心任务，包括：

- 函数调用栈：存储嵌套函数调用的返回地址、局部变量和参数
- 回溯：探索路径时撤销最近操作（例如迷宫求解、解谜游戏）
- 表达式求值与转换：处理中缀、前缀和后缀数学表达式
- 撤销功能：存储编辑记录，供用户在文本编辑器中按下撤销时回退

**例题:** 使用栈计算后缀表达式`3 4 + 2 *`的值，展示每一步后的栈状态。

1. 1. 初始化空栈，从左到右依次处理每个标记。
2. 2. 标记 = 3：入栈3 → 栈：[3]
3. 3. 标记 = 4：入栈4 → 栈：[3, 4]
4. 4. 标记 = +：弹出两个值，计算结果后入栈结果。弹出4，弹出3，3 + 4 = 7 → 栈：[7]
5. 5. 标记 = 2：入栈2 → 栈：[7, 2]
6. 6. 标记 = *：弹出2，弹出7，7 * 2 = 14 → 栈：[14]
7. 7. 表达式处理完毕：结果为栈顶值 = 14

## 考试要求

**考试命令词**

CIE 9618中栈相关问题的常见指令术语有以下特定要求：

- **Describe** — 解释结构和性质，必须提到LIFO顺序 *(描述为什么栈适合用于函数调用)*

- **Implement** — 编写操作的伪代码，包含溢出/下溢的错误处理 *(实现基于链表的栈的出栈操作)*

- **Evaluate** — 展示每一步后的栈状态以得到最终结果 *(计算后缀表达式 5 3 - 2 * 的值)*

**概念自测**

测试你对栈核心概念的理解：

1. 栈遵循哪种顺序？

   - 先进先出
   - 后进先出
   - 随机访问
   - 有序

   *答案:* 后进先出

   *解析:* 正确！FIFO是队列的顺序，不是栈的。

2. 对空栈执行出栈操作会发生什么错误？

   - 溢出
   - 下溢
   - 空指针
   - 索引越界

   *答案:* 下溢

   *解析:* 正确！向满栈入栈发生溢出，对空栈出栈发生下溢。

## 常见错误

- **错误做法:** 计算后缀表达式时弹出操作数的顺序错误
  - 原因: 考生经常先弹出第一个操作数，导致减法和除法的结果错误
  - 正确做法: 始终先弹出第二个操作数，再弹出第一个操作数：`result = firstOperand op secondOperand`
- **错误做法:** 将基于数组的空栈的栈顶指针初始化为0
  - 原因: 这会导致第一个数组槽位被浪费，并且溢出检查出错
  - 正确做法: 空栈初始化`top = -1`，检查溢出后再递增指针
- **错误做法:** 认为基于链表的栈永远不会耗尽内存
  - 原因: 尽管链表没有固定容量，但如果系统内存耗尽仍然会失败
  - 正确做法: 说明链表栈是动态大小，可避免固定容量溢出，但仍然可能耗尽内存
- **错误做法:** 在栈底添加或删除元素
  - 原因: 考生经常混淆栈和队列，修改结构错误的一端
  - 正确做法: 所有插入和删除操作只能在栈顶进行
- **错误做法:** 在实现题中忘记处理溢出/下溢
  - 原因: 考官要求对边界情况进行错误检查，这一点经常被遗漏
  - 正确做法: 入栈操作始终包含溢出检查，出栈操作始终包含下溢检查

## 速查表

| 性质 | 基于数组的栈 | 基于链表的栈 |
| --- | --- | --- |
| 顺序 | LIFO | LIFO |
| 入栈/出栈时间 | O(1) | O(1) |
| 容量 | 固定最大值 | 动态 |
| 溢出风险 | 是（固定大小） | 仅当无可用内存时 |
| 内存开销 | 低 | 高（每个节点需要指针） |
| 常见错误 | 栈顶初始化错误、溢出 | 下溢、丢失栈顶指针 |

## 下一步

栈是最基础的抽象数据类型之一，你会在从递归到操作系统内存管理等高级主题中反复遇到它。掌握栈的性质和操作对于回答CIE 9618的理论和编程题都至关重要。接下来，你将学习队列——另一种遵循不同FIFO顺序的线性数据结构，之后再进入树和图等更复杂的非线性结构。栈也是递归的基础，因此扎实的理解会让学习该主题轻松很多。

- [队列](https://www.owlsprep.com/zh/study/cie-9618-u10-queues/)
- [链表](https://www.owlsprep.com/zh/study/cie-9618-u10-linked-lists/)
- [树](https://www.owlsprep.com/zh/study/cie-9618-u10-trees/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u10-stacks/