用于队列和堆栈的Java LinkedList方法

Question

如果你看一下Java的LinkedList方法，它确实提供了Queue, Stack, Deque的操作。

我知道你可以用LinkedList实现Queue, Stack或Deque。如果你看一下c#的实现，Queue和Stack使用数组。

我的好奇心是，为什么他们为链表提供推送(T e)方法?

为什么Queue和Stack不是独立的类，就像c#一样。

下面是push和pop的代码，即duhhh。但是为什么呢?

public void push(Object obj)
{
    addFirst(obj);
}
public Object pop()
{
    return removeFirst();
}

如果你看HashMap或HashSet，它在内部使用数组，并且有相应的LinkedHashSet和map来保持排序。

这不是真的令人困惑，但它真的没有意义。

为什么java有这样的实现?

Answer 1

关注数据结构实现:

链表对于频繁的添加和删除是有效的。(就像Queue和Stack通常做的那样，迭代操作很少)。数组不是，它需要数组复制操作，这是耗时

Answer 2

双链表(如Java的LinkedList)是一种相当灵活的数据结构，因此使用它作为基础来实现多个数据结构是有意义的。所以如果你想把它看作一个Queue，你可以这样写(我省略了类型参数):

Queue q = new LinkedList();

如果你想使用它作为一个堆栈，你可以这样声明它:

Deque s = new LinkedList();

以此类推。这一切都归结为代码重用，毕竟，当一个类(在本例中是LinkedList)足够时，为什么要为类似的功能实现几个不同的类呢?

Answer 3

基本OOD: Queue, Stack和Deque大致描述了您可以在集合上执行的操作，因此值得作为接口。LinkedList描述了接口的实现和性能特征，因此应该成为一个类。该实现可以(已经)公开为多个接口。对我来说，真正的问题是，"为什么Stack是一个类?"

Answer 4

LinkedList实现了Queue接口，因为您可能希望在某些地方使用链表作为Queue。这意味着以队列作为输入参数的方法也可以处理链表。以下作品

List<String> linkedList = new LinkedList<String>();
linkedList.add("element1");
linkedList.add("element2");
Queue<String> q = (Queue<String>)linkedList; 
q.poll(); //removes and returns element1 from the linkedList

Java有一个单独的类叫做java.util.Stack，它从vector扩展而来，而vector又是一个基于数组的实现。但这是一个线程安全的版本。如果您不担心线程安全，那么您可以使用ArrayDeque作为堆栈。

Answer 5

Queue是一个接口，除了LinkedList还有其他实现。还有一个Stack类

最终，这似乎只是一个武断的决定，底层实现并不重要(IMO)。