Java - LinkedList push（）pop（）意味着它是一个堆栈，而不是一个队列？

在我的数据结构类中，我了解到LinkedList是一个队列。就像现实生活中的一条线一样，进入该线的第一个人将成为第一个离开的人。说得通。如下所示，ListedList实现了具有FIFO（先进先出）过程的Queue。Java - LinkedList push（）pop（）意味着它是一个堆栈，而不是一个队列？

但是，如果你看一下描述的方法push(E)和pop()，他们读如下：

推（E）

将元素推入此列表所表示的堆栈。换句话说，将该元素插入此列表的前面。

弹出（）

从此列表所表示的堆栈弹出一个元素。换句话说，删除并返回此列表的第一个元素。

这是....不是队列。这是一个堆栈。通过push进入LinkedList的第一个元素不能被pop访问，直到每个元素在pop()之后添加为止。

这是为什么？我得到LinkedLists既可以作为堆栈使用（如果你只使用addFirst(E)和removeFirst()），并可以用作队列（如果你只使用addFirst(E)和removeLast()或反之亦然），那么为什么它是这样呢？我觉得pop()应该删除并返回最后一个元素，或者push(E)应该在LinkedList的末尾添加元素。那么它会更有意义。

TLDR：为什么LinkedList的push和pop意味着它可以作为一个堆栈时LinkedList实际实现Queue来代替。

来源

2016-09-18 Hatefiend

列表既不是堆栈也不是队列，但它可以用作任何一个。 – chrylis

Push()和pop()是由与Stacks惯例操作（Deque，更具体地说是在这种情况下），这就是为什么你应该期待您的LinkedList到工作方式，当你使用这些方法。如果您希望LinkedList以Queue的方式工作（它实现Queue接口），您要使用的方法（如文档中所述）为add()和remove()。

See LinkedList Documentation

来源

2016-09-18 08:45:27 Sith

LinkedList是一个双端队列（Deque），因此你可以添加和删除从两端元件。它也实现List，它允许你在中间修改零件。

这并不改变它可以通过使用add/offer和poll/remove作为队列使用的事实。

来源

2016-09-18 08:34:20 fabian

“流行”和“推”条款是专门用于堆栈吗？我不想永远命名我的一个数据结构的方法'pop'，然后突然意识到'convention'应该是一个删除第一个元素的方法。 – Hatefiend

@Hatefiend AFAIK push/pop仅用于堆栈（或类似堆栈的行为）。 – fabian

您提到的方法（push()和pop()）来自Deque接口，该接口也由LinkedList执行。 Javadoc为Deque指出：

线性集合，支持在两端插入和移除元素。名称deque是“双端队列”的缩写，通常发音为“deck”。大多数Deque实现对它们可能包含的元素的数量没有固定限制，但是此接口支持容量限制的deques以及没有固定大小限制的deque。

换句话说，它与普通队列不一样。

如果你真的想用LinkedList作为一个队列，你应该将变量分配给该接口：

Queue<String> queue = new LinkedList<>();

这样做，你只能够使用queue的，好了，排队。除其他方法外，此接口定义了用于从队列中添加和移除元素的add()和remove()。

来源

2016-09-18 08:36:38 Magnilex

Ohhhh我忘了你可以做'Interf x = new ClassWhoImplementsInterf（）;'。当你做'Apple x = new SuperApple（）;'时会发生什么？（假设'SuperApple'是'Apple'的子类）在这种情况下，你只能使用'Apple'的方法，或者这种方法只适用于接口？ – Hatefiend

它基本上以类，抽象或具体的方式工作。虽然这将是一个完全不同的讨论，如果你想进一步解释，可能应该作为一个不同的问题。 – Magnilex

你可以从类图LinkedList既是List和一个Deque看到。

Deque接口定义了一个“双端队列”抽象，它可以同时作为FIFO（即堆栈）或LIFO（即Queue）......。从javadocs：

Deques也可以用作LIFO（后进先出）堆栈。此接口应优先使用传统的Stack类。当一个deque用作堆栈时，元素会从deque的开始处被推入并弹出。

的push和pop操作COM从Deque API的FIFO的一面。

LinkedList - push()，pop()意味着这是一个堆栈，而不是一个队列？

从逻辑上讲，这是不正确的。

你是对的，push()和pop()意味着一个堆栈。
然而，add()仅缺席和remove()不会暗示的队列。

FIFO和LIFO功能并不相互排斥。

来源

2016-09-18 08:48:25

一个单链表使得一个优秀的堆栈，但只有一个非常糟糕的队列。只有双链接，双重链接的列表非常适合作为队列。

单链表允许仅在头部插入和移除O（1）（即堆栈操作）。

查找尾部元素需要遍历O（n）中的所有列表（除非它是双重根）。删除尾部需要您修改倒数第二个元素。为了达到这个效率，你需要一个双链表（双重链表不足以使得O（1））

但是当然任何双链表都继承了从单一链接列表。您仍然可以访问O（1）中的头部。所以在队列和堆栈没有矛盾。

请注意，在Java的现实中，由于开销，LinkedList几乎总是一个坏主意。无论是堆栈还是队列，都应该使用它，但是您应该更喜欢基于阵列的实现，除非您经常插入或移除大型列表的中间中的对象。（真的，基准LinkedList - 这是非常缓慢和内存昂贵）。

来源

2016-09-18 12:48:27

Java - LinkedList push（）pop（）意味着它是一个堆栈，而不是一个队列？

回答

相关问题