Java集合（LIFO结构）

Question

我在查找Java的集合框架中寻找一个后进先出的结构（栈），但没有成功。基本上，我想要一个非常简单的栈；我的完美选择是Deque，但我使用的是Java 1.5。

我不想为我的结构添加另一个类，但我想知道是否有可能：

1. 在Collections框架（1.5）中有没有可以胜任这项工作的类？

2. 如果没有，有没有办法将队列转换为后进先出队列（也称为栈），而不需要重新实现？

3. 如果没有，应该扩展哪个接口或类来完成此任务？我想保持Sun公司使用Deque所采用的方式是一个很好的开始。

非常感谢。

编辑：我忘了提到Stack类：当我看到它实现Vector类时，我对这个类有所疑虑，而Vector类有点过时，对吗？

- David Santamaria

---

Vector的主要问题在于所有访问都是同步的，无论你是否需要。它与其他集合一样“最新”，但由于同步问题而声名狼藉。 - Ken Gentle

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 方法，使其非常适合用作堆栈或队列类。

- Eli Courtwright

---

LinkedList 还提供了 Deque 的定义，它是您所需的集合类型。 - Spencer Kormos

是的，我认为LinkedList就是我正在寻找的那个，因为在我第一次看它时，我没有意识到Addfirst和removeFirst方法。非常感谢。 - David Santamaria

@SpencerKormos ... 而且 LinkedList 与 ArrayDeque 相比，还支持空元素。 - dma_k

更新：此答案已过时。Stack类已被更现代的类所取代，如Javadoc中所解释的那样：“Deque接口及其实现提供了更完整和一致的LIFO堆栈操作集，应优先使用这个类。”请参见Brett Ryan的答案和Ivan的答案中的当前解决方案。 - Basil Bourque

在Java 21中，List扩展了新的SequencedCollection接口，其中包含addFirst、addLast、getFirst、getLast、removeFirst、removeLast等方法，因此您可以使用ArrayList。 - Olivier Boissé

Answer 2

我意识到我来晚了，但 Java7 中的 java.util.Collections 类提供了一个静态方法 'asLifoQueue'，它接受一个 Deque 参数并返回 (显然) 一个 Deque 的后进先出队列视图。我不确定这个版本是在哪个时候添加的。

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

- JVMATL

---

它是在Java 1.6中添加的。 - Gili

Answer 3

Deque、ArrayDeque 和 LinkedList

虽然这是以前的问题，但提供一个JDK6+的答案是明智的。现在提供了一个称为Deque（双端队列）接口，由ArrayDeque数据结构实现，而LinkedList已更新为实现此接口。

ConcurrentLinkedDeque 和 LinkedBlockingDeque

还存在专门用于并发访问的特殊形式，由ConcurrentLinkedDeque和LinkedBlockingDeque实现。

LIFO与FIFO

关于双端队列最好的一点是它既支持LIFO（堆栈），又支持FIFO（队列）。对于新手来说，这可能会导致混淆，因为不知道哪些方法是用于队列操作，哪些是用于堆栈操作。

在我看来，JDK应该有一个Stack接口和一个Queue接口，仍然可以由像ArrayDeque这样的数据结构实现，但只公开所需的子集方法，即LIFO可以定义pop()、push()和peek()，然后在上下文中：

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

只有堆栈操作是公开的，这可以防止某人在本意为使用push(E)时错误地调用add(E)。

- Brett Ryan

Answer 4

Stack类速度较慢：其方法是同步的 + Stack继承了同步的Vector

- Spy_DER

Answer 5

API中有一个Stack类。这个类符合您的需求吗？

- Greg Heidorn

---

抱歉，我忘了提到关于堆栈类和我的看法，但我认为可能比实现自己的类更好的解决方案是使用它，不是吗？ - David Santamaria

不要使用 Stack 类。它是继承自 Vector 的，而 Vector 仅为了向后兼容而保留。 - erickson

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

使用 LinkedList 来备份 Deque 对于性能来说非常好，因为它的元素插入和删除都是常数时间（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());

- Ivo

---

原始帖子使用的是明显是FIFO而不是LIFO的队列，因此我已经更新了我的答案。 - Ivo