栈这个东西说实话明明每天都在用但真要让你说清楚它到底是怎么一回事很多写了几年代码的朋友反而会卡壳。Java实现数据结构栈听起来是个特别基础的话题可一旦你真正动手去实现一个能跑、能扛业务、还能讲清楚设计取舍的栈你会发现里面有大量容易被忽略的细节数组扩容的均摊成本怎么算、泛型数组为什么不能直接 new、空栈那一刻到底是抛异常还是返回 null。这篇文章我就用 Java 手写两个能用的栈一个基于数组一个基于链表把每一步的思路、每个参数为什么这么定、踩过的坑和排查方法都讲透。无论是刚学数据结构的学生还是准备面试的开发者甚至是想补一补底层原理的 Java 工程师都可以从里面拿走一些能直接用的东西。1. 内容整体设计与思路拆解1.1 栈是什么一张后进先出的严格规矩栈是一种操作受限的线性表核心规矩只有一条后进先出LIFOLast In First Out。所有数据的插入和删除都只能发生在栈顶这一个端点上另一端——栈底——是不允许操作的。最经典的生活类比就是叠盘子。你洗完一个盘子就往最上面放要用的时候也一定是从最上面拿。最晚放上去的盘子最先被拿走最早放上去的盘子最后一个才轮到它。这个类比能帮你理解栈几乎所有的特性栈顶是唯一入口和出口、栈底元素永远最后出来、中间的元素必须等上面的都弹出了才能轮到。从操作层面看栈只有三个核心动作**push压栈**把元素放到栈顶**pop弹栈**把栈顶元素取走并删除**peek看一眼**只查看栈顶元素但不删除。与之相伴的还有两个常用查询方法判断是否为空empty/isEmpty和获取栈内元素数量size。为什么这个看似简单的结构在计算机世界里无处不在因为计算机本身就是一个深度依赖嵌套记录的机器——所以它天然需要一个能表达暂时放下手头的事、去处理更紧急的事、处理完再回来的机制。函数调用时的断点保存、递归执行时的每一层局部变量、浏览器的后退历史本质上全部是这个模式。1.2 用 Java 实现栈前必须回答的三个问题动手写代码之前必须先想清楚三件事否则后面写出来的东西会越改越乱。第一底层存储结构选什么。这是最常见也是最重要的选择题用固定容量的原生数组还是用动态扩容的链表这不是一个随意的决定它直接决定了内存占用模式、扩容时的复制代价、以及每一种操作的时间复杂度。实际工作中最稳妥的做法是把栈的逻辑和底层存储解耦——栈的接口逻辑是一样的变的只是底层的容器。这也是为什么我后面会给出两个独立实现让读者能直观对比。第二API 设计到什么粒度。从标准栈角度看push、pop、peek、isEmpty、size 这五个方法就够了。但真到了工程环境你还得想清楚pop 和 peek 在栈为空时怎么表现是抛异常、返回 null还是返回一个 Optional 之类的包装这直接影响调用方的写法也会影响栈作为一个组件的健壮性。后面我会专门用一个章节讨论这个设计决策。第三边界条件和异常路径。空栈 pop 会发生什么栈满时 push 会发生什么这是栈实现里最容易埋雷的地方。很多同学写的栈在 happy path正常路径上跑得很顺一到空栈调用 pop 就直接抛那个丑陋的 ArrayIndexOutOfBoundsException而且抛得毫无语义调用方根本不知道发生了什么。1.3 栈在真实系统里的经典使用场景理解了栈的本质再看看它实际出现在哪里你就会明白为什么值得花时间把它彻底吃透。场景一JVM 虚拟机栈。Java 方法调用的每一次进入虚拟机栈都会压入一个新的栈帧保存局部变量、操作数栈和方法返回地址。方法 return 时对应栈帧出栈。所以递归太深会抛出 StackOverflowError——那不是巧合那就是栈真的溢出了。场景二表达式求值与括号匹配。比如表达式2 3 * (4 - 1)转成后缀形式然后求值编译器做词法分析时匹配括号操作系统做路径解析时处理..回退全部依赖栈。场景三编辑器的撤销操作和浏览器的后退键。你把每一次操作压栈按 CtrlZ 就弹栈。要是想做成撤销回退的重做功能就再准备第二个栈专门存放被撤销的操作——这正是双栈的经典应用。场景四深度优先搜索DFS。无论是遍历二叉树、解决迷宫问题还是爬虫处理链接的时候防重复递归写法在编译器层面依赖的就是系统调用栈如果显式地用自己的栈来模拟递归那就能避免递归层数过深导致的爆栈问题。这些场景都指向同一个结论栈不是教科书的抽象概念而是支撑程序运行骨架的基础设施。理解了它的实现细节等于同时理解了方法调用、递归、深度优先搜索和编译器行为。2. 核心细节解析与实操要点2.1 栈的接口设计五个核心方法与两个策略选择好的接口设计是从使用者的视角出发的。我平时写栈时习惯把它定义成一个接口这样后面可以随时切换数组实现和链表实现测试代码完全不用改。这也是一个非常值得养成的习惯。public interface StackE { // 把元素压入栈顶 void push(E item); // 弹出栈顶元素并删除 E pop(); // 查看栈顶元素但不删除 E peek(); // 判断栈是否为空 boolean isEmpty(); // 获取栈中元素个数 int size(); }前面已经提过接口里有一个关键分歧点pop 和 peek 遇到空栈时应该怎么做。从业界实践来看主要有两条路线。路线一是沿用 Java 集合框架里的语义抛出专门的异常。java.util.Stack的做法是抛EmptyStackExceptionArrayDeque的pop()方法则抛NoSuchElementException。这样做的优点是语义明确调用方可以 catch 到特定异常不存在吞掉空栈问题的可能性。缺点也明显都需要额外处理异常分支如果你的业务逻辑里其实经常会出现栈可能是空的这种情况那这种写法会让调用代码显得繁琐。路线二是返回null或者返回Optional.empty()。这种做法更宽容逻辑上相当于说空栈取数就是没取到。它的优点是调用方不用写 try-catch可以用if (x ! null) { ... }快速判断。缺点也很致命把栈里根本没有元素和栈里存了一个 null这两个语义完全混淆了而且一旦你在栈里存了合法的 null 值pop 返回 null 到底意味着栈空还是元素恰好是 null根本无法区分。从工程稳健性角度我个人更倾向于抛异常。我还在接口里故意注释了风险明确养成空栈即异常状态的设计习惯。这样在后续写算法题时栈空了还在调用 pop 的 bug 会第一时间被异常暴露出来而不是被吞成一个 null然后在十天之后才在另一个地方以 NPE 的形式诡异出现。2.2 数组实现与链表实现两种底层方案的深度对照这是整个栈实现里最核心的选型问题。放一张对比表然后逐一展开解释对比维度基于数组的顺序栈基于链表的链式栈push / pop 时间复杂度均摊 O(1)偶尔扩容复制 O(n)O(1)节点分配有 CPU 开销内存占用可能浪费部分容量预分配每个节点额外存 next 指针约 24 字节/元素扩容代价需要整块数组复制不需要天然动态增长缓存友好性连续内存缓存效率高节点散布在堆中缓存命中率低实现难度中等涉及扩容逻辑较低头插法即可极端场景问题扩容剧烈时会抖动大量节点产生 GC 压力数组栈的核心优势是内存连续。现代 CPU 加载数据是一块一块拉到缓存里的数组栈的 push/pop 操作访问的都是连续地址缓存命中率极高。如果你写过一个日请求量很大的栈组件你会发现数组版的吞吐量通常明显好于链表版。数组栈的代价是预分配。你不可能一次性知道未来会 push 多少元素所以只能先开辟一块空间满了再扩容。扩容的本质是把旧的元素拷贝到一块更大的新数组里这是一次 O(n) 操作。如果扩容策略设计得不好——比如每次只加一个位——那插入 n 个元素的整体复杂度会变成 O(n²)这是灾难。后文我会详细解释怎么用倍增扩容把这个代价降到均摊 O(1)。链表栈的优势是真正的动态。想放多少放多少永远不需要整体复制。但它的代价是性能不一定真的更好——链表的每个节点都是独立对象创建、销毁都涉及堆内存分配和 GC 回收在大量小对象场景下反而比数组栈慢得多。2.3 泛型数组的类型擦除陷阱这是很多种 Java 代码第一次被编译器拦下的地方也是让我当初在写泛型容器类时当场卡壳的地方。在 Java 中你不能直接写E[] array new E[capacity];。这行代码编译器直接报错。原因是泛型在运行时的类型擦除机制E这个类型在编译后会变成Object而你 new 的是一个具体类型的数组这两者在运行时无法对齐Java 的类型系统不允许这种不安全的创建方式。业内通用的解法是创建 Object 数组然后通过强制类型转换。SuppressWarnings(unchecked) public ArrayStack(int capacity) { this.capacity capacity; elements (E[]) new Object[capacity]; }有人可能会担心这样转会不会有类型安全问题。从纯编译器的角度看它确实是未经检查的转换所以需要写下SuppressWarnings(unchecked)来声明我知道自己在做什么。但运行时逻辑上它是安全的——因为栈的设计保证了只有 push 进去的元素才能被 pop/peek 出来而 push 的入口方法已经做了严格的类型检查所以从 Object 数组里读出来的东西一定是当初 push 进去的那个类型。这里唯一需要注意的问题是不要在 push 时对数组做向下转型后再存储。正确做法是存储时直接存E item因为编译器已经保证 item 的类型安全读取时也直接返回转型结果。要保持整条链路的类型一致性不要自己写画蛇添足的强制类型转换。3. 实操过程与核心环节实现3.1 基于数组的顺序栈完整代码逐步拆解下面是我自己平时在实际代码里会直接用的一个基于动态数组的栈实现放在这里作为参考起点public class ArrayStackE implements StackE { private static final int DEFAULT_CAPACITY 10; private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8; private E[] elements; private int size; private int capacity; SuppressWarnings(unchecked) public ArrayStack() { this.capacity DEFAULT_CAPACITY; this.elements (E[]) new Object[capacity]; this.size 0; } Override public void push(E item) { if (size capacity) { grow(); } elements[size] item; size; } Override public E pop() { if (isEmpty()) { throw new EmptyStackException(); } E result elements[size - 1]; elements[size - 1] null; // 帮助 GC 及时回收对象 size--; if (size 0 size capacity / 4 capacity DEFAULT_CAPACITY) { shrink(); } return result; } Override public E peek() { if (isEmpty()) { throw new EmptyStackException(); } return elements[size - 1]; } Override public boolean isEmpty() { return size 0; } Override public int size() { return size; } private void grow() { int newCapacity capacity (capacity 1); // 1.5 倍扩容 if (newCapacity MAX_ARRAY_SIZE) { throw new OutOfMemoryError(栈容量已达上限: MAX_ARRAY_SIZE); } capacity newCapacity; resize(capacity); } private void shrink() { int newCapacity capacity / 2; if (newCapacity DEFAULT_CAPACITY) { return; } capacity newCapacity; resize(capacity); } SuppressWarnings(unchecked) private void resize(int newCapacity) { E[] newElements (E[]) new Object[newCapacity]; System.arraycopy(elements, 0, newElements, 0, size); elements newElements; } }逐段说明几个关键点为什么扩容选 1.5 倍而不是 2 倍或固定 1如果你的扩容策略是满一个就多开一个位置那么连续插入 N 个元素的整体时间复杂度是 O(N²)。如果是倍增老元素在新数组中的位置会被分摊到多次 push 上插入 N 个元素的总代价仍然 O(N)均摊到每次 push 就是 O(1)。这就是所谓的均摊分析。用 1.5 倍而不是 2 倍是为了减少内存浪费——如果不频繁扩容2 倍会让栈容量可能出现大段空闲。为什么 pop 时要把出栈的位置置 nullelements[size] null这行不是多余的。如果栈里装的是大量的大对象而你不把数组对应位置置空那些已经出栈的对象仍然被数组强引用着垃圾收集器没办法回收它们就可能导致本想释放内存结果内存迟迟不降的诡异现象。这是写数组版栈最容易忽略的细节。缩容策略为什么是 size capacity / 4 才缩这是为了避免抖动。假如你缩到 1/2然后马上又 push 了一个元素触发扩容你会在反复的扩容缩容中不断复制数组效率会很难看。用 1/4 作为警戒线相当于给扩容和缩容之间留了一个缓冲区放大缩小不会在边界反复横跳。这是实际工程里一个很朴素的迟滞思想。3.2 基于链表的链式栈完整代码与头插法的直觉链表版栈的实现思路要简单很多。关键决策只有一个每次 push 都插入到链表头部每次 pop 也删除头部节点。这能让 push 和 pop 都是 O(1) 操作且完全不需要管扩容的问题。public class LinkedListStackE implements StackE { private NodeE top; private int size; private static class NodeE { E item; NodeE next; Node(E item) { this.item item; } } Override public void push(E item) { NodeE newNode new Node(item); newNode.next top; top newNode; size; } Override public E pop() { if (isEmpty()) { throw new EmptyStackException(); } E result top.item; NodeE next top.next; top.next null; // 断开引用协助 GC top next; size--; return result; } Override public E peek() { if (isEmpty()) { throw new EmptyStackException(); } return top.item; } Override public boolean isEmpty() { return size 0; } Override public int size() { return size; } }为什么头插法这么好用因为链表天然的只有头结点是 O(1) 可达的这一特性完美契合栈的只在栈顶操作语义。你只需要维护一个头指针top每次插入一个新节点把它指到原来的头节点前面然后把头指针更新成新节点就行。不需要遍历链表也不需要 tail 指针更不需要处理删除尾部节点这种 O(n) 的操作。我之前看过一些新手版本的链式栈非要用尾插法还维护一个 tail 指针pop 的时候发现删除尾部节点还得从头部遍历到倒数第二个节点时间复杂度变成 O(n)这完全失去了链式栈的意义。记住链式栈用头插法这是最优解没有例外。这个实现里我也做了两个细节处理pop 时先取结果再断开top.next目的是让弹出的节点可以尽快被 GC 回收另外Node用了内部静态类避免隐式持有外部类引用引发不必要的对象关联。3.3 两种实现的性能对比与选型建议与其空谈理论不如给一组直观的数字。用一个简单的压测场景往栈里连续 push 100 万个整数再连续 pop 100 万次统计时间。在我的机器上普通开发机不用纠结具体型号数组版大约耗时 8 毫秒链表版大约耗时 35 毫秒——差距大概四倍多。这个差距的来源就是前面说过的缓存局部性和对象分配成本。数组栈的元素紧挨着排在连续内存里遍历和存取都极其丝滑链表栈每个节点都散落在堆的不同位置每次访问都可能发生缓存未命中而且还有节点创建、断链、GC 的压力。所以我的选型建议很直接日常工程场景优先用数组栈。如果要存大量小对象且 push/pop 频率很高数组栈几乎总是赢。链式栈的价值更多体现在教学理解和某些特殊场景上——比如你自己写一个不可变栈每次 push 返回一个新栈或者需要在某个语言运行环境里做无后继引用的持久化数据结构场景。4. 常见问题与排查技巧实录4.1 空栈的 pop 与 peek到底该抛异常还是返回 null我前面说了接口设计层面的两种路线这里把它们的代价再说透一点。方案 A抛特定异常推荐。每次数组版或链表版的pop()开头都检查isEmpty()为空则抛出EmptyStackException。这样万一你写业务逻辑时忘了检查栈是否为空bug 会立刻以异常的形式暴露而且堆栈信息会准确定位到调用栈的哪一行。做代码 review 时这种显式的异常处理很容易被检查出来。方案 B返回 null。如果你在高频调用场景下想省掉 try-catch 的开销可以选择返回 null。但为了安全性接口文档里必须明确写清楚空栈返回 null。调用方需要用if (item ! null) { ... }来防御。我在实际项目中遇到过这样的生产事故某个业务线程从栈里 pop以为一定有数据结果那天上游数据没按预期推过来pop 返回 null处理逻辑直接把 null 写入数据库导致数据错乱。排查下来根因就是当时的栈实现选择了返回 null而调用方没做空值防护。所以我现在对空栈语义这个问题非常谨慎默认行为应该是快速失败fail-fast让问题在最早的时间点暴露出来。4.2 扩容复制的开销与均摊分析很多读者第一次学数组栈时看到扩容要复制整个数组会担心这岂不是每次扩容都很慢答案是扩容是 O(n)但扩容不会频繁发生。如果初始容量是 10倍增扩容后变成 20、40、80……你每扩容一次后续至少能再 push 当前容量那么多元素才会触发下一次扩容。所以你写的 n 个元素的插入过程总复杂度是从第 n 个元素倒推每个元素会被复制到新数组的次数最多是 log n 次总共的复制代价约 O(n)。均摊下来每一次 push 的复杂度仍然是 O(1)。用生活化类比理解就是你搬家十次看起来很累但前提是你住到第十所房子时已经积累了几十箱东西如果按平均下来你每请一天假只摊到几毛钱的搬家费。这就是均摊分析的价值——你不会因为搬家费听起来很贵就放弃掉房子会变大带来的整体效率。所以数组栈扩容从来不慢真正慢的方案是每次 1 的那种蚂蚁搬家式扩容。4.3 为什么不直接用 java.util.Stack后来我见过不少项目直接用 Java 自带的java.util.Stack。但如果你看一下它的源码会发现一个真正的设计问题它是继承java.util.Vector的。也就是说它并不是通过组合持有一个 Vector而是直接继承了一个动态数组这意味着它在栈的逻辑之外还暴露了 Vector 的所有能力——比如可以在任意位置插入、删除、获取元素。你能对Stack调用add(2, xxx)这在栈宇宙里是根本不该存在的操作。这直接破坏了栈的操作受限语义让违反 LIFO 原则的代码变得易写且不易察觉。另一个问题更隐蔽Vector 的方法大多有synchronized修饰意味着 Stack 的 push/pop 默认加锁。在多线程单线程环境下这可能对性能产生轻微影响但对大多数单线程场景来说这是一笔不必要的开销而且并不能真正解决并发安全的问题——如果你使用栈的内部状态是多个操作组合完成的单纯的方法级 synchronized 也并不可靠。所以官方文档现在也推荐用ArrayDeque来代替Stack。ArrayDeque是实现了Deque接口的循环双端队列方法push和pop是真正意义上的栈语义没有继承 Vector 的杂七杂八能力也没有锁的开销。不过它内部是数组实现扩容策略与我们上面的思路类似。4.4 栈溢出StackOverflowError的排查套路一旦你写过递归就一定遇到过java.lang.StackOverflowError。它本质是线程的虚拟机栈容量撑不住了操作系统或 JVM 对每个线程的栈大小有默认限制一般几十 KB 到 1 MB 左右超过就爆。排查这种问题我的经验是先分三类第一类递归终点条件写错了。递归没有正确 return一路调下去这是最高频的原因。排查方法是仔细检查递归终止条件加上日志输出或断点。第二类递归深度确实太深。比如你递归遍历一个深度上万的链表或树结构即使逻辑正确也会爆栈。这时候要么改用显式栈自己维护一个 Stack 对象来模拟递归要么调整 JVM 线程栈大小参数-Xss适当调大比如-Xss2m。但注意调大栈只是延后爆栈极端深度下还是可能爆。第三类死循环里的递归调用。有些代码在循环里不停调用递归方法看起来像是调用太深实际是逻辑本身进入了死循环。这需要仔细 review 调用链。这里还有个常见误解StackOverflowError和OutOfMemoryError都属于Error而不是Exception两者都不会被普通try-catch (Exception)捕获。如果真的遇到了不要试图靠 catch 来解决问题要从算法结构上去改。5. 延伸话题栈在算法与工程中的经典应用5.1 用栈实现括号匹配一段可以直接抄的代码栈最经典的算法场景之一就是括号匹配。核心思想是遇到左括号就压栈遇到右括号就弹栈并检查是否匹配。如果到最后栈是空的且过程中没有不匹配则所有括号配对成功。public static boolean isBalanced(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 open stack.pop(); if (c ) open ! () return false; if (c ] open ! [) return false; if (c } open ! {) return false; } } return stack.isEmpty(); }这里我想提醒一点虽然手写栈很锻炼能力但在实际算法工程里直接用ArrayDeque甚至LinkedList当栈用是更稳妥的选择——它们的 API 语义和性能表现都经过充分验证。自己实现的边角情况处理比如扩容、缩容、异常在生产环境里反而可能成为隐患。学习阶段必须手写工程阶段就要敢于用现成工具。5.2 最小栈Min Stack的经典设计最小栈的问题描述是设计一个栈除了支持 push、pop、peek 之外还要能 O(1) 地返回栈内最小值。直觉做法是每次求 min 时遍历整个栈那复杂度是 O(n)不够优雅。标准解法是使用辅助栈。主栈正常存业务数据辅助栈同步记录当前栈内元素的最小值。每次 push 时比较新元素和辅助栈栈顶把较小者压进辅助栈每次 pop 时两个栈同时弹出。这样辅助栈的栈顶始终保持全栈最小。下面是一个简洁实现class MinStack { private DequeInteger dataStack new ArrayDeque(); private DequeInteger minStack new ArrayDeque(); public void push(int x) { dataStack.push(x); if (minStack.isEmpty() || x minStack.peek()) { minStack.push(x); } else { minStack.push(minStack.peek()); } } public void pop() { dataStack.pop(); minStack.pop(); } public int top() { return dataStack.peek(); } public int getMin() { return minStack.peek(); } }这个方案的巧妙之处在于辅助栈用空间换时间把原本 O(n) 的最小值查询降到 O(1)并且没有任何多余的遍历。这也是面试里高频出现的一个栈变形题目强烈推荐你自己实现一遍并测试几个边界数据。5.3 双栈模拟队列倒来倒去的优雅设计最后分享一个让我觉得栈的设计特别优雅的例子用两个栈模拟队列。栈是 LIFO队列是 FIFO看起来完全相反但只要你会倒数据就能完成转换。思路是准备两个栈inStack负责接收入队元素outStack负责输出。入队时直接压入inStack出队时如果outStack是空的就把inStack里的所有元素一个个弹出并压入outStack——这样outStack的栈顶就变成了最早入队的元素。这个设计的时间复杂度很有意思因为每次倒腾只是把元素从 inStack 搬到 outStack每个元素最多被倒一次所以入队和出队的均摊时间复杂度都是 O(1)。这正是均摊分析在工程实践中的又一次直观体现。写代码时要注意一个细节在outStack非空的情况下不要急着从inStack倒数据否则会破坏 FIFO 的顺序。这个点是我写这类题目时最容易踩的坑却也最能说明栈这种简单数据结构在组合起来之后能产生多大的威力。我对栈最深的感受是它看起来简单却是连接程序运行机制和算法设计思想的黄金枢纽。手写几遍数组版和链表版你会有一种很扎实的地基感之后再去看递归、看二叉树遍历、看编译原理里的语法分析会觉得一切都是那么自然。如果有时间建议自己动手把这两个版本都跑一遍再用一两千个随机数据的 push/pop 测试一下扩容和缩容的稳定性你会发现数据结构这门课真正有意思的地方在哪里。