为什么我应该使用Deque而不是Stack？

Question

为什么我应该使用Deque而不是Stack？

248

我需要一个Stack数据结构来满足我的需求。我应该能够将项目推入数据结构中，并且我只想从堆栈中检索最后一项。 Stack的JavaDoc说:

Deque接口及其实现提供了更完整和一致的LIFO堆栈操作集，应优先使用它们而不是此类。例如：

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

在这里，我绝对不希望出现同步行为，因为我会将这个数据结构用于方法的本地。除此之外，为什么我应该在这里优先选择 Deque 而不是 Stack 呢？

P.S：来自 Deque 的 javadoc 说：

Deques 也可以用作 LIFO（后进先出）栈。与传统的 Stack 类相比，应优先使用此接口。

- Geek

1

它提供了更多内置方法，或者说是“更完整和一致的集合”，如果您利用它们，将减少您需要编写的代码量。 - user684934

4

http://baddotrobot.com/blog/2013/01/10/stack-vs-deque/ - Free-Minded

8个回答

48

以下是Deque优于Stack的几个原因：

1.面向对象设计 - 继承、抽象、类和接口：Stack是一个类，而Deque是一个接口。在Java中，一个类只能被继承一次，但是一个类可以实现任意数量的接口（类型的多继承）。使用Deque接口可以消除对具体Stack类及其祖先的依赖性，并提供更大的灵活性，例如扩展不同的类或替换Deque的不同实现（如LinkedList、ArrayDeque）。

2.不一致性：Stack扩展了Vector类，允许通过索引访问元素。这与Stack实际应该执行的操作不一致，这就是为什么Deque接口更受欢迎的原因（它不允许这样的操作）--它允许的操作与FIFO或LIFO数据结构应该允许的操作保持一致。

3.性能：Stack扩展的Vector类基本上是ArrayList的“线程安全”版本。同步可能会对应用程序造成显着的性能损失。此外，扩展其他具有不需要功能的类（如#2中提到的）会使您的对象变得臃肿，可能会产生大量的额外内存和性能开销。

- Arpit Bhargava

4

这是一个不错的、特定领域的解释。毫无疑问，这是一个简短的采访材料。谢谢。 - sud007

20

使用Deque而不是Stack的另一个原因是，Deque具有使用流将其转换为列表并保持LIFO概念应用的能力，而Stack没有。

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

stack.push(1);//1 is the top
deque.push(1)//1 is the top
stack.push(2);//2 is the top
deque.push(2);//2 is the top

List<Integer> list1 = stack.stream().collect(Collectors.toList());//[1,2]

List<Integer> list2 = deque.stream().collect(Collectors.toList());//[2,1]

- Amer Qarabsa

2

好的，谢谢你提供这个例子。 - sud007

6

这是我对Stack类描述中提到的不一致性的解释。

如果您查看通用实现此处 - 您会发现在实现set、map和list时有一致的方法。

- 对于set和map，我们有2种标准实现：哈希映射和树。第一种最常用，第二种用于需要有序结构的情况（它还实现了自己的接口-SortedSet或SortedMap）。 - 我们可以使用首选的声明样式，例如 Set<String> set = new HashSet<String>(); 请参见此处的原因。

但是Stack类：1）没有自己的接口；2）是Vector类的子类-基于可调整大小的数组；那么stack的链表实现在哪里呢？

在Deque接口中，我们没有这样的问题，包括两个实现（可调整大小的数组-ArrayDeque; 链表-LinkedList）。

- irudyak

4

对于我来说，这个特定的点被忽略了：栈是线程安全的，因为它是从向量派生而来的，而大多数双端队列实现都不是线程安全的，所以如果你只在单个线程中使用它，那么速度会更快。

- Andi

2

grep "除此之外" - Pacerier

2

如果您想从堆栈（Stack）切换到双端队列（Deque），但希望在转换为ArrayList时保留相同的顺序，可以使用Deque.descendingIterator()。

然而，ArrayList没有接受迭代器的构造函数，因此您可能需要将其与Guava（或Apache Commons）等库结合使用：

Lists.newArrayList(deque.descendingIterator()) // Guava

或者Java 8：

List<Integer> list = new ArrayList<>();
deque.descendingIterator().forEachRemaining(list::add);

- Mads Hoel

2

Deque比栈更好的原因有以下几点：

Deque是一个接口而栈是一个类：在类创建中，实现一个接口比扩展一个类更好，因为在扩展后，您无法再扩展另一个类，只能在另一方面实现另一个接口时，您可以扩展一个类并实现其他接口。
同步：因为stack类是vector类的子类，而vector类是异步的，所以stack也是异步的。但是Deque不是。因此，如果没有同步的需求，则为了获得更好的性能，我们应该使用Deque。
Deque的迭代器按照我们期望的方式工作，用于堆栈：堆栈的迭代是从底部到顶部（FIFO（先进先出））。但是Deque的迭代是从顶部到底部（LIFO（后进先出））。
栈不是真正的LIFO：我们知道栈是vector类的子类，因此我们可以通过它们的索引访问元素，这与LIFO合同相违背。

- sfarshian

1

可能是因为性能问题。我使用的算法仅通过将Stack替换为Deque，就将运行时间从7.6分钟降至1.5分钟。

- eddy

grep "除此之外" - Pacerier

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jon Skeet · Accepted Answer

一方面，从继承的角度来看，这么做更加明智。在我看来，Stack 扩展 Vector 真的很奇怪。早期的Java中，我认为过度使用了继承——Properties就是另一个例子。

对我而言，你引用的文档中关键词是“一致”。Deque暴露了一组操作，所有这些操作都与能够从集合开头或结尾获取/添加/删除项目，进行迭代等有关。特意没有提供通过位置访问元素的方法，而Stack却因为是Vector的子类而暴露出这个方法。

哦，而且，Stack没有接口，因此如果您知道需要Stack操作，则最终会选择一个具体的类，这通常不是一个好主意。

此外，正如评论中指出的那样，Stack和Deque具有相反的迭代顺序：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(new ArrayList<>(stack)); // prints 1, 2, 3


Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(new ArrayList<>(deque)); // prints 3, 2, 1

这也在JavaDocs中解释了Deque.iterator():

按正确顺序返回此deque中元素的迭代器。元素将按从第一个（头）到最后一个（尾）的顺序返回。