42

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

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

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

  2. 如果没有，有没有办法在不重新实现的情况下将队列转换为 LIFO 队列（又名堆栈）？

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

非常感谢。

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

4

6 回答 6

59

实际上有一个 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 ) 具有addFirstandaddLast和removeFirstandremoveLast方法，使其非常适合用作堆栈或队列类。

于 2008-11-19T16:24:39.520 回答
11

我意识到我在这里聚会迟到了，但是 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)

于 2014-01-17T19:25:33.757 回答
11

Deque, ArrayDeque, &LinkedList

虽然前一段时间有人问过这个问题，但提供一个 JDK6+ 答案可能是明智的，它现在提供了一个由ArrayDeque数据结构实现的Deque（甲板）接口，并且更新了LinkedList以实现这个接口。

ConcurrentLinkedDeque&LinkedBlockingDeque

并发访问的特殊形式也存在并由ConcurrentLinkedDeque和LinkedBlockingDeque实现。

LIFO 与 FIFO

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

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

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

只有堆栈操作被公开，这会阻止某人在打算使用push(E )时意外调用add(E) 。

于 2015-02-28T22:25:09.357 回答
8

堆栈类很慢：方法是同步的 +堆栈扩展同步向量

于 2008-12-22T14:04:19.680 回答
7

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

于 2008-11-19T16:24:08.180 回答
3

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());
于 2016-10-05T16:21:08.650 回答