企业官网建设流程全解析

Java实现数据结构栈这个题看着基础，但真正动手写之前，我建议先想清楚一件事：你要的是一个能跑的Demo，还是一个能够放进生产代码里的栈结构。很多初学者写完就丢，结果在真正的项目里一用就出问题，原因往往不是“栈”这个概念没搞懂，而是细节处理不到位。这篇文章不是抄一遍教科书，而是把我自己实现栈时踩过的一些坑、反复权衡过的设计点，以及最后沉淀下来的可复用写法，一块儿整理出来。适合正在学数据结构的Java初学者，也适合需要快速封装一个栈组件却不想重复造轮子的人。

1. 什么是栈：先别急着写代码，把“后进先出”刻进脑子里

1.1 生活化的比喻

栈的行为一句话就能概括：后进先出（LIFO，Last In First Out）。理解它最直接的场景是叠盘子，你最后放上去的那个盘子，永远是下一次最先拿走的那个。如果你非要拿最底下的盘子，就得先把上面所有盘子都搬走，这显然不合理。所以栈这种结构天然适合“最近优先”的场景，最新的数据最先被处理。

另一个我经常用的比喻是浏览器返回键。你访问页面A、B、C，浏览器记录访问顺序，点“后退”时先回到B，再回到C（应该是再回A）。等等，实际浏览器也不是纯栈，这比喻只是帮助理解。更准确的比喻是文本编辑器里的Undo，你最后一次输入的操作，永远排在撤销列表的最上面，点一下撤销，最先被回退的就是它。

1.2 栈的核心操作与接口设计

一个栈对外暴露的核心操作，说白了就四个：

• push：把元素压栈，也就是放进栈顶。
• pop：把栈顶元素弹出，取出的同时从栈中移除。
• peek：看一眼栈顶元素，但是不移除。
• isEmpty：判断栈是不是空的。

很多人还会关心 size 或者 getDepth，用来知道栈里还剩多少个元素。还有一个稳态要求：栈满时能不能继续push？这取决于你实现的是固定容量的栈还是动态扩容的栈。

设计接口时我建议直接定义成一个接口，而不是一开始就定死实现。我自己是这么写的：

public interface Stack<T> { void push(T item); T pop(); T peek(); boolean isEmpty(); int size(); }

有人喜欢用push返回 boolean 表示是否成功，但我觉得既然是栈，push 失败属于异常情况，直接抛异常比返回 false 更明确。后面我会详细说异常怎么设计。

1.3 为什么要在 Java 里自己实现栈

Java 本身已经提供了java.util.Stack，也有ArrayDeque这种双端队列可以用。那自己实现一遍到底图什么？我个人的答案非常务实：为了搞懂底层逻辑，为了能做出符合业务约束的定制栈。

java.util.Stack本身存在一些历史包袱，它继承了Vector，所有方法都带同步锁，在单线程场景下性能白白损耗。而且它直接暴露了search、elementAt这类不属于栈语义的方法，容易引发误用。ArrayDeque虽然官方推荐用来当栈，但它的迭代方向、扩容策略对你来说是个黑盒。如果你只是调包，那当然没问题；可一旦你需要“栈容量上限”“监控栈深度”“统计 push 次数”这些定制能力，自己实现就是最干净的办法。

2. 两种主流实现：数组栈与链表栈的取舍

2.1 数组实现的思路与完整代码

数组栈的核心思路：使用一个 Object 数组作为底层存储，用一个 int 变量记录栈内元素个数，也就是栈顶位置的下一个索引。push 时把元素写到size位置，然后 size 加一；pop 时 size 先减一，再把该位置元素返回，最后把数组里的引用置空。

为什么 pop 之后要把引用置空？这问题我在第三次写栈时才真正想明白。如果数组某位置还持有不再需要的对象引用，JVM 的垃圾回收就认为对象仍然存活，无法回收它。网上很多教学代码没有这一步，短时间跑没问题，长时间运行就会内存泄漏。

完整可用的数组栈我这样写：

public class ArrayStack<T> implements Stack<T> { private Object[] elements; private int size; private static final int DEFAULT_CAPACITY = 10; public ArrayStack() { this(DEFAULT_CAPACITY); } public ArrayStack(int initialCapacity) { if (initialCapacity <= 0) { throw new IllegalArgumentException("初始容量必须大于0"); } elements = new Object[initialCapacity]; } @Override public void push(T item) { if (size == elements.length) { grow(); } elements[size++] = item; } @Override public T pop() { if (isEmpty()) { throw new IllegalStateException("栈为空，不能弹出元素"); } T result = (T) elements[--size]; elements[size] = null; return result; } @Override public T peek() { if (isEmpty()) { throw new IllegalStateException("栈为空，不能查看栈顶"); } return (T) elements[size - 1]; } @Override public boolean isEmpty() { return size == 0; } @Override public int size() { return size; } private void grow() { int oldCapacity = elements.length; int newCapacity = oldCapacity + (oldCapacity >> 1); elements = Arrays.copyOf(elements, newCapacity); } }

这里扩容我用了一个很常见的策略：每次扩容到原来的 1.5 倍。为什么不是 2 倍？因为扩容本身是耗时的，1.5 倍比 2 倍更节省内存，又比“加固定数量”这种策略减少扩容次数。实际项目中确实有人纠结这个，我的看法是：如果栈元素数量在几万量级，1.5 倍和 2 倍差别不大；但如果是长期运行的服务，1.5 倍更稳。

2.2 链表实现的思路与完整代码

链表栈的思路更简单：每个节点保存数据和下一个节点的引用。push 时新建节点，让新节点指向旧的栈顶节点，然后更新栈顶指针。pop 时把栈顶节点的 data 取出来，栈顶指针指向它的 next。

链表栈的优点是永远不会“溢出”（除非内存真的不够了），扩容逻辑天然不存在。缺点是每个节点都要存一个 next 引用，内存开销比数组大，而且访问缓存不友好，数据在内存中不是连续存储的。

完整写法：

public class LinkedStack<T> implements Stack<T> { private Node<T> top; private int size; private static class Node<T> { T data; Node<T> next; Node(T data, Node<T> next) { this.data = data; this.next = next; } } @Override public void push(T item) { Node<T> newNode = new Node<>(item, top); top = newNode; size++; } @Override public T pop() { if (isEmpty()) { throw new IllegalStateException("栈为空，不能弹出元素"); } T data = top.data; // 防止“游离”节点继续引用旧数据 top.data = null; top = top.next; size--; return data; } @Override public T peek() { if (isEmpty()) { throw new IllegalStateException("栈为空，不能查看栈顶"); } return top.data; } @Override public boolean isEmpty() { return top == null; } @Override public int size() { return size; } }

注意pop里我把top.data置为 null 了。这一步和数组栈里elements[size] = null是同一个道理：帮助 GC，避免旧对象因这个节点的引用而无法回收。

2.3 复杂度对比与选型建议

两种实现在时间复杂度上，核心操作都是 O(1)，这可能是很多人觉得“随便选一个就行”的原因。但实际工程里不能只盯着时间复杂度，还要看内存布局和使用场景。

我的选型建议非常直接：默认用数组栈。除非你明确知道栈元素数量波动极大、提前无法预估，而且每个元素都是大对象，才考虑链表栈。数组栈的连续内存访问在现代 CPU 上非常占便宜，性能实测比链表栈整段操作要快不少。特别是有遍历栈需求时，数组栈直接按索引访问，链表栈却要一个一个 next 跳，差距很大。

3. 实操细节：扩容策略、泛型、异常设计

3.1 动态扩容怎么做才不掉链子

数组栈的扩容是我最想强调的细节。初学时我也写过“每次 push 都新建一个更大的数组并复制所有旧元素”的版本，结果帮别人写一个性能测试时，几十万元素的压栈操作直接把耗时拉爆。问题就在于扩容频率太高。

好的策略是“倍增扩容”。最简单的倍增是newCapacity = oldCapacity * 2，我上面的代码用的是oldCapacity + (oldCapacity >> 1)，也就是 1.5 倍。这里>> 1是右移一位，相当于除以2，所以结果就是原来容量加一半。为什么用位运算？不是炫技，是让代码更贴合底层运算习惯，读起来也简洁。

扩容时机有两个坑。第一个是初始化容量设为 0，然后第一次 push 时size == elements.length成立，去扩容，结果是 0 位移还是 0 还是 0，直接死循环。所以要么初始容量至少为1，要么在 grow 里判断oldCapacity为 0 时给一个默认值。第二个坑是扩容后要Arrays.copyOf而不是System.arraycopy后手动 new 数组，前者内部帮你处理了类型转换和赋值。

实际操作时，我通常会额外提供一个trimToSize方法，把数组容量压缩到实际元素个数。因为栈作为工具类往往长期存活，如果曾经巅峰时存了几十万个元素，后面只剩几个元素，那大部分内存就白白占着。有这方法，在业务低峰期手动调用一下，内存压力马上降下来。

3.2 泛型与 null 值处理

Java 泛型在数组创建上有著名的限制：new T[DEFAULT_CAPACITY]根本编译不过。原因是泛型在运行时会被类型擦除，JVM 不知道 T 到底是什么类型，不能确定数组元素的实际类型。所以我用Object[]作为存储，push 时放入，pop 和 peek 时强转回 T。

强转的地方会产生 unchecked 警告，这是不可避免的。但要注意：只要你保证只往数组里放 T 类型的对象，强转就是安全的。不要在代码里把elements[size++] = item写错成elements[size] = item，因为你需要先用 size 作为索引，再自增。前者会出现“数组索引等于当前元素个数，写入后 size 已加1”的微妙区别。我写错过一次，结果 push 一个元素后 size 变成 2，实际数组下标0被写入，下标1还是 null，一 pop 就出空指针。

null 值要不要允许入栈？这是个设计选择。有些业务把 null 当作有效数据，有些则不允许。我个人建议在 push 时明确拒绝 null，原因是 pop 方法里我用result == null做状态判断很容易误伤。来看这段代码：

public T pop() { if (size == 0) { throw new IllegalStateException("栈为空"); } T result = (T) elements[--size]; elements[size] = null; return result; }

如果允许 null 入栈，那么当你真的放入了 null，pop 返回的也是 null，调用方无法区分“栈空”与“栈顶是 null”。为了避免这种歧义，我会在 push 开头加一句：

if (item == null) { throw new IllegalArgumentException("栈不支持null元素"); }

3.3 自定义异常还是用官方异常

刚开始写栈，很多人不知道异常该怎么抛。Java 自带了一个java.util.EmptyStackException，但它的父类是 RuntimeException，没有无参构造之外的更多信息。我试过在主业务代码里 catch 它，调试时完全看不出是哪一步弹出的空栈，非常难受。

后来我改成直接抛IllegalStateException，并带一句描述，比如“栈为空，不能弹出元素”。这样日志里能直接看到原因。如果你需要更细致的语义，比如“容量不足”和“非法参数”，可以自定义异常类，但绝大多数项目没必要为了一个栈写三个异常类。保持简单：push 传 null 抛 IllegalArgumentException，pop/peek 空栈抛 IllegalStateException，初始容量非法抛 IllegalArgumentException，就够了。

提示：如果你把这个栈用在多线程环境，不要直接给每个方法加 synchronized。更好的选择是让这个类保持非线程安全，在需要并发的地方用ConcurrentLinkedDeque或者外部加锁。Stack 当年就是因为所有方法都锁了，单线程性能才那么差。

4. 常见问题与排错实录

4.1 第1坑：容量判断和栈顶指针的边界

写数组栈最容易翻车的就是边界判断。我有一个经典的出错版本：

public T pop() { T result = (T) elements[size - 1]; size--; ... }

这个写法在栈里只有一个元素时看起来没问题，因为 size - 1 = 0，弹出后 size 变成 0，下一次 pop 时 size - 1 = -1，直接数组越界。排查起来最隐蔽的是：它不是立刻崩溃，而是先正常跑几次，等到第二次乱操作时才炸。

我建议的思考方式：始终让 size 代表“数组里下一个空位的位置”，而不是“栈顶元素的位置”。栈顶元素索引永远是 size - 1。这样 push 用elements[size++] = item，pop 用elements[--size]，不容易乱。写完后建议立刻测试这几个边界：空栈 pop 抛异常、压一个再弹、栈满扩容后继续压、弹到空再弹。

4.2 第2坑：pop 之后没有置空导致内存泄漏

我一次帮同事排查一个内存缓慢上涨的服务，定位到的是一个手写栈。那个栈的 pop 方法只做了size--，没有把elements[size]置空。数组里元素引用还留着，GC 无法回收它们。当时那栈里存的是带大图片的缓存对象，导致整个服务内存居高不下。

这不是危言耸听。只要你的栈存活时间足够长，pop 出来的对象又已经不被业务引用，那它就成了“隐形的强引用”。所以不管数组栈还是链表栈，pop 后置空引用这一步都不能省。数组栈是elements[size] = null，链表栈是置空top.data，原理一模一样。

4.3 第3坑：迭代器写错导致遍历顺序混乱

栈的遍历通常不需要，但如果你要实现Iterable<T>，就会遇到一个有意思的问题：从栈底到栈顶还是从栈顶到栈底？栈的语义是“顶”在最外面，可如果把它当列表用，你希望按什么顺序打印？

我见过的一个错误写法是直接在迭代器里用for (int i = 0; i < size; i++)，正好是栈底到栈顶，但用户预期往往是先看到栈顶。最后我在实现时采用了从栈顶到栈底的顺序，并且为了不动原始栈，迭代器里保存一份数组快照：

@Override public Iterator<T> iterator() { Object[] snapshot = Arrays.copyOf(elements, size); return new Iterator<T>() { private int index = snapshot.length - 1; @Override public boolean hasNext() { return index >= 0; } @Override public T next() { if (!hasNext()) { throw new NoSuchElementException(); } return (T) snapshot[index--]; } }; }

这里有两个细节。第一，必须Arrays.copyOf(elements, size)而不是Arrays.copyOf(elements, elements.length)，否则会把后面已经置空的槽也复制进去，遍历时出现 null。第二，用快照而不是直接用原数组，是为了防止迭代过程中有 push/pop 导致数据错乱，算是防御性编程。

4.4 问题速查表

我把上述问题和排查要点整理成一张表，方便遇到症状时快速定位：

如果你自己写了一个栈，建议写完立刻把这张表里的场景测一遍。很多问题不是逻辑写不出来，而是错得毫无征兆，等业务跑起来才暴露。单元测试能帮你把这些问题拦在发布之前。

5. 实际应用：栈在哪些地方悄悄工作

5.1 括号匹配与表达式求值

栈最经典的算法题就是括号匹配。比如给你一串( [ { } ] )，要判断是否合法。思路非常简单：遇到左括号就入栈，遇到右括号就弹出栈顶，检查是否配对。如果中途遇到空栈，说明右括号多余；如果遍历结束后栈非空，说明左括号多余。

我简单写一个示意：

public static boolean isValid(String s) { Stack<Character> stack = new ArrayStack<>(); Map<Character, Character> pairs = Map.of( ')', '(', ']', '[', '}', '{' ); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { if (stack.isEmpty()) { return false; } char top = stack.pop(); if (top != pairs.get(c)) { return false; } } } return stack.isEmpty(); }

表达式求值比如3 + 4 * 2也是栈的典型应用。中缀表达式转后缀表达式，用栈保存运算符；后缀表达式求值，用栈保存操作数。你把这两个过程写一遍，对“栈保存临时状态”的理解会立刻上一个台阶。

5.2 函数调用与递归

线程的调用栈本质上就是一个栈结构。每次调用一个方法，JVM 会把当前方法的局部变量、返回地址等信息压入线程栈；方法返回时，再从栈顶弹出。这也是为什么递归写太深会抛StackOverflowError，因为线程栈容量是有限的，不断入栈不弹栈，最终把栈空间耗尽。

如果你自己实现过栈，再去看调用栈的报错信息，会特别亲切。压栈和弹栈并不总是成对出现，一旦某个路径上漏了弹栈，栈帧越叠越高，迟早溢出。所以递归里尤其要注意终止条件，就像栈里需要一个可靠的 isEmpty 判断一样。

5.3 撤销操作与浏览器历史

实际业务里，很多“撤销”功能就是用一个栈保存历史状态。我做过一个批量编辑工具，每步修改前，把“修改前的数据”压入一个操作栈。用户点撤销，就从栈顶弹出上一次的旧状态，恢复到界面。如果用户撤销后做了新操作，就要清空重做栈，否则重做历史会和当前分支冲突。这个“双栈”模型很常用：一个栈管撤销，另一个栈管重做。

浏览器历史也是类似逻辑（当然真实浏览器会用更多优化）。每次访问新页面，把当前页面压栈；点后退，从栈里弹出上一个页面。注意“后退之后去了新页面”会清空前方历史，因为它背后的栈已经把那条分支弹出了，回不去了。

最后聊点我的个人习惯

每次写栈，我都会先在纸上画一遍 push/pop 的指针变化，尤其是数组栈里 size 到底代表什么。画完再动手，写出来的代码基本不会出边界问题。另一个习惯是测试完边界后，顺手压几万个元素跑一下，看看扩容是否正常、内存是否有异常上涨。栈这东西越底层，越容易被人忽视，可它一崩，整个程序都会被拖下水。真的用起来的时候，多想想你当初实现它时对边界和内存的处理，会少踩很多坑。