Java - LinkedList的push()和pop()方法是否意味着它是一个栈而不是队列？

Question

在我的数据结构课上，我学到一个 LinkedList 是一个队列。就像现实生活中的一条线，第一个进入队列的人将是第一个离开队列的人。很有道理。如下所示，ListedList 实现了一个 Queue，它具有 FIFO（先进先出）过程。

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

将元素推送到由此列表表示的堆栈上。换句话说，在此列表的前面插入元素。 pop()

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

那不是队列。那是一个堆栈。通过 push 添加到 LinkedList 中的第一个元素直到每个添加在它之后的元素都被弹出后，才能通过 pop 访问。

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

简而言之：为什么LinkedList的push和pop表明它像堆栈一样工作，而实际上LinkedList实现的是Queue。

- Hatefiend

---

一个列表既不是固有的栈也不是队列，但它可以被用作任意一种。 - chrylis -cautiouslyoptimistic-

Answer 1

Push()和pop()通常用于与Stacks（在这种情况下更具体地说是Deque）相关的操作，因此当您使用这些方法时，应该期望您的LinkedList按照这种方式工作。 如果您希望您的LinkedList作为Queue工作（它实现了Queue接口），则您想要使用的方法（如文档中所述）是add()和remove()。

请参阅LinkedList文档。

- Sith

Answer 2

你提到的方法（push()和pop()）来自Deque接口，该接口也由LinkedList实现。 Deque的Javadoc说明如下：

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

换句话说，它不同于普通队列。

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

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

这样做，你只能把 queue 当作一个队列来使用。这个接口定义了许多方法，其中包括 add() 和 remove()，用于向队列中添加和删除元素。

- Magnilex

---

哦，我忘记了你可以这样做：Interf x = new ClassWhoImplementsInterf();。如果你这样做：Apple x = new SuperApple();会发生什么呢？（假设SuperApple是Apple的子类）在这种情况下，你只能使用Apple中的方法吗？或者这个技巧只适用于接口？ - Hatefiend

它基本上与类、抽象或具体的方式相同。虽然这将是完全不同的讨论，如果您想要进一步的解释，应该作为另一个问题提出。 - Magnilex

Answer 3

从类图可以看出，LinkedList 既是 List，也是 Deque。 Deque 接口定义了“双端队列”抽象，可以同时作为FIFO(即堆栈)或LIFO(即Queue)。来自javadocs的描述：

Deques 也可以用作LIFO（后进先出）堆栈。与遗留的 Stack 类相比，应优先使用此接口。当deque被用作stack时，元素从deque的开头被推送和弹出。

push 和 pop 操作来自于 Deque API 的 FIFO 方面。

---

LinkedList - push(), pop() 暗示它是一个栈，而不是队列？

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

• 您是正确的，push() 和 pop() 暗示了一个栈。
• 然而，只有缺少 add() 和 remove() 才会暗示不是一个队列。

FIFO 和 LIFO 功能并不互斥。

- Stephen C

Answer 4

LinkedList 是一个双端队列（Deque），因此您可以从两端添加和删除元素。它还实现了List，这使您可以修改中间的部分。

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

- fabian

---

“pop”和“push”这两个术语是专门用于栈吗？我不想给我的数据结构命名一个叫做“pop”的方法，然后突然意识到约定规定“pop”应该是一种删除第一个元素的方法或者其他什么。 - Hatefiend

据我所知，push/pop 仅用于堆栈（或类似堆栈的行为）。 - fabian

Answer 5

单向链表非常适合作为栈，但是作为队列则不太好。只有双向链表才能很好地作为队列。

单向链表只允许在头部进行O(1)的插入和删除操作（即栈操作）。

要找到尾元素需要遍历整个链表，时间复杂度为O(n)（除非它是双根的）。删除尾元素需要修改倒数第二个元素。为了使这个过程更有效率，你需要使用双向链表（仅双根的链表无法做到O(1)）。

当然，任何双向链表都可以从单向链表继承作为栈的功能。你仍然可以在O(1)的时间内访问头部。因此，某些东西既可以是队列也可以是栈，并不存在矛盾之处。

请注意，在Java中，由于开销问题，LinkedList几乎总是一个坏主意。无论是用于栈还是队列，都不应该使用LinkedList，而应该始终优先选择基于数组的实现，除非你经常在大型列表的中间插入或删除对象。（真的，请对LinkedList进行基准测试——它非常慢且占用内存）。

- Has QUIT--Anony-Mousse