【数据结构】栈：后进先出的艺术

如果你去过自助餐厅，你一定见过那一叠叠整齐的盘子。

服务员往上放新盘子，你从最上面拿走盘子。这就是现实生活中的栈（Stack）。

在计算机科学里，栈是一种极其简单但又极其强大的数据结构。它遵循一个核心原则：后进先出（LIFO, Last In First Out）。今天，小明就带你看看这个“窄长”的容器里，到底装了多少算法的智慧。

一、栈的物理结构：只进不出（误）

想象一个死胡同，或者一个装网球的筒。

• 入栈（Push）：把东西塞进去，放在最上面。
• 出栈（Pop）：把最上面的东西拿出来。
• 查看栈顶（Peek/Top）：只看不拿。

栈是一种受限的线性表。它不像数组那样可以随便访问任意下标，你只能在“栈顶”这一头进行操作。

二、为什么要限制访问？

你可能会问：“小明，数组明明更灵活，为什么还要发明栈这种自我设限的东西？”

因为受限意味着确定性。

由于操作被限制在了一端，栈的操作时间复杂度是完美的 O(1)。而且，这种结构完美契合了人类和计算机处理“嵌套”问题的逻辑。

三、栈的三个经典应用场景

3.1 函数调用栈（Call Stack）

这是程序员每天都在打交道的东西。 当你执行 A() 函数，A 里面调用了 B()，B 里面又调用了 C()。

1. A 入栈。
2. B 入栈。
3. C 入栈。
4. C 执行完，出栈。
5. B 执行完，出栈。
6. A 执行完，出栈。

如果没有栈，计算机根本不知道从子函数回来后，该继续执行哪一行代码。

3.2 撤销操作（Undo / Ctrl+Z）

你在编辑器里写的每一笔，都被当做一个操作压入栈中。当你按下撤销键，系统就从栈顶弹出一个操作，并执行它的逆过程。

3.3 括号匹配

检查代码里的 () {} [] 是否闭合，最优雅的算法就是用栈：

• 遇到左括号，压入栈。
• 遇到右括号，弹出栈顶，看是否匹配。
• 最后如果栈空了，说明完全匹配。

四、栈的实现方式

1. 顺序栈：用数组实现。简单，但需要预先分配空间（或者动态扩容）。
2. 链式栈：用链表实现。不需要连续空间，但多了指针的内存开销。

总结

1. 栈是后进先出 (LIFO) 的受限线性表。
2. 操作简单高效，Push/Pop 均为 O(1)。
3. 应用广泛：函数调用、撤销重做、括号匹配、深度优先搜索 (DFS)。

小明建议： 理解栈不仅是为了面试，更是为了理解程序的运行逻辑。当你下次看到 StackOverflowError 时，你应该能瞬间想到：一定是哪里的递归太深，把那个“盘子桶”给撑爆了。

“栈和队列有什么区别？” “栈是先来的后走，队列是先来的先走。就像挤电梯和排队买奶茶的区别。” —— 小明

最后，送你一个冷笑话： 一个程序员去面试。 面试官：“请用一句话解释什么是栈。” 程序员（把简历塞回包里）：“我先走了。” 面试官：“？” 程序员：“这就是栈，最后一个进来的动作（放简历），第一个被撤销。” 面试官：“……你录取了。”