栈

计算机科学· 5 分钟阅读

1. 栈的结构与核心性质★★☆☆☆⏱ 15 min

📘 定义

栈

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

例:

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

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

📐 例题

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

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

2. 栈的实现★★★☆☆⏱ 20 min

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

方法对比

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

基于数组的栈

使用连续数组存储栈元素，用整数top指针记录当前栈顶的索引。初始化时定义固定的最大容量。

+ 优点: 所有操作时间复杂度均为常数O(1); 内存开销低

− 缺点: 栈超过容量时存在溢出风险; 小栈可能会浪费内存

基于链表的栈

每个节点存储一个栈元素和一个指向当前栈顶下方下一节点的指针。top指针指向链表的第一个节点。

+ 优点: 动态大小，按需扩容缩容; 无固定容量限制

− 缺点: 节点指针带来更高的内存开销; 访问速度略慢于数组

📐 例题

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

1
1. 首先定义栈结构：大小为maxSize的数组stack，top初始化为-1（表示空栈）。
2
1. 添加新元素前先检查栈是否已满：
3
$top = maxSize - 1$
4
1. 如果栈已满，输出溢出错误并退出。如果未满，递增栈顶指针，然后将新值赋值给数组中新栈顶的索引位置。

最终伪代码：

PROCEDURE push(value)
  IF top = maxSize - 1 THEN
    PRINT "Overflow Error"
  ELSE
    top = top + 1
    stack[top] = value
  ENDIF
ENDPROCEDURE

3. 栈的常见应用★★★☆☆⏱ 20 min

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

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

📐 例题

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

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

4. 考试要求★★☆☆☆⏱ 10 min

✓ 快速检测

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

栈遵循哪种顺序？
- 先进先出
- 后进先出
- 随机访问
- 有序
显示答案
1 —
正确！FIFO是队列的顺序，不是栈的。
对空栈执行出栈操作会发生什么错误？
- 溢出
- 下溢
- 空指针
- 索引越界
显示答案
1 —
正确！向满栈入栈发生溢出，对空栈出栈发生下溢。

5. 常见陷阱

错误做法:

计算后缀表达式时弹出操作数的顺序错误

原因:

考生经常先弹出第一个操作数，导致减法和除法的结果错误

正确做法:

始终先弹出第二个操作数，再弹出第一个操作数：result = firstOperand op secondOperand

错误做法:

将基于数组的空栈的栈顶指针初始化为0

原因:

这会导致第一个数组槽位被浪费，并且溢出检查出错

正确做法:

空栈初始化top = -1，检查溢出后再递增指针

错误做法:

认为基于链表的栈永远不会耗尽内存

原因:

尽管链表没有固定容量，但如果系统内存耗尽仍然会失败

正确做法:

说明链表栈是动态大小，可避免固定容量溢出，但仍然可能耗尽内存

错误做法:

在栈底添加或删除元素

原因:

考生经常混淆栈和队列，修改结构错误的一端

正确做法:

所有插入和删除操作只能在栈顶进行

错误做法:

在实现题中忘记处理溢出/下溢

原因:

考官要求对边界情况进行错误检查，这一点经常被遗漏

正确做法:

入栈操作始终包含溢出检查，出栈操作始终包含下溢检查

6. 速查表

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

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2022 · 12
栈的实现和核心操作
2023 · 13
使用栈进行后缀表达式求值
2024 · 11
栈实现方式对比

深入阅读

SyllabusCIE 9618 A-Level 计算机科学官方大纲页面

下一步

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

→队列
→链表
→树