为什么要在堆栈上使用双端队列?

问题描述 投票:134回答:6

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

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

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

我绝对不希望在这里出现同步行为,因为我将使用方法本地的数据结构。除此之外,为什么在这里我更喜欢Deque而不是Stack

P.S:Deque的Javadoc说:

双端队列也可以用作LIFO(后进先出)堆栈。这个接口应优先于旧版Stack类使用。

java data-structures
6个回答
167
投票

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

对我来说,您引用的文档中的关键词是consistentDeque公开了一组操作,这些操作仅涉及能够从集合的开头或结尾获取,添加/删除项,进行迭代等-就是这样。故意没有办法按位置访问元素,Stack公开了因为这是Vector的子类。

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

也如注释中所指出,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()中也对此进行了说明:

以适当的顺序返回此双端队列中的元素的迭代器。元素将按照从头(头)到后(尾)的顺序返回。


3
投票

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

如果您查看通用实现here-您会看到有一种一致的方法来实现集合,映射和列表。

  • 对于集和地图,我们有2个带有哈希图和树的标准实现。第一个最常用,第二个在需要有序结构时使用(它也实现了自己的接口-SortedSet或SortedMap)。

  • 我们可能会使用首选的声明方式,例如Set<String> set = new HashSet<String>();,请参见原因here

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

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


2
投票

在堆栈上使用出队的另一个原因是出队可以使用流转换为列表的流,并保持应用了LIFO概念,而没有在堆栈上应用。

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]

0
投票

对我来说,这点很重要:堆栈是线程安全的,因为它是从Vector派生的,而大多数双端队列的实现则不是,因此如果只在单个线程中使用它,则速度会更快。


0
投票

性能可能是一个原因。通过使用Deque替换Stack,我使用的算法从7.6分钟减少到1.5分钟。


-4
投票

使用双端队列是要从头部和尾部检索元素的情况。如果您想要一个简单的堆栈,则无需进行双端队列。

© www.soinside.com 2019 - 2024. All rights reserved.