跳至主要內容

为什么Java官方不推荐用Stack：Deque才是正确选择

老张2026/4/30大约 8 分钟

为什么Java官方不推荐用Stack：Deque才是正确选择

适读人群：Java初中级开发者 | 阅读时长：约12分钟 | 文章类型：源码分析+最佳实践

开篇故事

有天Code Review，看到一个刚入职的新人小周，用Stack实现了一个括号匹配算法：

Stack<Character> stack = new Stack<>();

我指着这行代码说：这里改成Deque<Character> stack = new ArrayDeque<>()。

小周看了看，说：功能是一样的吧？

我说：功能一样，但Stack有历史遗留问题，Java官方Javadoc里都写了：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.

他看了看Java文档，确实有这句话。然后他问：那Stack哪里不好？

这个问题问得好。Stack的问题不是功能缺失，而是设计缺陷——它继承了Vector，而Vector是一个全方法同步的线程安全列表，给栈带来了不必要的开销和错误的API。

今天我们把这段历史说清楚，顺带把Deque的源码摸透。

一、Stack的历史遗留问题

1.1 Stack继承Vector，暴露了不应该有的方法

// JDK的Stack继承关系：
// Stack -> Vector -> AbstractList -> AbstractCollection

// 问题：Stack继承了Vector的所有public方法
// 一个栈只应该有push/pop/peek三个操作
// 但Stack能这么用（违反栈语义！）：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

// 这些操作在语义上不应该属于栈：
stack.add(0, 99);    // 在下标0处插入！破坏LIFO顺序
stack.remove(1);     // 删除下标1的元素！
stack.get(0);        // 随机访问底部元素！
stack.set(0, 100);   // 修改底部元素！

// 这些操作语义上是对的，但Stack没有正确实现接口规范
System.out.println(stack); // [99, 100, 2, 3]  乱了

这就是API设计的大忌：子类暴露了父类所有方法，打破了封装。一个栈，不应该支持随机插入和删除。

1.2 Vector的全局锁：不必要的同步开销

// Vector的所有public方法都是synchronized（JDK1.0时代的历史遗留）
// Stack继承Vector，所以Stack的push/pop/peek也全是synchronized
// 在单线程场景下，这些锁毫无意义，只是徒增开销

// JDK1.0时代（1996年），多线程还是稀奇玩意儿，
// 当时的设计者认为"所有集合类都线程安全"是个好主意
// 这个决定后来被证明是错的，所以JDK1.2引入了Collections框架重新设计

// 据我测试（JDK17，单线程，100万次push/pop）：
// Stack: 约85ms（有synchronized开销）
// ArrayDeque: 约15ms（无锁）
// 差距约5.7倍

二、Deque的设计与ArrayDeque源码

Deque（Double-Ended Queue，双端队列）接口同时支持栈和队列两种操作，设计非常精妙：

  • 用作栈：push(e) / pop() / peek()（操作头部）
  • 用作队列：offer(e) / poll() / peek()（尾部入，头部出）

2.1 ArrayDeque的循环数组实现

package com.laozhang.deque;

import java.util.Arrays;

/**
 * ArrayDeque核心原理实现（参考JDK11源码）
 *
 * 底层：循环数组（Circular Array）
 * 关键：head和tail指针，head指向队列第一个元素，tail指向下一个要插入的位置
 *
 * 插入复杂度：均摊O(1)（扩容时O(n)，但均摊O(1)）
 * 随机访问：不支持（这是设计上的主动限制，保证API纯洁性）
 */
public class CircularArrayDequeImpl<E> {

    private Object[] elements;
    private int head; // 第一个元素的下标
    private int tail; // 下一个将要插入的下标（tail位置本身为空）

    private static final int MIN_INITIAL_CAPACITY = 8;

    public CircularArrayDequeImpl() {
        elements = new Object[16]; // 默认16，必须是2的幂（方便位运算取模）
    }

    /**
     * 头部插入（push操作）
     * 循环数组：head向前移动一步，用 & (length-1) 实现循环
     *
     * 为什么用 & (length-1) 而不是 % length？
     * 位运算比模运算快（约10倍），而且length是2的幂，保证结果等价
     */
    public void addFirst(E e) {
        if (e == null) throw new NullPointerException();
        // head向前移动一步（循环，越过0就到length-1）
        head = (head - 1) & (elements.length - 1);
        elements[head] = e;
        if (head == tail) // 如果head和tail相遇，说明数组满了
            doubleCapacity();
    }

    /**
     * 尾部插入（offer操作）
     * tail向后移动一步
     */
    public void addLast(E e) {
        if (e == null) throw new NullPointerException();
        elements[tail] = e;
        // tail向后移动一步（循环）
        if ((tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity(); // 满了就扩容
    }

    /**
     * 头部删除（pop/poll操作）
     */
    @SuppressWarnings("unchecked")
    public E removeFirst() {
        int h = head;
        E result = (E) elements[h];
        if (result == null) return null; // 空队列
        elements[h] = null; // 清空（帮助GC）
        head = (h + 1) & (elements.length - 1); // head前进
        return result;
    }

    /**
     * 扩容：容量翻倍
     * 把循环数组"展开"到新数组的前面
     */
    private void doubleCapacity() {
        int p = head;
        int n = elements.length;
        int r = n - p; // 从head到数组末尾的元素数量

        int newCapacity = n << 1; // 容量翻倍
        if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big");

        Object[] a = new Object[newCapacity];
        // 分两段复制：head到末尾，0到tail
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);

        elements = a;
        head = 0;
        tail = n; // 所有元素都在[0, n)
    }

    /**
     * 查看头部元素（不删除）
     */
    @SuppressWarnings("unchecked")
    public E peekFirst() {
        return (E) elements[head];
    }

    public int size() {
        return (tail - head) & (elements.length - 1);
    }

    public boolean isEmpty() {
        return head == tail;
    }
}

2.2 用ArrayDeque实现栈和队列的标准写法

package com.laozhang.deque;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * ArrayDeque作为栈和队列的完整使用示例
 * 这是Java官方推荐的做法，替代Stack和LinkedList<Queue>
 */
public class DequeUsageDemo {

    /**
     * ArrayDeque用作栈：括号匹配算法
     * 这是LeetCode 20题的Java最佳实现
     */
    public static boolean isValidParentheses(String s) {
        // 官方推荐：Deque<Character> stack = new ArrayDeque<>()
        // 不要用：Stack<Character> stack = new Stack<>()
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c); // 等价于 addFirst(c)，入栈
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop(); // 等价于 removeFirst()，出栈
                if (c == ')' && top != '(') return false;
                if (c == ']' && top != '[') return false;
                if (c == '}' && top != '{') return false;
            }
        }
        return stack.isEmpty();
    }

    /**
     * ArrayDeque用作队列：BFS层序遍历
     * 队列操作：offer（尾部入）/ poll（头部出）
     */
    public static void bfsExample() {
        // 模拟二叉树的BFS
        Deque<Integer> queue = new ArrayDeque<>();

        // 模拟树节点（用数字代替）
        queue.offer(1);  // 根节点入队（等价于addLast）

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 出队（等价于removeFirst）
            System.out.print(node + " ");

            // 把左右子节点入队
            if (node * 2 <= 7) queue.offer(node * 2);
            if (node * 2 + 1 <= 7) queue.offer(node * 2 + 1);
        }
        // 输出：1 2 3 4 5 6 7
    }

    /**
     * ArrayDeque的性能基准（与Stack对比）
     */
    public static void performanceBenchmark() {
        int N = 1_000_000;

        // Stack（有synchronized开销）
        java.util.Stack<Integer> stack = new java.util.Stack<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) stack.push(i);
        for (int i = 0; i < N; i++) stack.pop();
        System.out.println("Stack push+pop 100万次: " +
            (System.currentTimeMillis() - start) + "ms");
        // 据我测试JDK17：约85ms

        // ArrayDeque（无锁）
        Deque<Integer> deque = new ArrayDeque<>(N);
        start = System.currentTimeMillis();
        for (int i = 0; i < N; i++) deque.push(i);
        for (int i = 0; i < N; i++) deque.pop();
        System.out.println("ArrayDeque push+pop 100万次: " +
            (System.currentTimeMillis() - start) + "ms");
        // 据我测试JDK17：约15ms，约5.7倍性能差距
    }

    public static void main(String[] args) {
        System.out.println("括号匹配 '()[]{}': " + isValidParentheses("()[]{}"));
        System.out.println("括号匹配 '([)]': " + isValidParentheses("([)]"));
        System.out.print("BFS遍历: ");
        bfsExample();
        System.out.println();
        performanceBenchmark();
    }
}

四、踩坑实录

坑1：Stack的peek()在空栈时抛EmptyStackException，而ArrayDeque返回null

报错现象：把代码从Stack迁移到Deque，在空队列上调用peek()，行为变了：Stack.peek()抛异常，ArrayDeque.peekFirst()返回null。

根本原因：Deque的方法分两套：

  • 抛异常版：addFirst/removeFirst/peekFirst、push/pop
  • 返回null版：offerFirst/pollFirst/peekFirst、offer/poll/peek

注意：peekFirst()返回null（不抛异常），removeFirst()抛异常，pollFirst()返回null。

具体解法：

Deque<Integer> deque = new ArrayDeque<>();

// 迁移时的对应关系：
// Stack.push(e) -> deque.push(e) 或 deque.addFirst(e)
// Stack.pop()   -> deque.pop()（空时抛NoSuchElementException）
//               或 deque.pollFirst()（空时返回null）
// Stack.peek()  -> deque.peek()（空时返回null！不是抛异常）
//               注意：Stack.peek()空时抛EmptyStackException，行为不同！

// 安全的peek写法：
Integer top = deque.isEmpty() ? null : deque.peek();

坑2：用LinkedList作为Queue，以为和ArrayDeque一样高效

报错现象：用LinkedList实现的消息队列，GC日志里Minor GC频率非常高，触发Full GC。

根本原因：每次offer都要创建LinkedList.Node对象，大量短命对象触发Minor GC。这个问题在高吞吐量场景（比如每秒几万次offer）非常明显。

具体解法：

// 错误：LinkedList作为队列
Queue<Message> queue = new LinkedList<>();
queue.offer(msg); // 每次 new Node，GC压力

// 正确：ArrayDeque
Queue<Message> queue = new ArrayDeque<>(10000); // 预设容量
queue.offer(msg); // 数组存储，分配效率高

// 并发场景：
// 单Producer单Consumer：ArrayBlockingQueue（有界）
// 多Producer多Consumer无界：ConcurrentLinkedQueue
// 不要用LinkedBlockingQueue（链表节点）除非需要无界且高并发

坑3：ArrayDeque不允许插入null，迁移时NPE

报错现象：把代码从LinkedList迁移到ArrayDeque，某些特定情况下报NullPointerException。

根本原因：ArrayDeque不允许插入null元素（用null作为空位标记，和LinkedList不同）。而LinkedList允许null。

具体解法：

// LinkedList允许null
LinkedList<String> ll = new LinkedList<>();
ll.offer(null); // 可以

// ArrayDeque不允许null
ArrayDeque<String> ad = new ArrayDeque<>();
// ad.offer(null); // 抛 NullPointerException

// 迁移时：如果数据里可能有null，用Optional包一层
Deque<java.util.Optional<String>> deque = new ArrayDeque<>();
deque.offer(java.util.Optional.ofNullable(nullableValue));
String result = deque.poll().orElse(null);

五、总结与延伸

  1. Stack的问题不是性能，是设计：继承Vector导致暴露了不属于栈的API（随机访问、中间插入），破坏了封装性。 Java官方已经在Javadoc里明确推荐用Deque替代，但历史包袱让Stack至今还在标准库里。

  2. ArrayDeque是Java集合里被严重低估的类。 它既能当栈（用push/pop），又能当队列（用offer/poll），底层循环数组保证均摊O(1)，无锁设计性能比Stack/Vector快约5倍。大多数用到栈或队列的场景，ArrayDeque是首选。

  3. 如果需要线程安全的栈/队列，别用Stack/Vector。 用ConcurrentLinkedDeque（无界无锁）或LinkedBlockingDeque（无界阻塞）。或者用Semaphore/ReentrantLock手动保护ArrayDeque——这样粒度更可控，性能通常也更好。

编辑此页
最近更新:
贡献者: xiaozhangge