Java 集合（LIFO 结构）

Java Collections (LIFO Structure)

提问by David Santamaria

I am looking in the Collections framework of Java for a LIFO Structure (Stack) without any success. Basically I want a really simple stack; my perfect option would be a Deque, but I am in Java 1.5.

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

I would like not to have to add another class to my structure but I am wondering if that is possible:

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

1. Is there any class in the Collections framework (1.5) that does the job?

2. If not, is there any way to turn a Queue in a LIFO Queue (aka Stack) without reimplementation?

3. If not, which Interface or class should I extend for this task? I guess that keep the way that the guys of Sun have made with the Deque is a good start.

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

2. 如果没有，是否有任何方法可以在不重新实现的情况下在 LIFO 队列（又名堆栈）中转换队列？

3. 如果不是，我应该为这个任务扩展哪个接口或类？我想，保持 Sun 的家伙使用 Deque 的方式是一个好的开始。

Thanks a lot.

非常感谢。

EDIT: I forgot to say about the Stack class: I have my doubts about this class when I saw that it implements the Vector class, and the Vector class is a little bit obsolete, isn't it?

编辑：我忘了说 Stack 类：当我看到它实现了 Vector 类时，我对这个类产生了怀疑，而且 Vector 类有点过时了，不是吗？

采纳答案by Eli Courtwright

There's actually a Stack class: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Stack.html

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

If you don't want to use that, the LinkedList class (http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html) has addFirstand addLastand removeFirstand removeLastmethods, making it perfect for use as a stack or queue class.

如果您不想使用它，LinkedList 类（http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html）具有addFirstandaddLast和removeFirstandremoveLast方法，使其成为非常适合用作堆栈或队列类。

回答by Greg

There is a Stack class in the API. Will this meet your needs?

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

回答by Eli Courtwright

Stackclass is slowly: methods are synchronized + Stack extends synchronized Vector

堆栈类是慢慢：方法是同步+的Stacķ延伸同步矢量

回答by JVMATL

I realize I'm late to the party here, but java.util.Collections (Java 7) has a static 'asLifoQueue' that takes a Deque argument and returns (obviously) a LIFO queue view of the deque. I'm not sure what version this was added.

我意识到我在这里参加聚会迟到了，但是 java.util.Collections (Java 7) 有一个静态的“asLifoQueue”，它接受一个 Deque 参数并返回（显然）一个 deque 的 LIFO 队列视图。我不确定这是添加的哪个版本。

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

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

回答by Brett Ryan

Deque, ArrayDeque, & LinkedList

Deque, ArrayDeque, &LinkedList

While this was asked a while ago it might be wise to provide a JDK6+ answer which now provides a Deque(deck) interface which is implemented by the ArrayDequedata structure and the LinkedListwas updated to implement this interface.

虽然不久前有人问过这个问题，但提供 JDK6+ 的答案可能是明智的，它现在提供了一个由ArrayDeque数据结构实现的Deque(deck) 接口，并且LinkedList已更新以实现此接口。

ConcurrentLinkedDeque& LinkedBlockingDeque

ConcurrentLinkedDeque& LinkedBlockingDeque

Specialised forms for concurrent access also exist and are implemented by ConcurrentLinkedDequeand LinkedBlockingDeque.

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

LIFO versus FIFO

LIFO 与 FIFO

The one thing that is great about a deque is that it provides both LIFO (stack) and FIFO (queue) support it can cause confusion as to which methods are for queue operations and which are for stack operations for newcomers.

双端队列的一大优点是它同时提供了 LIFO（堆栈）和 FIFO（队列）支持，它可能会导致混淆哪些方法用于队列操作，哪些方法用于新人的堆栈操作。

IMHO the JDK should have a Stackinterface and a Queueinterface that could still be implemented by the likes of ArrayDequebut only expose the subset of methods required for that structure, i.e. a LIFO could define pop(), push()and peek(), then in the context of

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

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

only stack operations are exposed which stops someone accidentally calling add(E)when push(E)was intended.

仅公开堆栈操作，这会阻止有人在预期push(E)时意外调用add(E)。

回答by Ivo

Deque& LinkedList

Deque& LinkedList

Just for the sake of completeness I'm providing an example using Dequeinterface and a LinkedListimplementation.

为了完整起见，我提供了一个使用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());

Backing up a Dequeby a LinkedListis great for performance, since inserting and removing elements from it is done in constant time (O(1)).

Deque用 a备份 a LinkedList对性能很有好处，因为从其中插入和删除元素是在恒定时间 (O(1)) 内完成的。

Using a LinkedListalone:

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

回答by Ahmed Rezk

[WRONG ANSWER PERFORMANCE-WISE] I'm only keeping it for people to learn that this is not a good solution.

[错误答案性能明智] 我只是保留它，让人们了解这不是一个好的解决方案。

Simplest answer would be to use an ArrayList, and just add objects at the 0 index.

最简单的答案是使用ArrayList，只需在 0 索引处添加对象。

List<String> arrayList = new ArrayList<>();
arrayList.add(0, "three");
arrayList.add(0, "two");
arrayList.add(0, "one");

// Prints: [one, two, three]
System.out.println(arrayList);

adding objects at 0 index will add to the top of the list, and shifts the rest of the list. Now you have a simple functioning LIFO data structure.

在 0 索引处添加对象将添加到列表的顶部，并移动列表的其余部分。现在您有了一个简单的 LIFO 数据结构。

EDIT: Using a LinkedList is faster than using an ArrayList. So using LinkedList.addFirst() is better.

编辑：使用 LinkedList 比使用 ArrayList 更快。所以使用 LinkedList.addFirst() 更好。