栈
复习
- 数组与链表：两种基本的线性存储方式
- 抽象数据类型：先规定能做什么，再决定怎么做
- 函数调用与运行栈：调用信息如何被保存
TL;DR
- 栈是“后进先出”的结构
- 只在同一端插入和删除
- 它天然契合函数调用、表达式求值和撤销
- 用数组或链表都能实现
正文
数组和链表描述的是“数据怎么摆”。而栈（stack）和下一章的队列，更强调“操作按什么顺序进行”。它们都是抽象数据类型，重点在接口，而不是底层用数组还是链表。
后进先出
栈的规则只有一条，却极其有用：后进先出（LIFO，Last In First Out）。
想象一摞盘子：你只能从最上面拿，也只能往最上面放。最后放上去的那个，最先被取走。
它的核心操作通常有：
- 压栈（push）：把元素放到顶端
- 出栈（pop）：取走并移除顶端元素
- 看栈顶（top）：只看看顶端是谁，不取走
所有操作都只在同一端进行，因此实现简单，代价也都是 O(1)。用数组或链表都能实现。
为什么它无处不在
栈的价值在于：很多问题的处理顺序，天然就是“后进先出”。几个典型例子：
- 函数调用：调用一个函数，它的局部变量、返回地址要先“压”起来；函数返回时再“弹”出去。前面讲编程基础时的“运行栈”，正是这个结构
- 括号匹配：遇到左括号压栈，遇到右括号就看栈顶是不是对应的左括号
- 表达式求值：把中缀表达式转成后缀，栈是关键工具
- 撤销操作：每做一步就压栈，撤销时弹出最近一步
拿“撤销”来说，它太贴合直觉了：你最后做的那件事，理应是第一个被撤销的。顺序天然吻合，栈就成了最自然的选择。
这又回到那句老话：选数据结构，本质是选一种与问题天然契合的组织方式。 契合了，代码就简单，效率也高。
那么，如果场景需要的是“先来先服务”呢？那就该轮到队列了。
思考题 1
为什么函数调用天然适合用栈来组织？
思考题 2
为什么“撤销”操作很适合用栈实现？
小结
知识点
- 栈是后进先出的抽象数据类型
- 只在一端进行压栈、出栈、看栈顶
- 用数组或链表都能实现，基本操作
O(1) - 函数调用、括号匹配、表达式求值、撤销都用到栈
参考资料
- Wikipedia(zh)：堆栈：后进先出的数据结构
- Wikipedia(zh)：调用栈：函数调用信息的栈式存储
思考题答案（仅供参考）
思考题 1
因为函数调用具有“后进先出”的嵌套关系：最近的调用必须最先返回。把局部变量、返回地址等按调用顺序压栈，返回时从栈顶依次弹出，正好符合这种嵌套结构。
思考题 2
因为撤销需要“最后做的先撤”。每做一步就压入栈中，撤销时弹出最近的记录，顺序天然符合后进先出。用栈来实现，既直观又高效。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪