如何在 Java 中利用 ArrayDeque 作为双端队列同时实现栈与队列的高效操作

如何在 Ja va 中利用 ArrayDeque 作为双端队列同时实现栈与队列的高效操作

在 Ja va 集合框架中，ArrayDeque 是一个常被低估但实力非凡的选手。它本质上是一个基于循环数组实现的双端队列（deque），这意味着它能在队列的两端都提供高效的添加和删除操作。更重要的是，它没有内置的同步开销，这使得它在性能上成为传统 Stack 类和 LinkedList 作为队列时的理想替代品。其内部设计精妙，扩容策略合理，确保了所有核心操作——无论是 addFirst、addLast，还是 removeFirst、removeLast，抑或是查看元素的 peekFirst 和 peekLast——其平均时间复杂度都能稳定在 O(1)。

ArrayDeque 是基于循环数组实现的高效双端队列，支持 O(1) 均摊时间复杂度的两端操作；模拟栈时统一用 *Last 方法（push/pop/peek），模拟队列时用 addLast + removeFirst（或 offer/poll/peek），语义清晰且性能优于 Stack 和 LinkedList。

用 ArrayDeque 模拟栈（LIFO）

栈的核心原则是后进先出（LIFO）。用 ArrayDeque 来实现这一点非常直观：你只需要固定在同一端进行操作，通常推荐使用尾端。这样一来，方法调用就变得非常清晰：

• 压栈 (push): 使用 push(e) 方法，它实际上等价于 addLast(e)（或者更温和的 offerLast(e)）。
• 弹栈 (pop): 使用 pop() 方法，它等价于 removeLast()（如果栈为空会抛出异常），或者你可以选择无异常的 pollLast()（栈空时返回 null）。
• 查看栈顶 (peek): 使用 peek() 方法，它对应的是 peekLast()，只查看不删除元素。

来看一个简单的例子，一切就一目了然了：

Deque stack = new ArrayDeque<>();
stack.push(1); stack.push(2); // 栈内状态：[1, 2]
int top = stack.pop(); // 返回 2，栈变为 [1]

用 ArrayDeque 模拟队列（FIFO）

队列遵循先进先出（FIFO）的规则。用 ArrayDeque 模拟队列，诀窍在于“一端进，另一端出”，通常采用“尾进头出”的策略：

立即学习“Ja va免费学习笔记（深入）”；

• 入队 (offer): 使用 offer(e) 方法，这相当于 addLast(e) 或 offerLast(e)。
• 出队 (poll): 使用 poll() 方法，它对应的是 removeFirst()（异常版）或 pollFirst()（安全版，返回 null）。
• 查看队首 (peek): 使用 peek() 方法，也就是 peekFirst()。

实践一下，逻辑非常顺畅：

Deque queue = new ArrayDeque<>();
queue.offer("a"); queue.offer("b"); // 队列状态：["a", "b"]
String head = queue.poll(); // 返回 "a"，队列变为 ["b"]

避免误用：别混用两端操作破坏语义

这里有一个关键的实践要点：保持语义的一致性。如果你正在模拟一个栈，却偶尔调用了 addFirst() 或 removeFirst()，那么后进先出的顺序就被彻底打乱了。同理，在队列模式中混用 addLast() 和 removeLast()，不知不觉间你就把它变成了一个栈。所以，记住这个简单的约定：

• 栈模式: 坚持使用与“尾端”相关的方法，即 *Last(...) 系列（或直接使用别名方法 push/pop/peek）。
• 队列模式: 坚持使用“尾进头出”的组合，即 addLast() + removeFirst()（或它们的别名 offer/poll/peek）。

幸运的是，Ja va 的设计者已经考虑到了这一点，为这两种常见场景提供了清晰的方法别名。直接使用 push、pop、peek 来操作栈，使用 offer、poll、peek 来操作队列，不仅语义一目了然，也省去了记忆底层是“头”还是“尾”的麻烦。

为什么不用 Stack 或 LinkedList？

你可能会问，既然有现成的 Stack 类，为什么还要用 ArrayDeque 来模拟栈呢？原因在于，Stack 类继承自陈旧的 Vector，其所有方法都是同步的，这在单线程环境下带来了不必要的性能损耗，并且其“继承”的设计也违背了现代“组合优于继承”的原则。至于 LinkedList，它虽然也实现了 Deque 接口，但其底层基于链表。每个元素都需要额外的指针空间，内存访问的缓存局部性较差，因此在大多数场景下，其实际性能表现往往不如基于数组的 ArrayDeque。事实上，Ja va 官方文档也明确给出了建议：“此类很可能在用作栈时比 Stack 快，在用作队列时比 LinkedList 快。” 所以，当需要在栈和队列之间做选择，或者追求极致性能时，ArrayDeque 无疑是更优的那个选项。