04 - 栈：只能从一头进出

从这一章起，我们看几种「限制了使用方式」的数据结构。你可能会奇怪：给数据结构加限制，不是让它更弱吗？恰恰相反——限制得当，反而让它特别适合某类问题，用起来又简单又不容易错。 栈就是第一个例子。

栈是什么：只能从顶上进出

栈（Stack） 是一种只能从一头进出的结构。这一头叫「栈顶」。

• 放东西（叫入栈 / push）：只能放在最上面。
• 拿东西（叫出栈 / pop）：只能从最上面拿。

它的核心规则叫 后进先出（LIFO，Last In First Out）：最后放进去的，最先被拿出来。

最贴切的比喻是一摞盘子：

       ┌─────┐  ← 栈顶：只能从这里放/取
       │ 盘4 │     （最后放的，最先拿）
       ├─────┤
       │ 盘3 │
       ├─────┤
       │ 盘2 │
       ├─────┤
       │ 盘1 │  ← 栈底：最先放的，最后才拿到
       └─────┘

你洗好盘子一个个往上摞，用的时候也从最上面拿。想拿最底下那个盘 1？得先把上面的都拿走。

• 入栈、出栈都是 O(1)：只在栈顶操作，一步搞定，非常快。

栈擅长解决什么：需要「后来先处理」的场景

只要一个问题有「最近发生的事，要最先处理/撤销」的特征，栈就特别合适。

场景 1：撤销功能（Ctrl+Z）

你在编辑器里每做一个操作，就把它 push 进栈。按撤销时，pop 出最近那个操作撤掉。最后做的，最先被撤销——完美契合栈。

场景 2：函数调用（这是最重要的一个）

还记得操作系统/组成原理里程序的执行吗？程序里 A 函数调用 B、B 又调用 C，计算机就是用栈来管理的（叫「调用栈」）：

• 调用 A，A 入栈；A 里调用 B，B 入栈；B 里调用 C，C 入栈。
• C 执行完返回，C 出栈；回到 B，B 执行完出栈；回到 A。

最后被调用的最先返回，正是后进先出。你听过的「栈溢出（Stack Overflow）」错误，就是函数嵌套调用太深（比如无限递归），把这个调用栈撑爆了。

场景 3：括号匹配 / 表达式求值

检查代码里括号是否配对：遇到左括号 push，遇到右括号就 pop 一个出来看是否匹配。浏览器前进/后退、计算器算式，也都用栈。

一个小直觉

只要你听到「最近的、最后的、最新的」要优先处理，或者「层层嵌套、后开的先关」，脑子里就该跳出「栈」。

小结

• 栈只能从一头（栈顶）进出，规则是后进先出（LIFO），像一摞盘子。
• 核心操作：入栈 push、出栈 pop，都在栈顶，都是 O(1)。
• 擅长「最近发生的要最先处理/撤销」「层层嵌套后开先关」的场景。
• 经典应用：撤销功能、函数调用栈（栈溢出就是它爆了）、括号匹配、浏览器前进后退。
• 直觉口诀：听到「最近的优先」「后开先关」，就想到栈。

下一章 → 05 - 队列：排队叫号 ｜ 回到 README 目录