一文通解：数据结构之 栈

上周同事小王找我 debug说他的递归方法一直报StackOverflowError我一看代码——递归终止条件写反了。我说老弟你这是栈溢出了。他一脸茫然栈什么栈Java 里不就有个Stack类吗很多 Java 程序员天天写代码Stack类倒也用过JVM 栈溢出也见过但真要系统地说清楚栈到底是什么、它凭什么这么重要、它在 Java 世界里有多少种存在形式可能就支支吾吾了。这篇文章就是重点把栈这件事彻底搞明白的。我们不讲枯燥的理论不写晦涩的数学公式就从你每天都在用的功能出发为什么按 CtrlZ 能撤销为什么浏览器能后退为什么递归太深会 StackOverflow——读完你会发现栈无处不在而你已经用了它很多年只是不认识它而已。一、先从一个生活场景说起——叠盘子与后入先出在正式写代码之前我想请你想象一个场景你去自助餐厅吃饭后厨洗完的盘子是这样叠放的↑ 新的盘子放最上面入栈 ┌───┐ │ 5 │ ← 最后一个放上去的 │ 4 │ │ 3 │ │ 2 │ │ 1 │ ← 第一个放上去的 └───┘ ↓ 取盘子也从最上面取出栈规则只有一条你只能从最上面拿盘子。你不能从中间抽一个也不能从最底下掏一个。这就意味着最后一个放上去的盘子一定是第一个被拿走的。英文里叫LIFOLast In, First Out中文叫后进先出。栈的 LIFO 特性不是人为规定的而是只能在一端操作这个限制自然导致的结果。就像你没法从盘子堆的中间抽出一个盘子而不把上面的全弄倒——这不是规矩是物理规律。叠盘子的规则搞懂了栈你也就懂了 70%。下面我们把它翻译成计算机语言。二、栈的基本操作就三招两式栈是数据结构里最简单的之一——操作只有三种一手数得过来2.1 核心三操作操作英文名大白话解释图解入栈push把元素放到栈顶往盘子堆顶上再摞一个出栈pop把栈顶元素取出来并删除从盘子堆顶上拿走一个查看栈顶peek/top看一眼栈顶元素是什么不删除瞅一眼最上面的盘子但不拿走// 伪代码示意 Stack stack new Stack(); stack.push(1); // 栈[1] stack.push(2); // 栈[1, 2] stack.push(3); // 栈[1, 2, 3] ← 3 在栈顶 stack.peek(); // 返回 3 ← 只是看看栈不变 stack.pop(); // 返回 3 ← 拿走栈顶栈[1, 2] stack.pop(); // 返回 2 ← 栈[1]2.2 两个辅助操作操作英文名大白话解释判空isEmpty栈里还有东西吗查大小size栈里现在有几个元素就这么多。没了。栈就是这么朴素的家伙——不像树有一堆术语不像图有各种遍历算法。正因为简单所以它在软件工程中无处不在。好了概念讲完了。接下来我们动真格的——用 Java 亲手实现一个栈。自己写过一遍比什么记忆法都好使。三、用 Java 徒手撸一个栈写过才真正理解栈有两种主流实现方式数组和链表。两种各有优劣咱们各写一个。3.1 数组实现顺序栈public class ArrayStackT { private Object[] elements; // 存储元素的数组 private int top; // 栈顶指针指向栈顶元素的位置 private static final int DEFAULT_CAPACITY 10; public ArrayStack() { this.elements new Object[DEFAULT_CAPACITY]; this.top -1; // -1 表示空栈 } // 入栈 public void push(T item) { if (top elements.length - 1) { resize(); // 满了就扩容 } elements[top] item; // 先移动指针再放入元素 } // 出栈 SuppressWarnings(unchecked) public T pop() { if (isEmpty()) { throw new EmptyStackException(); } T item (T) elements[top]; elements[top] null; // 防止内存泄漏 top--; return item; } // 查看栈顶 SuppressWarnings(unchecked) public T peek() { if (isEmpty()) { throw new EmptyStackException(); } return (T) elements[top]; } public boolean isEmpty() { return top -1; } public int size() { return top 1; } // 扩容为原来的 2 倍 private void resize() { elements Arrays.copyOf(elements, elements.length * 2); } }图解数组栈的工作过程初始状态 push(10) 后 push(20) 后 pop() 后 ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ │ │ │ │ │ │10 │ │ │ │ │10 │20 │ │ │ │10 │20 │ │ │ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ top -1 top 0 top 1 top 0 (20 被取出)3.2 链表实现链式栈public class LinkedStackT { // 节点内部类 private static class NodeT { T data; NodeT next; Node(T data, NodeT next) { this.data data; this.next next; } } private NodeT top; // 栈顶节点 private int size; // 入栈在链表头部插入 public void push(T item) { top new Node(item, top); // 新节点指向旧栈顶 size; } // 出栈从链表头部删除 public T pop() { if (isEmpty()) { throw new EmptyStackException(); } T item top.data; top top.next; // 栈顶指针后移 size--; return item; } // 查看栈顶 public T peek() { if (isEmpty()) { throw new EmptyStackException(); } return top.data; } public boolean isEmpty() { return top null; } public int size() { return size; } }链表实现中push和pop都在链表头部操作时间复杂度都是 O(1)。注意是头部而不是尾部——如果你每次push都要遍历到链表尾部那时间复杂度就变成 O(n) 了这是初学者常犯的错误。3.3 两种实现的对比维度数组实现链表实现访问速度快连续内存缓存友好稍慢节点分散缓存不友好动态扩容需要扩容时有 O(n) 开销天然动态随用随加内存占用可能浪费预留空间每个节点多一个指针开销线程安全都不安全都不安全适用场景数据量可预估数据量不确定Java 标准库里的Stack类用的是数组继承了Vector而ArrayDeque推荐用来替代 Stack也是用循环数组实现的。下面会详细讲。自己手写了两个栈你应该对栈的底层原理了然于胸了。但写项目时没人会手写栈——接下来我们看看 Java 标准库里给我们准备了什么。四、Java 集合框架中的栈Stack 与 Deque 的新旧交替4.1 Stack 类——一个不应该再用的老古董java.util.Stack是 Java 1.0 就有的类直接继承自Vectorpublic class StackE extends VectorE { public E push(E item) { ... } public synchronized E pop() { ... } public synchronized E peek() { ... } public boolean empty() { ... } public synchronized int search(Object o) { ... } }问题很大继承 VectorStack 是 LIFO 的但继承了 Vector 以后你可以调用get(index)从中间取元素、add(index, e)往中间插入——完全破坏了栈的语义。所有方法都是synchronized不管你需不需要线程安全它都给你加锁性能差。官方都不推荐了Java 官方文档明确说应该使用Deque接口来替代。// 反例虽然编译通过但完全违背了栈的设计初衷 StackInteger stack new Stack(); stack.push(1); stack.push(2); stack.add(1, 99); // 往栈中间插入这不是栈该有的操作 stack.get(0); // 从栈底取元素这也行4.2 Deque——官方推荐的栈替身DequeDouble Ended Queue双端队列是 Java 6 引入的接口你可以把它当成栈用也可以当成队列用// 把 Deque 当栈用 DequeInteger stack new ArrayDeque(); stack.push(1); // 入栈 stack.push(2); // 入栈 stack.push(3); // 入栈 stack.pop(); // 出栈返回 3 stack.peek(); // 查看栈顶返回 2操作Stack 类的方法Deque 当作栈用的方法Deque 当作队列用的方法入栈 / 入队push(e)push(e)或addFirst(e)offer(e)或addLast(e)出栈 / 出队pop()pop()或removeFirst()poll()或removeFirst()查看 / 查看peek()peek()或peekFirst()peek()或peekFirst()4.3 ArrayDeque 和 LinkedList选哪个ArrayDeque和LinkedList都实现了Deque接口都可以当栈用DequeString stack1 new ArrayDeque(); // 推荐 DequeString stack2 new LinkedList(); // 也可以但不够好维度ArrayDequeLinkedList底层结构循环数组双向链表内存占用更低无节点开销更高每个 Node 多两个指针扩容开销需要扩容翻倍无缓存友好度高连续内存低内存分散支持 null❌ 不支持✅ 支持推荐做法当栈用时永远用ArrayDeque。除非你需要频繁在栈中间操作元素但这本身就不是栈的用法否则LinkedList没有优势。// 标准姿势 DequeInteger stack new ArrayDeque(); // 面试时如果你还在写 StackInteger stack new Stack() // 面试官可能会在心里默默扣分好了栈的基础知识和 Java 实现都讲清楚了。下面才是最精彩的部分——栈到底能干什么你平时用的哪些功能背后都是栈在默默工作五、栈的经典应用场景——原来这些功能都是它干的5.1 浏览器前进后退——双栈协作你用浏览器时一定点过后退和前进按钮。这个功能就是两个栈实现的public class BrowserHistory { private DequeString backStack new ArrayDeque(); private DequeString forwardStack new ArrayDeque(); private String currentUrl; // 访问新页面 public void visit(String url) { if (currentUrl ! null) { backStack.push(currentUrl); // 当前页进后退栈 } currentUrl url; forwardStack.clear(); // 前进栈清空新页面后不能前进了 } // 后退 public String back() { if (backStack.isEmpty()) return null; forwardStack.push(currentUrl); // 当前页进前进栈 currentUrl backStack.pop(); // 从后退栈取上一个页面 return currentUrl; } // 前进 public String forward() { if (forwardStack.isEmpty()) return null; backStack.push(currentUrl); // 当前页进后退栈 currentUrl forwardStack.pop(); // 从前进栈取下一个页面 return currentUrl; } }5.2 撤销操作Undo/Redo——写代码最离不开的功能你写代码时狂按 CtrlZ 的时候背后就是一个栈在帮你记住每一步操作public class TextEditor { private DequeString undoStack new ArrayDeque(); private DequeString redoStack new ArrayDeque(); private String text ; // 执行操作前保存快照 public void type(String newText) { undoStack.push(text); // 旧状态入栈 text newText; redoStack.clear(); // 新操作后 redo 栈清空 } // CtrlZ public String undo() { if (undoStack.isEmpty()) return text; redoStack.push(text); // 当前状态进 redo 栈 text undoStack.pop(); // 恢复上一个状态 return text; } // CtrlY public String redo() { if (redoStack.isEmpty()) return text; undoStack.push(text); // 当前状态进 undo 栈 text redoStack.pop(); // 恢复下一个状态 return text; } }5.3 括号匹配——IDEA 的自动括号高亮就是它你写代码时IDEA 会自动把匹配的括号高亮出来。这个功能的底层算法就是用栈做的public class BracketMatcher { public static boolean isValid(String s) { DequeCharacter stack new ArrayDeque(); for (char c : s.toCharArray()) { if (c ( || c [ || c {) { stack.push(c); // 左括号入栈 } else { if (stack.isEmpty()) return false; // 没有配对的左括号 char top stack.pop(); // 弹出栈顶左括号 if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; // 类型不匹配 } } } return stack.isEmpty(); // 栈为空说明全部配对成功 } public static void main(String[] args) { System.out.println(isValid(()[]{})); // true System.out.println(isValid(([)])); // false System.out.println(isValid({[()]})); // true } }图解算法过程以{[()]}为例这个算法是LeetCode 20面试出镜率极高。建议你自己手写三遍直到不看模板也能写出来。5.4 表达式求值——计算器背后的中缀转后缀你在电脑上敲3 4 × 2计算器得出11而不是14——这是因为它先算乘除再算加减。这个优先级处理就是用栈来实现的。这个过程分两步中缀表达式 → 后缀表达式 → 计算。public class ExpressionEvaluator { // 计算后缀表达式逆波兰表达式 public static int evalRPN(String[] tokens) { DequeInteger stack new ArrayDeque(); for (String token : tokens) { switch (token) { case - stack.push(stack.pop() stack.pop()); case - - { int b stack.pop(); int a stack.pop(); stack.push(a - b); // 注意顺序 } case * - stack.push(stack.pop() * stack.pop()); case / - { int b stack.pop(); int a stack.pop(); stack.push(a / b); // 注意顺序 } default - stack.push(Integer.parseInt(token)); } } return stack.pop(); } public static void main(String[] args) { // 3 4 × 2 的后缀表达式[3, 4, 2, *, ] System.out.println(evalRPN(new String[]{3, 4, 2, *, })); // 输出11 } }计算过程图3 4 2 * │ │ │ │ │ ↓ ↓ ↓ ↓ ↓ 3 4 2 → 读到 *弹出 2 和 4计算 4×28推回 8 3 8 → 读到 弹出 8 和 3计算 3811推回 11 11 → 最终结果5.5 深度优先搜索DFS——树的三种遍历全靠栈二叉树的先序、中序、后序遍历递归写法确实简单但面试官通常还会追问一句你能用迭代的方式写吗迭代版的二叉树遍历核心就是手动用一个栈模拟递归public class TreeTraversal { // 迭代版中序遍历左-根-右 public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode current root; while (current ! null || !stack.isEmpty()) { // 一路向左沿途全部入栈 while (current ! null) { stack.push(current); current current.left; } // 左到底了弹出栈顶根然后转向右子树 current stack.pop(); result.add(current.val); current current.right; } return result; } }这些应用场景看下来你应该能感受到——栈虽然结构简单但在实际开发中的应用场景非常多。面试中这些都是高频考点尤其是括号匹配和表达式求值几乎是栈相关题目的标准题库。好接下来我们往深里走一层——栈不仅在应用层面有用在 JVM 底层它更是 Java 程序运行的生命线。六、深入 JVM每个 Java 线程都背着一条栈龙6.1 JVM 中的栈是什么JVM 的内存模型中每个线程都有自己独享的一块内存区域叫作Java 虚拟机栈Java Virtual Machine Stack。6.2 栈帧方法的运行档案每当你调用一个方法JVM 就在虚拟机栈里创建一个栈帧Stack Frame把它压入栈顶。方法执行完这个栈帧就从栈顶弹出。main() 调用 methodA() 调用 methodB() 调用 ┌──────┐ ┌──────┐ ┌──────┐ │main │ │ A │ │ B │ │栈帧 │ │栈帧 │ │栈帧 │ └──────┘ │main │ │ A │ │栈帧 │ │栈帧 │ └──────┘ │main │ │栈帧 │ └──────┘ methodB() 返回 methodA() 返回 main() 返回 ┌──────┐ ┌──────┐ ┌──────┐ │ A │ │main │ │ │ │栈帧 │ │栈帧 │ │ 空 │ │main │ └──────┘ └──────┘ │栈帧 │ └──────┘每个栈帧包含四部分组成部分存了什么大白话局部变量表Local Variables方法参数 方法内的局部变量方法的私人物品清单操作数栈Operand Stack计算过程中的中间数据方法的草稿纸动态链接Dynamic Linking指向运行时常量池中该方法的引用方法的身份证返回地址Return Address方法执行完后回到哪里方法的回家地址来一段代码感受一下public class StackFrameDemo { public static void main(String[] args) { int a 10; // main 的局部变量 int result add(a, 20); // 调用 add创建 add 的栈帧 System.out.println(result); } // main 的栈帧销毁 public static int add(int x, int y) { int sum x y; // add 的局部变量 return sum; } // add 的栈帧销毁返回 main }执行过程main 开始执行 add 被调用 add 返回后 ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │ main 栈帧 │ │ add 栈帧 │ ← 栈顶 │ main 栈帧 │ │ a 10 │ │ x 10 │ │ a 10 │ │ result ? │ │ y 20 │ │ result 30 │ └──────────────┘ │ sum 30 │ └──────────────┘ ├──────────────┤ │ main 栈帧 │ └──────────────┘6.3 StackOverflowError——每个 Java 人都见过的红色现在你应该能理解这个经典错误了public void recursive() { recursive(); // 没有终止条件无限递归 } // java.lang.StackOverflowError原因每次调用recursive()都会创建一个新的栈帧压入虚拟机栈。栈的容量是有限的默认约 1MB当栈帧数量超过栈的容量就抛出StackOverflowError。// 可以通过 JVM 参数调整栈大小 // -Xss256k设置每个线程的栈大小为 256KB // -Xss2m 设置每个线程的栈大小为 2MB面试常见追问StackOverflowError和OutOfMemoryError有什么区别StackOverflowError栈空间不够用通常是递归太深导致的。OutOfMemoryError: Java heap space堆空间不够用通常是创建了太多对象。关键区别一个发生在栈线程私有一个发生在堆线程共享。JVM 的栈原理讲完了。你可能已经发现——JVM 的栈和数据结构里的栈本质上就是同一个东西在不同层面的应用。下面我们聊一个与之密切相关的话题递归。七、栈与递归你不写栈但栈无处不在7.1 递归本质上就是栈写过递归的同学都知道递归代码通常很简洁但背后 JVM 帮你做了一堆事情——每次递归调用都创建一个新栈帧。以经典问题——反转单链表为例// 递归版优雅但暗藏玄机 public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; // 递归终止条件 } ListNode newHead reverseList(head.next); // 递归深入 head.next.next head; // 反转指针 head.next null; return newHead; // 层层返回 }递归调用栈的过程反转链表 1→2→3→nullreverseList(1): newHead reverseList(2) 等待中... reverseList(2): newHead reverseList(3) 等待中... reverseList(3): 返回 3 ← 触底反弹 reverseList(2): 3.next 2, 2.next null 返回 3 reverseList(1): 2.next 1, 1.next null 返回 37.2 递归的隐患与解法递归虽然优雅但有两大问题栈溢出深度大了就 StackOverflow重复计算斐波那契递归是最经典的例子fib(5)会重复计算fib(3)两次、fib(2)三次……// 递归版斐波那契时间复杂度 O(2^n)极其低效 public int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); } // 迭代版用栈思想但不递归时间复杂度 O(n) public int fib(int n) { if (n 1) return n; int a 0, b 1; for (int i 2; i n; i) { int sum a b; a b; b sum; } return b; }经验法则能用迭代解决的问题尽量用迭代。递归只在分治场景如树的遍历、归并排序才真正有优势。别为了代码短而滥用递归。理论知识学得差不多了。下面我们转入面试实战模式——把前面学的东西变成面试官眼中的高分答案。八、面试高频考题实战——把知识变成分数8.1 最小栈Min Stack——LeetCode 155题目设计一个栈支持push、pop、top操作并能在O(1)时间内获取栈中最小值。这个题的核心技巧是用两个栈一个正常存数据一个存当前最小值。class MinStack { private DequeInteger dataStack; // 存数据 private DequeInteger minStack; // 存每个阶段的最小值 public MinStack() { dataStack new ArrayDeque(); minStack new ArrayDeque(); } public void push(int val) { dataStack.push(val); // 如果 minStack 为空或 val 比当前最小值更小则入 minStack if (minStack.isEmpty() || val minStack.peek()) { minStack.push(val); } else { minStack.push(minStack.peek()); // 重复压入当前最小值 } } public void pop() { dataStack.pop(); minStack.pop(); // 同步弹出 } public int top() { return dataStack.peek(); } public int getMin() { return minStack.peek(); } }图解push(5) push(2) push(3) push(1) pop() dataStack dataStack dataStack dataStack dataStack ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ 5 │ │ 2 │ │ 3 │ │ 1 │ │ 3 │ └───┘ │ 5 │ │ 2 │ │ 2 │ │ 2 │ └───┘ │ 5 │ │ 5 │ │ 5 │ └───┘ └───┘ └───┘ minStack minStack minStack minStack minStack ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ 5 │ │ 2 │ │ 2 │ │ 1 │ │ 2 │ └───┘ │ 5 │ │ 2 │ │ 2 │ │ 2 │ └───┘ │ 5 │ │ 5 │ │ 5 │ └───┘ └───┘ └───┘ getMin()5 getMin()2 getMin()2 getMin()1 getMin()28.2 用栈实现队列——LeetCode 232题目用两个栈实现一个队列支持push、pop、peek、empty操作。栈是 LIFO队列是 FIFO。两个栈配合可以翻转两次负负得正。class MyQueue { private DequeInteger inStack; // 输入栈push 用 private DequeInteger outStack; // 输出栈pop/peek 用 public MyQueue() { inStack new ArrayDeque(); outStack new ArrayDeque(); } public void push(int x) { inStack.push(x); // 直接往入栈放 } public int pop() { if (outStack.isEmpty()) { transfer(); // outStack 空了就从 inStack 倒过来 } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { transfer(); } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() outStack.isEmpty(); } // 关键操作把 inStack 的元素全部倒入 outStack private void transfer() { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } }核心图解push(1) → push(2) → push(3) 第一次 pop() inStack outStack inStack → transfer → outStack ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ 3 │ │ │ │ │ │ 1 │ ← pop 出 1 │ 2 │ │ │ │ │ │ 2 │ │ 1 │ │ │ │ │ │ 3 │ └───┘ └───┘ └───┘ └───┘ (栈顶是3先进后出) (栈顶是1先进先出)复杂度虽然单次pop可能是 O(n)但均摊时间复杂度是 O(1)——每个元素只会被 transfer 一次。面试时能说出均摊 O(1)是一个加分点。8.3 有效的括号——LeetCode 20这道题在 5.3 节已经讲过这里补充几个要点时间复杂度 O(n)只需遍历一遍字符串空间复杂度 O(n)最坏情况下全是左括号全入栈面试官可能追问如果括号类型扩展到 4 种、5 种怎么办——代码不改逻辑只需增加判断条件。用HashMap存储配对关系更优雅private static final MapCharacter, Character PAIRS Map.of( ), (, ], [, }, { );8.4 每日温度——LeetCode 739单调栈经典题题目给定一个温度数组对于每一天需要等多少天才能遇到更高的温度。如果之后没有更高的温度记为 0。这道题是单调栈的经典应用public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] result new int[n]; DequeInteger stack new ArrayDeque(); // 存下标栈底→栈顶递减 for (int i 0; i n; i) { // 当前温度比栈顶对应的温度高 → 找到栈顶那天之后第一个高温 while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) { int prevDay stack.pop(); result[prevDay] i - prevDay; } stack.push(i); } return result; // 栈里剩下的都是后面没有更高温度的 }temperatures [73, 74, 75, 71, 69, 72, 76, 73] result [ 1, 1, 4, 2, 1, 1, 0, 0] 图解 i0(73): push(0) 栈[0] i1(74): 7473 → pop(0), result[0]1, push(1) 栈[1] i2(75): 7574 → pop(1), result[1]1, push(2) 栈[2] i3(71): 7175 → push(3) 栈[2,3] i4(69): 6971 → push(4) 栈[2,3,4] i5(72): 7269 → pop(4), result[4]1 7271 → pop(3), result[3]2 7275 → push(5) 栈[2,5] ...单调栈的特点栈内元素始终保持单调递增或单调递减。一旦遇到破坏单调性的元素就弹出栈顶来处理。这类题目还有接雨水LeetCode 42、柱状图中最大矩形LeetCode 84等套路类似。面试题也刷完了最后我们来一个串珠子式的总结——把今天聊的所有内容串成一条线。九、总结栈很小世界很大让我们回头看一眼这趟栈之旅生活中的栈 → 叠盘子、子弹夹 ↓ 数据结构中的栈 → LIFO、push/pop/peek两种实现数组 / 链表 ↓ Java 中的栈 → 别用 Stack 类用 Deque ArrayDeque ↓ 栈的应用 → 浏览器前进后退、CtrlZ 撤销、括号匹配、表达式求值 ↓ JVM 中的栈 → 方法调用栈帧、局部变量表、操作数栈 ↓ 栈的翻车现场 → StackOverflowError、递归过深 ↓ 面试中的栈 → 最小栈、双栈模拟队列、单调栈栈可能是所有数据结构里最简单的一个——没有旋转、没有平衡、没有复杂的遍历算法。但正是这种极致的简单让它成为了计算机科学中最基础、最通用的工具之一。从你按下 CtrlZ 的那一刻到 JVM 内部的每一次方法调用栈都在默默地执行着它的 LIFO 原则——后来者居上先到者垫底。