如果你去面 Java 岗位问数据结构栈Stack大概率会被第一批翻牌子。它看起来简单到不像话——一个“后进先出”背过的人满地都是。但你翻翻搜索记录就会发现“java面试八股文”、“栈和堆”、“数据结构期末复习”这些词常年挂在热门上说明越是看似简单的东西越有人在细节上栽跟头。今天这篇文章我不想写成 API 手册而是想从源码实现、运行时机制、面试真题到工程选型把 Java 里的栈完整拆一遍尤其会把那些“文档里不写、实战中踩坑”的地方说清楚。这篇文章适合三类人正在准备 Java 面试的人尤其是背了八股文但没细想过原理的、期末复习数据结构的学生、以及已经写了几年业务代码但从来没认真看过 Stack 源码的开发者。看完你至少能搞清楚一个问题为什么越来越多 Java 工程师说“别再用 Stack 类了”以及栈到底凭什么能同时出现在算法题、JVM 虚拟机和编译原理里。1. 先理解栈的本质一种被“限制”住的线性表反而有大用有人说栈很神奇其实它一点不神秘。栈的本质就是一个线性表只不过这个线性表只允许在一端进行插入和删除操作。这一端叫栈顶另一端叫栈底。你可以把栈理解成食堂里那种弹簧托盘架你只能把托盘放在最上面也只能从最上面拿走托盘。谁最后一个放上去谁第一个被拿走——这就是“后进先出”英文 Last In First Out缩写 LIFO。1.1 后进先出从一个生活场景到操作系统内核“后进先出”这个约束看似简单实际上威力巨大。你想想浏览器里的“后退”按钮你访问页面 A - B - C再点后退回到的是 B而不是 A你写文档时 CtrlZ 撤销撤销的总是最近一次操作。这些都是栈的典型应用它们有一个共同特征需要记住操作发生的时序并且必须能回退到上一时刻的状态。在操作系统和语言运行时内部栈更是无处不在。函数调用栈、表达式求值、异常处理、线程切换全都依赖栈。可以说没有栈程序根本无法运行。你写的 main 方法调用了一个 service 方法service 又调用了 dao 方法这个调用链在 JVM 里就是一个不断压栈和弹栈的过程。这种场景和食堂托盘架完全一样只不过托盘换成了“栈帧”而已。1.2 五个基础操作与时间复杂度栈这个“抽象数据类型”ADT核心操作就五个不多不少操作说明时间复杂度push(E e)元素入栈放到栈顶O(1)pop()弹出栈顶元素并移除O(1)peek()查看栈顶元素但不移除O(1)isEmpty()判断栈是否为空O(1)size()返回栈中元素个数O(1)为什么入栈出栈是 O(1)因为栈操作只发生在栈顶。你永远不需要遍历找到插入位置或删除位置头部就是你要操作的位置。当然这里说的是普通栈结构如果底层基于数组且容量不够push 可能触发扩容扩容要拷贝数组那一次性的时间复杂度是 O(n)。不过均摊下来动态栈的 push 仍然是 O(1)。这就引出一个很多初学者没想明白的点栈不是一种新的存储结构而是对已有存储结构数组或链表施加了“只能在一端操作”的约束。约束越多能力越受限但也越容易被高效实现和维护。这个道理放到软件设计里也是一样的。1.3 顺序栈和链栈底层用数组还是链表栈的实现方式一般分两种顺序栈数组实现和链栈链表实现。顺序栈底层用一块连续内存。你只需要维护一个 top 指针或者一个 size 变量push 时往 top 位置放元素再 top1pop 时 top-1 再把对应位置置空。它的优点是内存连续CPU 缓存友好随机访问快缺点是容量固定动态扩容除外满的时候要扩容。链栈底层用链表节点。每个节点包含数据和指向下一个节点的指针push 就是在链表头部插入一个新节点pop 就是删除头部节点。它的优点是理论上没有容量上限受堆内存限制不需要考虑扩容缺点是每个节点需要额外存储指针内存碎片化而且节点创建有开销。实际开发中数组实现的顺序栈是主流。Java 里的 ArrayDeque 就是典型的动态数组实现默认初始容量 16容量不够时自动翻倍。链表实现的链栈在真实业务里反而很少见更多是在面试手写题或某些无锁并发场景里出现。2. 官方 Stack 类的大坑继承 Vector 的历史包袱以及 Deque 的正确姿势如果你刚学 Java 不久第一反应可能是Java 不是有现成的 java.util.Stack 类吗直接 new Stack 然后用 push、pop 不就行了吗行是行但你要知道Stack 类在官方文档里早就被建议不要再用了。这不是某个技术大 V 的个人观点而是 JDK 文档里白纸黑字的建议“A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.”——翻译过来就是想用栈操作请去用 Deque 接口及其实现类别用我。2.1 Stack 类源码里的三大硬伤为什么官方这么不给面子打开 java.util.Stack 的源码一眼就能看出问题。第一Stack 直接继承自 Vector。这意味着 Stack 不是一个独立的类而是 Vector 的子类它天然继承了 Vector 的随机访问能力。换句话说你可以对一个栈执行 get(0) 这种操作可以直接遍历栈内部所有元素。这严重破坏了栈的“只能在一端操作”的约束——你本意是设计一个严格的栈结果别人想怎么访问就怎么访问。第二Vector 的每个方法上都加了 synchronized 锁。Stack 所有操作都是方法级同步这在单线程环境里纯粹是性能浪费。每次 push、pop 都要经过同步块虽然现代 JVM 会对无竞争锁做优化但总体开销依然比无锁实现大。第三Stack 缺少接口抽象。你在代码里如果用 Stack 类型声明变量那就被这个具体类绑死了。而 Deque 是接口你可以灵活替换实现类比如 ArrayDeque、LinkedList甚至自己实现的并发双端队列。面向抽象编程这是 Java 集合框架的基本素养Stack 却反着来。所以结论很明确除非你在维护古董代码否则不要再 new Stack()。面试的时候能说出这一层你就已经超过了绝大多数只会调 API 的候选人了。2.2 用 ArrayDeque 实现栈的正确姿势既然不让你用 Stack那用什么最推荐的是 ArrayDeque。它实现了 Deque 接口提供了一整套 LIFO 操作DequeString stack new ArrayDeque(); // 入栈 stack.push(Java); stack.push(数据结构); stack.push(栈); // 查看栈顶不会移除 System.out.println(stack.peek()); // 输出栈 // 出栈 String top stack.pop(); System.out.println(top); // 输出栈 System.out.println(stack.size()); // 输出2注意Deque 接口下操作栈的方法有好几对push/pop、addFirst/removeFirst、offerFirst/pollFirst。它们语义上都能用但细节有差别。push 在容量受限的 deque 中可能抛 IllegalStateException而无限制的 ArrayDeque 则不会pop 在栈为空时抛 NoSuchElementException。如果你需要更宽松的语义可以用 offerFirst 和 pollFirst它们不会抛异常而是返回特殊值来提示失败。我个人的习惯是写算法题和业务代码统一用 push/pop/peek因为它们语义最贴合“栈”。如果栈可能为空调用 pop 前一定要先判 isEmpty这是很多线上 bug 的源头。2.3 手写一个通用栈数组扩容版与链表头插版理解栈最好的方式就是亲手写一个。即使你平时直接用 ArrayDeque手写的过程也能帮你把扩容、空栈、泛型这些底层机制一次想清楚。下面先看数组扩容版public class MyStackE { private static final int DEFAULT_CAPACITY 10; private Object[] elements; private int size; public MyStack() { elements new Object[DEFAULT_CAPACITY]; } public void push(E e) { ensureCapacity(); elements[size] e; } SuppressWarnings(unchecked) public E pop() { if (size 0) { throw new RuntimeException(stack is empty); } E result (E) elements[--size]; elements[size] null; // 防止内存泄漏 return result; } SuppressWarnings(unchecked) public E peek() { if (size 0) { throw new RuntimeException(stack is empty); } return (E) elements[size - 1]; } public boolean isEmpty() { return size 0; } public int size() { return size; } private void ensureCapacity() { if (size elements.length) { elements Arrays.copyOf(elements, elements.length 1); } } }你有没有注意到一个细节pop 的时候我特意把 elements[size] 置为 null。这个操作叫“清空引用”目的是防止对象滞留。如果数组里还保留着被弹出元素的引用就算栈里已经看不到了这个对象也不会被回收时间久了就会内存泄漏。这在写通用容器时是个很重要的职业习惯。下面是链表头插版public class LinkedStackE { private NodeE head; private int size; private static class NodeE { E value; NodeE next; Node(E value) { this.value value; } } public void push(E e) { NodeE newNode new Node(e); newNode.next head; head newNode; size; } public E pop() { if (head null) { throw new RuntimeException(stack is empty); } E value head.value; head head.next; size--; return value; } public E peek() { if (head null) { throw new RuntimeException(stack is empty); } return head.value; } public boolean isEmpty() { return size 0; } public int size() { return size; } }每次 push 新节点前先把新节点的 next 指向当前 head再把 head 移到新节点上。这其实就是一个单链表的头插法时间复杂度 O(1)非常干净。面试时如果让你手写栈链表版和数组版写一个出来基本就能过关。3. 栈不止活在考试题里方法调用、表达式求值与括号匹配很多人觉得栈就是数据结构课程里的一个章节考试背完就扔。但栈实际上是整个计算机系统运行的底座之一。这节我把栈拉到运行时的视角讲讲它在 JVM、编译器和日常开发里的真实角色。3.1 方法调用就是压栈和弹栈JVM 栈帧机制与 StackOverflowErrorJVM 为每个线程分配了一个私有的虚拟机栈这个栈的生命周期和线程一致。每次调用一个方法JVM 就会创建并压入一个栈帧方法执行完毕这个栈帧就被弹出。栈帧里装的是局部变量表、操作数栈、动态链接和方法返回地址等一大堆运行信息。看一段简单的代码public class StackDemo { public static void main(String[] args) { int result add(1, 2); System.out.println(result); } public static int add(int a, int b) { return a b; } }main 方法先入栈然后调用 addadd 的栈帧压到 main 上面。add 执行完栈帧弹出返回值交给 main。整个过程就像叠盘子一层压一层。如果你写一个没有结束条件的递归public class RecursionDemo { public static void main(String[] args) { recurse(); } public static void recurse() { recurse(); } }每次递归都会压入一个新栈帧而栈的内存是有上限的默认大约是 512KB 到 1MB取决于平台和 JVM 参数栈帧越压越多迟早会把栈空间耗尽最终抛出著名的 StackOverflowError。这就是热门搜索里 “protect(): protection stack overflow” 这类错误的本家兄弟。解决这类问题要么是改递归为循环或显式栈要么是限制递归深度要么调整 JVM 栈大小参数-Xss。这里顺便提一个 JVM 调优的常识-Xss设置的是每个线程的栈大小。调大它能延缓递归溢出但也会增加内存占用因为 JVM 要给每个线程预留这么多空间。线程数一多内存就吃紧了。所以看到一个 StackOverflowError第一反应不应该是调大栈而应该是检查你的递归逻辑是否真的会终止。3.2 表达式求值双栈法如何计算一个中缀算式第二个经典应用是表达式求值。你输入3 4 * 2计算器怎么知道先算乘法再算加法因为人眼能看懂运算符优先级但程序不能。程序的解决方案之一就是用两个栈一个数字栈一个运算符栈。思路是这样的从左到右扫描表达式。遇到数字就压入数字栈遇到运算符的时候如果运算符栈为空或者当前运算符优先级高于栈顶运算符就压入运算符栈否则弹出栈顶运算符从数字栈弹出两个数做计算把结果压回数字栈然后重复比较。遇到左括号直接压栈遇到右括号则一直弹出运算符计算直到遇到左括号。以3 4 * 2为例扫描到*的时候因为*的优先级高于所以先把*压栈。继续扫描2压入数字栈。表达式结束开始弹运算符栈先弹*计算4 * 2 8再弹计算3 8 11。最终结果是 11正确。这种“双栈求值”是编译原理里表达式处理的雏形。Java 编译器、数据库的 SQL 解析器、模板引擎的表达式计算底层都有类似机制。你也许不会在手写一个计算器但理解了这套逻辑再看到“表达式中缀转后缀”、“调度场算法”这些名词就不会发怵了。3.3 括号匹配、DFS 与页面栈从算法到日常开发你上学时肯定做过括号匹配的题判断一个字符串里的括号是否正确嵌套。解决方式就是一个栈public 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 ! () return false; if (c ] top ! [) return false; if (c } top ! {) return false; } } return stack.isEmpty(); }这题的价值不只是面试你写代码时用的 IDE、格式化工具、解析器全都在靠这种机制检查语法结构的完整性。遇到括号不匹配编译器能精确报错说“期望 } 但实际上来了 )”背后就是栈在查岗。深度优先搜索DFS是另一个典型场景。递归实现 DFS 时系统调用栈本身就帮你做了“回溯”的管理如果不用递归就需要手动维护一个栈模拟递归压栈弹栈的过程。你在 LeetCode 上做二叉树前序遍历、迷宫寻路、岛屿数量全都能看到显式栈的身影。还有一个非常贴近我们日常开发的东西页面栈。小程序里访问页面就是压栈返回上一页就是弹栈热门搜索里那个“小程序页面栈大于10怎么处理”就是页面栈超过上限的问题。浏览器也是同样的逻辑你每开一页就压入一页点后退就弹出一页。浏览器和 JVM 在这一点上是相通的栈这个结构从内核到应用层无处不在。4. 面试真题与期末考点最小栈、单调栈、双栈队列与堆栈混淆栈是面试题的重灾区。因为栈本身简单所以面试官往往会把它当成底层工具设计出各种各样的变种题来考察你的算法能力和代码功底。这节我挑几道有代表性的题讲透你再遇到这类题至少不会发懵。4.1 栈和堆到底怎么分别被两个“栈”搞混先把这个最容易混淆的概念理清。搜索热词里“栈和堆”常年上榜说明太多人分不清数据结构的栈和 JVM 内存的栈。这是两个不同维度的概念。数据结构的栈和队列讨论的是数据组织方式栈是 LIFO队列是 FIFO。而 JVM 内存里的堆和栈讨论的是运行时存储划分方法中定义的局部变量、引用等放在虚拟机栈的栈帧中new 出来的对象实例存放在堆中。举个例子public void foo() { int a 10; String s new String(hello); }变量a是基本类型直接存在 main 的栈帧局部变量表里。变量s本身是一个引用也保存在栈帧里但它指向的 String 对象实体在堆上。所以“对象在堆上引用在栈上”是对Java对象内存分配最简单粗略的描述。那为什么大家说起递归溢出会提到栈说起大对象频繁创建会提到堆因为递归深度由栈大小决定而对象分配频率由堆管理。两个“栈”字很容易把人绕晕你面试时如果能主动区分这两个概念面试官通常会觉得你学得比较扎实。4.2 最小栈辅助栈的空间换时间最小栈是一道非常经典的题要求设计一个栈在 O(1) 时间内能获取栈中的最小值。你可能会想用一个变量记录最小值不就行了但问题在于pop 操作可能会把这个最小值弹出去那之前第二小的值怎么办所以一个变量明显不够。标准解法是额外维护一个辅助栈栈顶永远保存当前栈中的最小值。push 的时候如果当前值比辅助栈栈顶小就压入辅助栈否则辅助栈不压。pop 的时候如果主栈弹出的值等于辅助栈栈顶辅助栈也要弹。这样 getMin 只需要直接 peek 辅助栈即可class MinStack { DequeInteger stack new ArrayDeque(); DequeInteger minStack new ArrayDeque(); public void push(int val) { stack.push(val); if (minStack.isEmpty() || val minStack.peek()) { minStack.push(val); } } public void pop() { int val stack.pop(); if (val minStack.peek()) { minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }这题的底子就是“空间换时间”也是面试官最喜欢引导你往深里想的点。你可以想想如果面试官要求你用 O(1) 空间实现怎么办答案是用差值法栈里每个元素存的是和当前最小值的差值这样就不需要辅助栈了。不过差值法容易踩整型溢出的坑刷题时要注意边界。4.3 单调栈栈里存的是索引不只是值单调栈是在普通栈的基础上加了一条“单调性”约束栈中元素从栈底到栈顶保持单调递增或单调递减。它在解决“数组中某个元素离它最近的大/小数”这类问题时能把 O(n²) 暴力优化到 O(n)。最经典的题目是每日温度给你每天的温度要返回一个数组answer[i] 表示对于第 i 天下一个更高温度出现在几天后。暴力解法是双层循环而单调栈只需要一遍遍历public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] answer new int[n]; DequeInteger stack new ArrayDeque(); // 存索引 for (int i 0; i n; i) { while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) { int prevIndex stack.pop(); answer[prevIndex] i - prevIndex; } stack.push(i); } return answer; }核心思路是栈里保存的是下标而不是温度值本身。每次遇到一个新温度时不断和栈顶下标对应的温度比较如果新温度更高说明栈顶元素“找到了下一个更高温度”它就可以出栈了。因为每个下标最多入栈一次、出栈一次所以总时间复杂度 O(n)。单调栈在接雨水、柱状图最大矩形、滑动窗口最大值等题目中都能用到值得单独多练几道。4.4 双栈实现队列两次倒腾的摊还复杂度队列的规则是先进先出栈的规则是后进先出两者怎么用栈模拟队列办法是用两个栈一个 in 栈负责入队一个 out 栈负责出队。入队只管往 in 栈 push出队的时候如果 out 栈为空就把 in 栈所有元素依次 pop 再 push 进 out 栈这样元素顺序就被反转了再从 out 栈 pop 就变成了先进先出DequeInteger in new ArrayDeque(); DequeInteger out new ArrayDeque(); public void push(int x) { in.push(x); } public int pop() { if (out.isEmpty()) { while (!in.isEmpty()) { out.push(in.pop()); } } return out.pop(); }你可能会问这样会不会慢其实整体是摊还 O(1)。虽然每次 out 为空时需要倒腾一批元素但每个元素只被倒腾一次均摊到每个操作上复杂度还是常数。这道题能帮你理解“均摊分析”这个进阶概念面试时如果能把摊还复杂度的道理讲清楚是很加分的。4.5 空栈与异常最容易失分的小细节八股文背得再溜一个空栈操作就能让你当场翻车。Stack 的 pop 方法用peek()时空栈会抛 EmptyStackExceptionArrayDeque 的 push 在容量无限时不会抛异常但 pop 在空栈时会抛 NoSuchElementException。很多人在写算法题时忘了判空然后抛异常非常尴尬。还有一个细节是 Stack 的 search 方法它返回的是对象在栈中的 1-based 位置栈顶为 1。如果元素不存在返回 -1。这个方法的语义和 List 的 indexOf 完全不同我以前面试时就因为把这个搞混被面试官点过。现在我已养成了习惯凡是 stack.peek()、stack.pop() 之前先问自己一句——这个栈现在到底为空吗5. 工程视角的补充栈的线程安全、扩容策略与拷贝问题前面讲的都是栈的原理和算法接下来说几个工程实践中一定会碰到、但文档里很少写清楚的细节。5.1 Stack 的同步锁与并发场景选型Stack 类继承了 Vector所以它的方法都带 synchronized。这意味着 Stack 本身是线程安全的但线程安全不是免费午餐。方法级锁在并发高的时候会形成竞争热点性能比无锁容器差一个量级。而且它锁的粒度太粗整个方法从检查到修改都锁住并发度很低。如果你在多线程场景下需要栈结构我的建议是不要直接用 Stack也不要用普通的 ArrayDeque它非线程安全而是用 ConcurrentLinkedDeque或者给 ArrayDeque 加外部锁。如果队列本身能代替栈的话BlockingDeque 的实现类也可以考虑。关键点在于先想清楚你的并发模型再决定容器。无脑使用 Vector 系的老容器通常是历史包袱而不是最佳选择。5.2 ArrayDeque 的循环数组与扩容逻辑ArrayDeque 是很多场景下替代 Stack 的首选但它为什么快因为它内部是一个循环数组。所谓循环数组就是逻辑上的首尾相连当插入位置到达数组末尾时下一次插入会回到数组头部继续插这样头和尾都可以高效地增长。ArrayDeque 默认初始容量为 16扩容时容量翻倍。你如果大概能预估栈的最大规模可以用构造函数提前指定容量DequeInteger stack new ArrayDeque(1024);这能减少扩容次数提升性能。不过有一点要注意ArrayDeque 不允许存放 null 元素。官方明确写了这一点如果业务上确实需要存 null那你只能换 LinkedList 或者自己实现。这是我在一个解析配置文件的功能中踩过的坑——解析结果偶尔为空结果往栈里 push null 直接抛 NPE排查了半天才发现是容器的限制。5.3 栈内元素的拷贝陷阱最后说一个特别容易忽略的问题栈里的元素其实是引用。你在栈里 push 一个对象再修改这个对象的状态栈里的内容也会跟着变。很多人以为“存入栈就安全了”其实只是复制了引用不是复制了对象本体。如果你需要栈中的数据在后续操作中不受原对象影响就得在 push 时做深拷贝或者让对象实现不可变设计。尤其是做撤销重做、历史记录这类场景一份可变对象被反复引用最后可能出现“撤销之后发现历史记录里的数据也变了”的反直觉问题。这个坑在写业务代码时非常典型处理方式没有标准答案但你必须意识到栈只管你的元素进出顺序管不了元素内部的纯度。还有一点当你把一个元素从栈里 pop 出来以后如果这个元素是某个大对象的引用而这个大对象短期内还会被其他数据结构继续引用栈这边及时清空引用反而能帮助 GC 尽快回收。我在第一节手写栈的 pop 方法里强调过 elements[size] null就是这个道理。凡是自己实现容器类都要养成释放引用的习惯。收尾说点我自己的体会写了这么多年 Java我真正直接用到 java.util.Stack 类的次数其实屈指可数但栈的思想几乎每天都出现在我的代码里处理嵌套 JSON 时用栈辅助层级配对、解析 DSL 表达式时用双栈求值、做代码扫描时靠栈来判断块结构是否闭合甚至调 JVM 参数排查递归问题时脑子里想的也全是栈帧的压弹过程。所以我对初学者的建议是不要停留在“栈就是后进先出”这句话上而是亲手写一遍数组栈和链表栈再把括号匹配和表达式求值手推一遍。做完这些你才算真正吃透了 Java 里的栈。数据结构这东西看着是具体类和 API但真正留在脑子里的永远是那套组织数据和控制时序的思路。栈可能是其中最简单的一个但它恰恰是理解递归、理解方法调用、理解一切“先发生的事要后处理”场景的起点。