Java集合(LIFO结构)

Question

我正在寻找Java的Collections框架中的LIFO结构(Stack)而没有任何成功.基本上我想要一个非常简单的堆栈; 我完美的选择是Deque,但我是Java 1.5.

我不想在我的结构中添加另一个类,但我想知道是否可能:

1. Collections框架(1.5)中是否有任何类可以完成这项工作？

2. 如果没有,有没有办法在没有重新实现的情况下在LIFO队列(即堆栈)中转换队列？

3. 如果没有,我应该为此任务扩展哪个接口或类？我想保持Sun公司与Deque的合作是一个良好的开端.

非常感谢.

编辑:我忘了谈论Stack类:当我看到它实现Vector类时,我对这个类有疑问,而Vector类有点过时了,不是吗？

Answer 1

实际上有一个Stack类:http://java.sun.com/j2se/1.5.0/docs/api/java/util/Stack.html

如果你不想使用,LinkedList类(http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html)有addFirst和addLast和removeFirst和removeLast方法,使它非常适合用作堆栈或队列类.

Answer 2

堆栈类很慢:方法同步+ Stac k扩展同步Vector

Answer 3

我知道我迟到了这里,但java.util.Collections中(Java 7中)有一个静态的"asLifoQueue",需要一个deque的参数和返回双端队列(显然)一个LIFO队列视图.我不确定这是什么版本.

http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#asLifoQueue(java.util.Deque)

Answer 4

API中有一个Stack类.这会满足您的需求吗？

Answer 5

虽然前一段时间提出这个问题,但提供一个JDK6 +答案可能是明智之举,该答案现在提供了一个Deque(deck)接口,该接口由ArrayDeque数据结构实现,并且LinkedList已更新以实现此接口.并发访问的专用表单也存在,并由ConcurrentLinkedDeque和LinkedBlockingDeque实现.

关于双端队列的一件好事是它提供了LIFO(堆栈)和FIFO(队列)支持,它可能会导致混淆哪些方法用于队列操作以及哪些方法用于新手的堆栈操作.

恕我直言,在JDK应该有一个Stack接口和Queue可能仍然被这样的人来实现的接口ArrayDeque但只公开的该结构所需的方法的子集,即LIFO可以定义pop(),push()和peek(),然后在上下文

LIFO<String> stack = new ArrayDeque<>();

只有堆栈操作被暴露,这会阻止某人在推送(E)时意外调用add(E).

Answer 6

Deque&LinkedList

为了完整起见，我提供了一个使用Deque接口和LinkedList实现的示例。

    Deque<String> deque = new LinkedList<>();
    deque.add("first");
    deque.add("last");

    // returns "last" without removing it
    System.out.println(deque.peekLast());

    // removes and returns "last"
    System.out.println(deque.pollLast());

Deque 按 a备份 a LinkedList对于性能来说非常有用，因为向其中插入和删除元素是在常数时间内完成的 (O(1))。

单独使用LinkedList：

    LinkedList<String> list = new LinkedList<>();
    list.add("first");
    list.add("last");

    // returns "last" without removing it
    System.out.println(list.getLast());

    // removes and returns "last"
    System.out.println(list.removeLast());