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

2022-01-22 00:00:00 data-structures deque stack java

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

I need a Stack data structure for my use case. I should be able to push items into the data structure and I only want to retrieve the last item from the Stack. The JavaDoc for Stack says :

一组更完整和一致的 LIFO 堆栈操作是由 Deque 接口及其实现提供,应该优先于此类使用.例如:

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. For example:

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

我绝对不想在这里同步行为,因为我将在方法本地使用这个数据结构.除此之外,为什么我应该更喜欢 Deque 而不是 Stack ?

I definitely do not want synchronized behavior here as I will be using this datastructure local to a method . Apart from this why should I prefer Deque over Stack here ?

P.S:来自 Deque 的 javadoc 说:

P.S: The javadoc from Deque says :

双端队列也可以用作 LIFO(后进先出)堆栈.这应优先使用接口而不是旧的 Stack 类.

Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.

推荐答案

一方面,它在继承方面更明智.在我看来,Stack 扩展 Vector 的事实真的很奇怪.在 Java 早期,IMO 过度使用继承 - Properties 是另一个例子.

For one thing, it's more sensible in terms of inheritance. The fact that Stack extends Vector is really strange, in my view. Early in Java, inheritance was overused IMO - Properties being another example.

对我来说,您引用的文档中的关键词是一致.Deque 公开了一组操作,这些操作都是关于能够从集合的开头或结尾获取/添加/删除项目、迭代等 - 就是这样.故意无法按位置访问元素,Stack 暴露了 因为它是 Vector 的子类.

For me, the crucial word in the docs you quoted is consistent. Deque exposes a set of operations which is all about being able to fetch/add/remove items from the start or end of a collection, iterate etc - and that's it. There's deliberately no way to access an element by position, which Stack exposes because it's a subclass of Vector.

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

Oh, and also Stack has no interface, so if you know you need Stack operations you end up committing to a specific concrete class, which isn't usually a good idea.

正如评论中指出的,StackDeque 具有反向迭代顺序:

Also as pointed out in the comments, Stack and Deque have reverse iteration orders:

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():

以正确的顺序返回此双端队列中元素的迭代器.元素将按从第一个(头)到最后一个(尾)的顺序返回.

Returns an iterator over the elements in this deque in proper sequence. The elements will be returned in order from first (head) to last (tail).

相关文章