堆栈、队列和链接列表

Question

我最近已经开始学习数据结构，并且刚刚有了自己的linked list实现。

现在我偶然发现了两个新的数据结构：stack和queue。

从我到目前为止学到的

stack是一个只允许从其尾部插入/删除的linked list，并且

queue是一种linked list，它只允许在尾部插入，只允许从头部删除。

我的问题是：

为什么我要使用这两个数据结构而不是允许从任何地方插入和删除的常规linked list？

此外，为什么这两种数据结构被归类为独立的数据结构，而不是“有限访问链接列表”？

Answer 1

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

​

然后，当用户按回按钮时，会弹出顶部的(从尾部移除--用于插入的相同端)，这将给出最后一次访问的站点C。因此，先入(即站点A)和last的概念(最后一个进入的是site，它反过来成为第一个被访问的站点)。

队列也可以被称为FIFO (先到先出)。考虑作业队列的例子。在执行一项工作时，您将(不考虑任何优化算法)首先到达。这使得队列成为一种优秀的数据结构，可以在先到先得的基础上处理作业。

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

抱歉，图像质量很差-我只是在油漆中画出来的。

Answer 2

堆栈基本上是遵循LIFO (最后一个先出)的数据结构。队列是遵循FIFO (先入先出)的队列。

通常，Stacks和Queues可以使用Arrays和Linked Lists实现。

使用Linked List实现Stack的原因是，当您需要一个涉及LAST表单的功能时，您不确定该功能需要多少个元素。因此，您将根据需求动态地使用LinkedList创建节点。

Queues也是如此

之所以两者都是独立的，是因为两者遵循不同的原则，即先入先出和先先出。

Answer 3

链表是一种数据结构，内存中的元素之间有一定的关系，而堆栈和队列是具有特定接口的数据结构，behavior.Stack和队列甚至可以在数组中实现，因此它们是遵循一定规则的数据结构，即堆栈的LIFO和队列的FIFO (它们不仅限于链表，它们还可以在其他数据结构中实现，比如数组它们遵循的行为和规则是什么重要的)。