栈：后进先出结构与典型应用
学完顺序表和链表之后，一个很自然的问题就是：这些基础结构本身能不能进一步抽象成更有明确访问约束的模型？答案当然可以，而栈就是最经典的第一类。它不再允许你像线性表那样在任意位置自由访问和修改，而是主动收紧操作范围，只允许在同一端进行插入和删除。也正因为这种限制，栈反而变得更有力量：规则简单、行为稳定、适合表达一类非常典型的问题。
栈最核心的特征通常只需要一句话就能概括：后进先出，也就是 Last In First Out，常写作 LIFO。最后放进去的元素，会最先被取出来；越早进去的元素，越靠近底部，越晚才能被访问到。这个规律听起来很朴素，但它在程序世界里出现得非常频繁。函数调用栈、表达式求值、括号匹配、浏览器返回、撤销操作、深度优先搜索，都和栈的思想有非常直接的关系。
所以栈这一篇最重要的，不只是知道它能 push 和 pop，而是理解：
- 为什么“只能在一端操作”反而是一种强约束下的高效抽象；
- 为什么这么简单的结构会在系统和算法里反复出现；
- 为什么很多看似不同的问题，背后其实都符合“最后进入的状态，最先需要处理”这一模式。
一、什么是栈
栈可以先从抽象数据类型的角度来理解：
栈是一种只允许在表的一端进行插入和删除操作的线性结构。
这一端通常被称为栈顶，另一端称为栈底。
于是栈中最重要的规则就出来了：
- 新元素只能从栈顶进入；
- 删除元素也只能从栈顶移除；
- 因此最后进入栈顶的元素，会最先离开。
这就是“后进先出”的本质。
如果把它想象成一摞盘子，会非常直观：
- 你往上面放一个新盘子；
- 取的时候也总是先拿最上面那个；
- 最早放进去的盘子会被压在下面，必须等上面的都拿掉之后才能取到。
这种模型虽然简单，但非常适合描述“最近进入的内容应该最先处理”的问题。
二、栈通常支持哪些操作
如果从 ADT 视角看，栈最常见的操作通常只有这几个：
push(x)：把元素压入栈顶；pop()：弹出栈顶元素；peek()或top()：查看栈顶元素但不删除；isEmpty()：判断栈是否为空；size()：获取栈中元素个数。
你会发现，和线性表相比，栈的接口非常克制。它故意不鼓励你去中间访问、随机修改，而是把操作集中在一个端点上。
这种限制并不是“功能变少了”，而是让结构的语义更清晰，也让很多操作的复杂度更稳定。
三、为什么栈是线性表的受限版本
前面我们说过，栈不是凭空出现的，它可以看成是线性表在访问规则上的一种特化。
线性表允许你：
- 按位置访问；
- 在任意位置插入删除；
- 查找任意元素。
而栈把这些自由度收紧成：
- 只能在栈顶插入；
- 只能在栈顶删除；
- 最常关注的只有栈顶元素。
所以你可以把栈理解成一种“操作受限，但行为模式更明确”的线性结构。
这种受限设计非常重要，因为它带来了两个直接好处：
- 实现通常会更简单；
- 某些场景的建模会特别自然。
数据结构里有一个很常见的思想就是：
不是所有时候都追求“越自由越好”，很多时候恰恰是通过限制操作，换来更清晰的语义和更稳定的效率。
栈就是这类思想最典型的例子。
四、栈为什么容易实现
因为栈只需要关心一个端点，也就是栈顶。
不管你用什么底层结构实现，只要能高效维护栈顶附近的操作，栈的核心能力就能成立。
这也是为什么栈通常有两种最经典的实现方式：
- 顺序栈，也就是用顺序表或动态数组实现；
- 链式栈，也就是用链表实现。
由于操作范围很集中，栈的 push 和 pop 都很容易做到常数级，这一点比一般线性表要稳定得多。
五、顺序栈是什么
顺序栈可以理解成：
用一段连续存储空间来保存栈中的元素，并用一个变量记录当前栈顶位置。
它的典型特点是：
- 底层通常是数组或动态数组；
- 栈顶一般放在数组末尾；
- 入栈相当于尾部追加；
- 出栈相当于尾部删除。
如果底层是动态数组，那么：
- 查看栈顶通常是
O(1)； - 入栈通常是均摊
O(1)； - 出栈通常是
O(1)。
顺序栈的优点非常明显：
- 实现简单；
- 内存局部性好；
- 栈顶操作很快；
- 常数开销通常较小。
但它也保留了顺序存储的一些特性，比如依赖连续空间，以及在静态实现下可能会遇到容量限制。
六、链式栈是什么
链式栈通常是：
用链表来表示栈，并把链表头部作为栈顶。
这样设计很自然，因为：
- 头插相当于入栈；
- 删除头节点相当于出栈；
- 查看头节点相当于查看栈顶。
链式栈的特点通常是：
- 不要求连续空间；
- 理论上更灵活，不容易受固定容量限制；
- 栈顶插入删除也能做到
O(1)； - 但每个节点会有额外指针开销。
所以顺序栈和链式栈并不是谁绝对更好，而是两种不同的实现取舍：
- 顺序栈通常更紧凑、更快；
- 链式栈通常更灵活、扩展性更自然。
七、栈的复杂度为什么通常很稳定
这是栈很重要的一个特点。
由于栈所有核心操作都集中在栈顶，所以：
push通常是O(1)；pop通常是O(1)；peek通常是O(1)；isEmpty通常也是O(1)。
如果是基于动态数组的顺序栈，入栈偶尔会因为扩容出现一次较贵操作，但从均摊角度看仍然通常是 O(1)。
这说明栈非常适合那种“只关心最近状态”的场景，因为它既能清晰表达语义，又能提供稳定的局部操作效率。
八、为什么说函数调用本身就是一个栈过程
这是栈最经典、也最重要的现实应用之一。
程序在执行函数调用时，通常会为每次调用创建一份调用记录，用来保存：
- 参数；
- 局部变量；
- 返回地址；
- 调用状态。
这些调用记录通常放在调用栈里。
于是执行过程就非常符合栈的规律：
- 调用一个新函数，相当于把一个新的调用帧压入栈顶；
- 当前函数执行结束后，相当于从栈顶弹出这一帧；
- 总是最后调用的函数先返回。
这和我们前面学递归时看到的执行过程完全一致。所以从某种意义上说，递归之所以能成立，背后正是因为系统用栈维护了层层调用关系。
也正因为这样，递归太深时才会出现栈溢出问题。这不是“递归神秘”，而只是调用栈空间有限。
九、括号匹配为什么适合用栈
这是栈在算法题里最经典的入门应用。
例如一个表达式里有 ()、[]、{}，我们要判断括号是否匹配。直觉上，后出现但尚未闭合的左括号，应该优先等待匹配它后面最近出现的右括号。
这件事和栈非常吻合：
- 遇到左括号就压栈；
- 遇到右括号就检查栈顶是否是对应类型的左括号；
- 如果匹配就弹栈；
- 最后栈为空，则匹配成功。
这里背后的本质就是：
最近打开但还没关闭的结构，必须最先被关闭。
这正是一个典型的后进先出过程。
十、表达式求值和栈有什么关系
中缀表达式、后缀表达式、运算符优先级处理，也都和栈高度相关。
例如处理中缀表达式时，常常需要解决这些问题：
- 运算符什么时候参与计算；
- 括号如何改变优先级；
- 某个运算符应该先处理还是后处理。
这时，栈就非常适合作为“暂存最近尚未处理运算符或操作数”的结构。
很多经典算法都会用：
- 一个栈存运算符；
- 一个栈存操作数；
或者直接把表达式转换成更容易计算的后缀表达式，再借助栈求值。
所以你会发现，栈特别适合那些“当前还不能立刻处理，需要暂时挂起，等后面时机成熟再处理”的场景。
十一、浏览器返回、撤销操作为什么也符合栈模型
这类例子在日常使用中最容易感受到。
1. 浏览器返回
你访问页面的顺序通常是：
- A 页面；
- B 页面；
- C 页面；
此时点击返回，最先离开的应该是最近进入的 C，然后才是 B，最后才轮到 A。这显然符合栈模型。
2. 撤销操作
在编辑器里，你最近做的一次修改，通常会最先被撤销；更早之前的修改，则要等最近操作撤销后才会轮到。
这本质上也是：
- 最新状态最先回退；
- 早期状态后回退。
所以很多撤销、回退、历史状态恢复，本质上都非常适合用栈来维护。
十二、深度优先搜索为什么常和栈联系在一起
图和树的深度优先搜索 DFS，无论是显式写栈，还是用递归，本质上都离不开栈思想。
因为深度优先搜索的行为模式是：
- 先沿着当前路径一直往深处走；
- 走不通了再回退到最近的分叉点；
- 再继续尝试新的分支。
这里“最近的分叉点先被回退处理”，本质上就是后进先出。
如果用递归写 DFS，系统调用栈在替你隐式维护这条路径；如果不用递归，就常常要自己显式维护一个栈。
所以栈不仅是一个独立结构，也是一种很强的“过程组织方式”。
十三、什么时候一个问题适合想到栈
这是学栈时最值得培养的判断能力。
一个问题如果具备下面这些特征，往往就可以考虑栈：
- 最近进入的状态要最先处理；
- 需要沿着一条路径不断深入，再逐层回退；
- 某些元素需要暂存，等待未来某个时机再处理；
- 存在明显的嵌套结构；
- 需要匹配“最近未完成的部分”。
例如：
- 括号匹配；
- 函数调用；
- 表达式求值；
- 路径回退；
- 单调栈类问题；
- 深度优先遍历。
也就是说，真正学会栈，不是背一个定义，而是看到问题时能识别出“这里是不是最近进入的东西要最先出来”。
十四、学习栈时最容易踩的坑
1. 只记住后进先出，但不会识别应用场景
这是最常见的问题。定义背得很熟，但一到题目里就不知道什么时候该用栈。
2. 忘记判空
无论是顺序栈还是链式栈，在 pop 或 peek 前都要先考虑空栈情况。
3. 把“栈”和“递归”当成两套无关知识
其实递归背后就是调用栈，二者联系非常紧密。
4. 对顺序栈和链式栈的差别没有建立复杂度和实现视角
虽然它们核心操作都很快，但内存组织、扩容方式、空间开销并不一样。
5. 只会写基本栈操作，不理解为什么某些问题天然符合栈模型
真正重要的是模式识别能力，而不是 push、pop 几行代码。
十五、为什么栈是后面很多主题的基础
栈虽然看起来比线性表更“收缩”，但它的影响范围非常广。
后面你会不断遇到和栈相关的内容：
- 递归和调用栈；
- 表达式求值；
- 深度优先搜索；
- 单调栈；
- 语法解析中的嵌套结构处理；
- 编译器和解释器中的部分状态维护。
这说明栈并不是一个“功能单一、只适合入门”的结构。恰恰相反，它是那种规则很简单，但可以稳定迁移到很多复杂问题中的基础模型。
总结
栈的重要性，不只是因为它简单，而是因为它把“最近状态优先处理”这类问题抽象得非常清楚。真正值得先建立起来的，是这些核心认识：
- 栈是一种只允许在一端插入和删除的线性结构，核心规律是后进先出；
- 它是线性表的一种受限版本，通过限制操作换来了更清晰的语义和更稳定的局部效率；
- 顺序栈和链式栈都能高效实现栈，但它们在空间组织和实现细节上有所不同；
- 函数调用、递归、括号匹配、表达式求值、浏览器返回、撤销操作和深度优先搜索都和栈高度相关；
- 真正学会栈，不是只会几个基础操作，而是能识别“最近进入的内容应该最先处理”的问题模式；
- 栈既是一种具体数据结构，也是一种非常重要的过程组织思想。
把这一篇理解透之后，后面再去学队列时，你会更明显地看到另一种完全不同的访问约束：一个强调后进先出，一个强调先进先出。它们共同说明了一件很重要的事：在数据结构里，限制操作方式并不是削弱能力，很多时候恰恰是在为某类问题提炼最合适的表达模型。
参考资源：