java - 为什么我应该使用 Deque 而不是 Stack，使用 LinkedList 而不是 Queue？

Question

当我了解堆栈和队列时，它在 ArrayList 上使用堆栈/队列。但是，我通过Intellij搜索API，Stack和Queue在列表集合中使用ArrayDeque类，而不是ArrayList。

  /**
  * <p>A more complete and consistent set of LIFO stack operations is
   * provided by the {@link Deque} interface and its implementations, which
  * should be used in preference to this class.  For example:
  * <pre>   {@code   *   Deque<Integer> stack = new ArrayDeque<Integer>();}
  */

在Queue中，它使用LinkedList API中的LinkedList类。大多数人的代码也像:

Queue<Integer> q1 = new LinkedList<>()

/**
 * Queue operations.
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */

重点是，在解释Stack和Queue这个概念时，使用ArrayList。

但是，实际上，使用 LinkedList 或 ArrayDeque，而不是 ArrayList。你能解释一下为什么吗？

Answer 1

这个问题大部分是针对 Java 的，但是关于使用数组列表作为队列的部分则更为通用。

<小时/>

特别是在 Java 中，您应该使用 ArrayDeque 或另一个双端队列实现而不是 Stack 类:根据文档，

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.

选择 ArrayDeque 的另一个原因对于大多数用例来说 Stack 延伸 Vector ，这是一个同步实现。同步会降低性能，并且当仅从单个线程访问堆栈时(即几乎所有时间)，同步是不必要的。

安 ArrayDeque 比 ArrayList 更好作为堆栈，因为要模拟pop ArrayList 上的方法你必须写s.remove(s.size() - 1) ，这不方便且不太清晰。

<小时/>

您应该使用 LinkedList 的原因“而不是” Queue 是因为 Queue 是一个接口(interface)，而不是一个类，所以你根本不能写 new Queue<>()创建队列；这会产生编译错误。

请注意，最好将变量的类型声明为 Queue<...> .

<小时/>

您不应该使用 ArrayList 的原因因为队列更通用:它是 dynamic array data structure ，因此它只支持一端 O(1) 时间内的添加和删除操作。在另一端添加或删除需要 O(n) 时间。所以它不适合用作队列，因为队列应该在不同的一端入队和轮询，与其他更合适的队列数据结构相比，一端的操作效率会很低。