栈、队列和链表

Question

我最近开始学习数据结构(Data Structures)，并且刚刚实现了自己的链表(linked list)。

现在我遇到了两种新的数据结构：栈(stack)和队列(queue)。
根据我目前所学：
栈是一种只允许从末尾插入/删除的链表，
而队列是一种只允许从头插入和从头删除的链表。

我的问题是：
为什么我要使用这两个数据结构，而不是允许从任何位置插入和删除的常规链表？
此外，为什么将这两个数据结构分类为独立的数据结构，而不是"受限访问链表(limited access linked lists)"？

- Hamed Khaled

---

栈和队列是基本的数据结构抽象。它们不一定要使用链表来实现。栈和队列分别代表我们在日常生活中想要的两个属性，FILO和FIFO。 - Jason Hu

Answer 1

栈和队列各有存在的原因。 栈是一种FILO(先进后出)或LIFO(两种方式)数据结构，可以使用数组、链表或其他形式来实现。考虑浏览器历史记录。您导航到站点A->然后B->然后C->D。随着用户向前移动，您首先推送(插入尾部)网站列表。这确保当前站点始终位于堆栈顶部。

然后当用户点击返回按钮时，您从顶部弹出(从尾部移除-用于插入相同的末端)，这会给出最后访问的站点-C。因此，"先进先出"的概念就浮现了出来，其中第一个元素(即站点A)被赋予了“先进”的属性，而最后一个进入的元素(即站点D)则成为第一个弹出的元素，即具有“后出”的属性。

对于队列来说，也可以这么说，它是FIFO（先进先出）的。考虑作业队列的例子。在执行作业时，您会(不考虑任何优化算法)首先服务于最先到达的那一个。这使得队列成为一种处理作业的优秀数据结构，可以按先来先服务的原则进行处理。

在这两种情况下，您都不希望在任何索引处任意删除或插入元素。否则，将导致不良行为。因此，需要使用栈/队列。我再次强调，可以通过对链接列表施加限制来实现堆栈/队列。

抱歉图像质量差 - 我只是用画图工具绘制的。

- Slartibartfast

---

好的例子。我有一个问题。 栈是一种FILO（先进后出）或LIFO（两者都可以）数据结构，可以使用数组实现如果使用数组实现队列，则推入复杂度将高于链表。 - Alizain Prasla

基于队列和栈的实现，推入时间相似。不同之处在于从开头还是结尾删除项目所需的时间。一些语言（如JavaScript）内置了从堆栈（pop）和队列（shift）中删除项目的方法。在https://jsfiddle.net/chechs/b9Lfu2do/15/上创建了一个小工具，显示了Chrome和Opera在这两个操作中的巨大时间差异；Firefox和Safari仍然需要更长的时间来进行移位操作，但不像Chrome和Opera那样明显。您可以尝试使用`push`与`pop`来检查推入复杂性。 - Slartibartfast

Answer 2

堆栈基本上是一种遵循LIFO（后进先出）的数据结构。队列是一种遵循FIFO（先进先出）的数据结构。

通常，可以使用数组和链表来实现堆栈和队列。

使用链表实现堆栈的原因是当您需要使用后进先出形式的功能并且不确定该功能需要多少个元素时，您将使用LinkedList根据要求动态创建节点。

队列也是同样的道理。

两者独立的原因是它们都遵循不同的原则，即LIFO和FIFO。

- yyk

Answer 3

链表是一种具有内存中元素之间特定关系的数据结构，而栈和队列是具有特定接口和行为的数据结构。栈和队列甚至可以在数组中实现，因此它们是遵循某种规则的数据结构，例如栈遵循后进先出（LIFO）规则，队列遵循先进先出（FIFO）规则(它们不仅限于链表，也可以在其他数据结构如数组中实现，重要的是它们所遵循的行为和规则)。

- Rapeti charan