为什么我应该使用Deque over Stack?

2022-08-31 05:43:34

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

Deque 接口及其实现提供了一组更完整、更一致的 LIFO 堆栈操作,应优先使用此类。例如:

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

我绝对不希望在这里进行同步行为,因为我将使用此方法的本地数据结构。除此之外,我为什么要更喜欢这里?DequeStack

P.S:来自Deque的javadoc说:

Deques也可以用作LIFO(Last-In-First-Out)堆栈。应优先使用此接口,而不是旧版 Stack 类。


答案 1

首先,在继承方面更明智。在我看来,扩展的事实真的很奇怪。在Java的早期,继承被过度使用IMO - 这是另一个例子。StackVectorProperties

对我来说,你引用的文档中的关键词是一致的。 公开了一组操作,这些操作都是关于能够从集合的开始或结束获取/添加/删除项目,迭代等 - 仅此而已。故意无法按位置访问元素,这会暴露,因为它是 的子类。DequeStackVector

哦,而且也没有接口,所以如果你知道你需要操作,你最终会提交到一个特定的具体类,这通常不是一个好主意。StackStack

同样如注释中指出的那样,并且具有反向迭代顺序:StackDeque

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 for Deque.iterator()中也有解释:

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


答案 2

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

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

不一致:Stack 扩展了 Vector 类,允许您按索引访问元素。这与堆栈实际应该执行的操作不一致,这就是为什么Deque接口是首选(它不允许此类操作)的原因 - 它允许的操作与FIFO或LIFO数据结构应该允许的操作一致。

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


推荐