Java 中 Deque 与 Stack 的对比分析

1. 概述

Java 中的 Stack 类实现了栈数据结构。从 Java 1.6 开始，引入了 Deque 接口，用于实现一个“双端队列”，支持在两端进行元素的插入和删除操作。

现在，我们也可以将 Deque 接口用作 LIFO（后进先出）的栈。此外，如果你查看 Java 官方文档中对 Stack 类的说明，你会发现这样一句话：

更完整且一致的一组 LIFO 栈操作由 Deque 接口及其具体实现提供，应优先使用这些类而不是本类。

本文将对比 Java 中的 Stack 类和 Deque 接口，并探讨为什么在实现 LIFO 栈时应该优先选择 Deque 而不是 Stack。

2. 类 vs 接口

Java 的 Stack 是一个类：

public class Stack<E> extends Vector<E> { ... }

也就是说，如果我们要自定义自己的 Stack 类型，就必须继承 java.util.Stack 类。

由于 Java 不支持多重继承，在我们的类已经继承了其他类的情况下，扩展 Stack 类可能会变得很困难：

public class UserActivityStack extends ActivityCollection { ... }

在上面的例子中，UserActivityStack 已经是 ActivityCollection 的子类，因此它无法再继承 java.util.Stack 类。为了使用 Java 原生的 Stack 类，我们可能需要重新设计数据模型。

而 Java 的 Deque 是一个接口：

public interface Deque<E> extends Queue<E> { ... }

我们知道，在 Java 中一个类可以实现多个接口。因此，实现接口比继承类更加灵活。

例如，我们可以轻松地让 UserActivityStack 实现 Deque 接口：

public class UserActivityStack extends ActivityCollection implements Deque<UserActivity> { ... }

✅ 所以从面向对象设计的角度来看，使用 Deque 接口比 Stack 类更灵活。

3. 同步方法与性能

我们已经知道 Stack 类是 java.util.Vector 的子类。而 Vector 类是线程安全的，它采用传统方式实现线程安全：所有方法都加上了 synchronized 关键字。

作为其子类，Stack 类自然也是同步的。

而另一方面，Deque 接口本身并不保证线程安全。

⚠️ 因此，如果不需要线程安全特性，使用 Deque 通常比 Stack 性能更好。

4. 迭代顺序差异

虽然 Stack 和 Deque 都是 java.util.Collection 的子类型，因此也都支持迭代（Iterable），但它们的迭代顺序却不同。

如果我们以相同顺序向 Stack 对象和 Deque 实例中压入相同的元素，它们的迭代顺序是不一样的。

让我们通过示例来看清楚这一点。

4.1. Stack 的迭代顺序是从底部到顶部

@Test
void givenAStack_whenIterate_thenFromBottomToTop() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am at the bottom.");
    myStack.push("I am in the middle.");
    myStack.push("I am at the top.");

    Iterator<String> it = myStack.iterator();

    assertThat(it).toIterable().containsExactly(
      "I am at the bottom.",
      "I am in the middle.",
      "I am at the top.");
}

运行这个测试会通过。也就是说，当我们遍历 Stack 中的元素时，顺序是从栈底到栈顶。

4.2. Deque 的迭代顺序是从顶部到底部

@Test
void givenADeque_whenIterate_thenFromTopToBottom() {
    Deque<String> myStack = new ArrayDeque<>();
    myStack.push("I am at the bottom.");
    myStack.push("I am in the middle.");
    myStack.push("I am at the top.");

    Iterator<String> it = myStack.iterator();

    assertThat(it).toIterable().containsExactly(
      "I am at the top.",
      "I am in the middle.",
      "I am at the bottom.");
}

这个测试也会通过。

✅ 所以说，Deque 的迭代顺序是从栈顶到栈底。

📌 对于一个标准的 LIFO 栈来说，正确的迭代顺序应该是从栈顶到底部。从这个角度看，Deque 的行为更符合我们对栈的预期。

5. 非法的 LIFO 栈操作

标准的 LIFO 栈只支持三个核心操作：push()、pop() 和 peek()。Stack 类和 Deque 接口都支持这三个方法。这点上没有问题。

但问题在于，LIFO 栈不应该允许通过索引访问或操作元素，因为这会破坏栈的 LIFO 特性。

接下来我们看看 Stack 和 Deque 是否允许这种非法操作。

5.1. java.util.Stack 类允许索引操作 ❌

由于其父类 Vector 是基于数组的结构，Stack 类具备通过索引访问元素的能力：

@Test
void givenAStack_whenAccessByIndex_thenElementCanBeRead() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am the 1st element."); //index 0
    myStack.push("I am the 2nd element."); //index 1
    myStack.push("I am the 3rd element."); //index 2
 
    assertThat(myStack.get(0)).isEqualTo("I am the 1st element.");
}

运行测试会通过。

也就是说，我们可以通过索引直接访问栈底元素，而不需要遵循 LIFO 的弹出规则。

更离谱的是，我们甚至可以通过索引插入和删除元素：

@Test
void givenAStack_whenAddOrRemoveByIndex_thenElementCanBeAddedOrRemoved() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am the 1st element.");
    myStack.push("I am the 3rd element.");

    assertThat(myStack.size()).isEqualTo(2);

    myStack.add(1, "I am the 2nd element.");
    assertThat(myStack.size()).isEqualTo(3);
    assertThat(myStack.get(1)).isEqualTo("I am the 2nd element.");

    myStack.remove(1);
    assertThat(myStack.size()).isEqualTo(2);
}

这个测试同样可以通过。

📌 所以说，Stack 类允许我们像操作数组一样操作栈元素，完全破坏了 LIFO 的语义。

5.2. java.util.Deque 接口不支持索引操作 ✅

Deque 不允许通过索引访问、插入或删除元素，这比 Stack 更合理。

但由于 Deque 是“双端队列”，它可以在两端插入或删除元素。

也就是说，当我们把 Deque 当作栈使用时，仍然可以直接操作栈底元素：

@Test
void givenADeque_whenAddOrRemoveLastElement_thenTheLastElementCanBeAddedOrRemoved() {
    Deque<String> myStack = new ArrayDeque<>();
    myStack.push("I am the 1st element.");
    myStack.push("I am the 2nd element.");
    myStack.push("I am the 3rd element.");

    assertThat(myStack.size()).isEqualTo(3);

    // 插入到栈底
    myStack.addLast("I am the NEW element.");
    assertThat(myStack.size()).isEqualTo(4);
    assertThat(myStack.peek()).isEqualTo("I am the 3rd element.");

    // 从栈底删除
    String removedStr = myStack.removeLast();
    assertThat(myStack.size()).isEqualTo(3);
    assertThat(removedStr).isEqualTo("I am the NEW element.");
}

运行测试会通过。

📌 所以说，Deque 也并没有完全遵守 LIFO 的语义。

5.3. 基于 Deque 实现一个严格的 LIFO 栈 ✅

我们可以通过封装 Deque 来实现一个严格遵循 LIFO 规则的栈接口：

public interface LifoStack<E> extends Collection<E> {
    E peek();
    E pop();
    void push(E item);
}

然后我们可以在实现类中封装一个 Deque 实例，比如 ArrayDeque：

public class ArrayLifoStack<E> implements LifoStack<E> {
    private final Deque<E> deque = new ArrayDeque<>();

    @Override
    public void push(E item) {
        deque.addFirst(item);
    }

    @Override
    public E pop() {
        return deque.removeFirst();
    }

    @Override
    public E peek() {
        return deque.peekFirst();
    }

    // 转发 Collection 接口方法
    @Override
    public int size() {
        return deque.size();
    }
...
}

📌 通过这种方式，我们可以确保只暴露栈应有的操作，从而真正遵守 LIFO 的语义。

6. 结论

自 Java 1.6 起，java.util.Stack 和 java.util.Deque 都可以用来实现 LIFO 栈。本文对比了它们之间的差异，并分析了为什么推荐使用 Deque 而不是 Stack。

此外，我们也通过示例展示了 Stack 和 Deque 在某些场景下都会破坏 LIFO 语义。

最后，我们还演示了如何基于 Deque 实现一个严格遵守 LIFO 规则的栈接口。

📌 总结一下：

✅ 优先使用 Deque 实现栈，而不是 Stack
⚠️ Stack 是同步的，性能不如 Deque
❌ Stack 和 Deque 都不完全符合 LIFO 语义
✅ 可以封装 Deque 实现真正的 LIFO 栈

完整代码示例可在 GitHub 项目中找到。

Persistence

REST

Security