链表和队列有什么区别？

Question

我是数据结构的新手，似乎两种数据结构都有更多的相似之处。

在这个答案中，它说界面有所不同。请解释一下。

Answer 1

队列是任何“ FIFO = 先进先出”的数据结构。这是一个等待名单。（在英国，这个词用在普通对话中……你“在队列中等待”而不是“排队等候”。）

堆栈是任何“ LIFO = 后进先出”的数据结构。这是一个下推的堆栈，就像自助餐厅里的一堆菜肴一样。

链表是任一此类结构的可能实现。它由包含指向列表中相邻节点的指针的节点组成。

然而，还有许多其他的实现。各种“树”也可以用来实现队列和堆栈。普通数组可以做到这一点，尽管数组当然不能“增长”。

理想情况下，现在，您只需使用您最喜欢的语言中的适当“容器类”并了解它的实际实现方式即可。“你知道它有效，所以你不在乎如何。” 此类事情的实际实施可能是一项学术活动。

Answer 2

我和你有同样的疑问！这是我发现的：

\n

队列本质上只是比链接列表更具限制性。例如，在 LinkedList 中，您可以使用 方法.add(int index, Object obj)，但如果您尝试使用 Queue 接口执行此操作，则 \xe2\x80\x99 将收到错误，因为使用 Queue 只能在尾部添加元素。类似地，在 LinkedList 中，您可以使用.remove(int index)as well .remove(Object obj)，但尝试对 Queue 执行此操作将导致错误，因为您只能从头部删除对象。因此，本质上，队列在可使用的方法方面的选择较少。（可能不止这些，但 \xe2\x80\x99 是与我最相关的。）

\n

两者之间有一些相似之处。例如，它们都有该.poll()方法，并且结果是相同的：从 Object 中删除 head 元素。

\n

这里有一些链接，您可以在其中比较两者的方法（滚动到每个页面的底部可以查看全部方法，您\xe2\x80\x99将立即看到 LinkedList 还有更多）：

\n

https://www.geeksforgeeks.org/linked-list-in-java/（链接列表）\n https://www.geeksforgeeks.org/queue-interface-java/（队列）

\n

Answer 3

列表只是事物的列表（项目、对象等等）。例如，您在学期中修读的课程列表。您正在听的歌曲列表。本页上此问题的答案列表。没有与列表关联的顺序。您可以将项目添加到列表中的任何位置，也可以从列表中的任何位置删除项目，这不会更改列表的定义。它只是一组相似（或不那么相似）的项目。

现在考虑站在 ATM 机或银行出纳员前面的人员名单。该列表必须遵守特定的顺序。队列（列表）中的第一个人将是第一个被服务的人（并且将是第一个离开此列表的人）。新进来的人将作为队列中的最后一个人，在他前面的每个人都得到服务后才会得到服务。名单中间的人不应该插队。这是队列的示例。您还可以猜测优先队列是什么（想想办理登机手续时有银卡和金卡会员的航空公司）。

我希望这能解释其中的差异。

Answer 4

链接列表是节点列表。每个节点包含一个地址字段，该地址字段保存其下一个节点的地址。这种结构的原因是从它的第一个节点到最后一个节点遍历列表。这种类型的结构称为单链表。链表也可以双向链接，在这种结构中，一个节点将有两个地址字段，其中一个字段将存储其前一个节点的地址，一个地址将保存其下一个节点的地址。链表最重要的一点是它的第一个节点地址必须存储在一个地址变量中，以便我们可以随时遍历链表。

但是 Queue 可以是一个链表或一个节点数组。在列表中，可以在任何位置插入节点。但是在队列中，必须在列表的开头插入一个新节点。队列工作在先进先出的基础上，即先进先出。因此，当您在队列上使用 pop 命令时，如果它是一个链接列表，它必须删除列表的最后一个节点并返回最后一个节点的值。因此，队列也可以是一个列表，但具有基于 FIFO 的原则。

您将在网上获得更多信息。正确阅读并尝试理解差异。

Answer 5

在 Java（可能还有其他语言）中，LinkedList 实现了 Queue 接口。所以从本质上来说，LinkedList就是一个 Queue；它具有队列的所有功能，甚至更多。请记住，队列不是链接列表，因为链接列表是在队列上构建和扩展的。

看看这个：