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

我需要一个Stack数据结构为我的用例。我应该能够将项目推入数据结构，我只想从堆栈中检索最后一项。JavaDoc for Stack说:

一个更完整和一致的LIFO堆栈操作集是 由Deque接口及其实现提供，这应该 优先用于该类。例如:< / p > 
Deque<Integer> stack = new ArrayDeque<>();

我肯定不希望在这里使用同步行为，因为我将在方法的本地使用这个数据结构。除此之外，为什么我应该更喜欢Deque而不是Stack在这里?

附:Deque的javadoc说:

Deques也可以用作后进先出(LIFO)堆栈。这

.接口应该优先于传统的Stack类
113433 次浏览
小开
最佳答案

一方面，它在继承方面更合理。在我看来，Stack扩展Vector的事实真的很奇怪。在Java早期，IMO过度使用继承——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

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

以适当的顺序返回该deque中元素的迭代器。元素将按照从第一个(头)到最后一个(尾)的顺序返回。

小开

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

如果你看一下通用实现在这里 -你会发现有一个一致的方法来实现set, map和list。

  • 对于set和map，我们有两个标准的哈希映射和树实现。第一个是最常用的，第二个是当我们需要一个有序结构时使用的(它也实现了自己的接口——SortedSet或SortedMap)。

  • 我们可以使用首选的声明风格，如Set<String> set = new HashSet<String>();see reason here。

但是Stack类:1)没有自己的接口;2)是Vector类的子类-它是基于可调整大小的数组;那么堆栈的链表实现在哪里呢?

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

小开
对我来说，这一点是缺失的: Stack是线程安全的，因为它是从Vector派生的，而大多数deque实现不是，因此如果你只在单个线程中使用它，速度会更快
小开

使用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]
小开

业绩可能是原因之一。我使用的一种算法通过将Stack替换为Deque将时间从7.6分钟缩短到1.5分钟。

小开

下面是Deque优于Stack的几个原因:

面向对象设计——继承、抽象、类和接口:Stack是一个类，Deque是一个接口。只能扩展一个类，而Java中的单个类可以实现任意数量的接口(类型的多重继承)。使用Deque接口消除了对具体Stack类及其祖先的依赖，并为您提供了更大的灵活性，例如，可以自由扩展不同的类或交换出不同的Deque实现(如LinkedList, ArrayDeque)。

不一致性:Stack扩展了Vector类，允许您通过索引访问元素。这与Stack应该做的事情不一致，这就是为什么Deque接口是首选的(它不允许这样的操作)——它允许的操作与FIFO或LIFO数据结构应该允许的操作一致。

性能:Stack扩展的Vector类基本上是ArrayList的“线程安全”版本。同步可能会对应用程序造成严重的性能影响。此外，扩展其他类使用不需要的功能(如第2条所述)会使对象膨胀，可能会消耗大量额外的内存和性能开销。

小开

Deque在实现方面优于stack有以下几个原因:

  1. Deque是接口，stack是类: 在创建类时，实现一个接口比扩展一个类更好 因为在扩展之后你不能扩展另一个类，你只能在另一方面实现一个接口，当你实现一个接口时，你可以扩展一个类，同时也可以实现另一个接口

    2. <李> < p >同步: 因为堆栈类是vector类的子类，vector类是异步的 stack太，但Deque不是。 因此，如果不需要同步，那么为了更好的性能，我们应该使用 双端队列。< / p >

  2. Deque的迭代器的工作方式与我们对堆栈的期望相同: 堆栈中的迭代是自下而上的(FIFO(先进先出))。 但是Deque中的迭代是自上而下的(后进先出)

  3. Stack不是真正的LIFO: 我们知道stack是vector类的子类，所以我们可以通过

小开

如果出于某种原因，你想从Stack转换到Deque，但想在转换到ArrayList时保持相同的顺序，你可以使用Deque.descendingIterator()。

但是ArrayList没有接受Iterator的构造函数，所以你可能想把它和一个库结合起来，比如Guava(或Apache Commons):

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

或者Java 8:

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

提交答案