堆栈和队列，为什么？

为什么和什么时候应该使用堆栈或队列数据结构而不是数组/列表？你能举一个例子说明，如果你使用堆栈或队列，它会更好吗？堆栈和队列，为什么？

来源

2010-01-15 Alon Gubkin

堆栈和队列用数组和列表实现。 – Yada 2010-01-15 21:43:36

您可能想查阅数据结构上的文本。这是所有CS和DP学生的基本要求。 – 2010-05-08 15:49:09

因为它们以比数组和列表更特殊的方式帮助管理数据。

队列是先入先出（FIFO）

堆栈是后进先出（LIFO）

数组和列表是随机接入。它们非常灵活，也很容易腐败。如果您希望将数据作为FIFO或LIFO来管理，最好使用已经实施的那些集合。

来源

2010-01-15 21:44:08

“列表”与“数组”不同时通常意味着链接列表，因此不完全是随机访问。 – Porculus 2010-01-15 21:46:01

@Porculus：取决于环境。 .Net具有通用的List <>集合和1.0以来的ArrayList类，允许通过[]运算符进行随机访问。链表实现被特别命名为LinkedList – 2010-01-15 21:49:16

我会说更简单的接口给他们的实现更多的纬度。总是有一个典型的搜索示例，深度首先通过将队列替换为堆栈，然后再与优先级队列再次变得不同。 – wowest 2010-01-15 22:27:05

当您想要在您的数据结构上实施某种使用模式时。这意味着当你调试一个问题时，你不必怀疑某人是否随机地将一个元素插入列表的中间，搞乱了一些不变量。

来源

2010-01-15 21:43:35

当你想要得到的东西出来的顺序，你把他们在使用的队列中。
当你想要得到的东西出相反的顺序比你把他们在使用堆栈。
无论您何时放入（以及何时不希望它们自动移除），您都可以使用列表获取任何内容。

来源

2010-01-15 21:44:37

这是一个意图问题。堆栈和队列通常使用数组和列表来实现，但是元素的添加和删除更加严格。

来源

2010-01-15 21:44:37

栈或队列是一个逻辑数据结构;它将在具有物理结构（例如列表，阵列，树等）的封面下实现。

如果您愿意，或者利用已经实现的抽象，欢迎您“推出自己的产品”。

来源

2010-01-15 21:45:09 Joe

除了其他人已经提到的使用强制执行之外，还有一个性能问题。当你想从一个数组的开头或一个List（ArrayList）中移除某些东西时，它通常需要O（n）次，但对于一个队列则需要O（1）次。如果有很多元素，这可以产生巨大的差异。

来源

2010-01-15 21:46:16

问题不明确，因为您可以使用数组或链接数据结构表示堆栈或队列的抽象数据类型。

堆栈或队列的链表实现与数组实现之间的区别与任何数组与动态数据结构具有相同的基本折衷。

链接队列/链接堆栈具有灵活，高速的插入/删除和合理的实现，但需要比阵列更多的存储空间。插入/删除在阵列末端便宜，直到用尽空间;队列或堆栈的数组实现需要更多的工作来调整大小，因为您需要将原始数据复制到更大的结构中（或者发生溢出错误）。

来源

2010-01-15 21:49:26 JasonTrue

数组/列表和堆栈/队列不是互斥的概念。事实上，您发现的任何堆栈或队列实现几乎可以肯定地使用阵列或引擎盖下的列表。

数组和列表结构提供了数据如何存储的说明，只要保证结构上基本操作的复杂性即可。

堆栈和队列给出了如何插入或删除元素的高级描述。队列FIFO，堆栈FILO。

例如。如果你正在实现一个消息队列，你将使用一个队列。但是队列本身可以将每条消息存储在一个列表中。 “推送”添加到列表前面的消息，“弹出”列表末尾的消息。

来源

2010-01-15 21:50:03

堆栈和队列是更高级的方式来处理数组本身的集合，该集合本身不会以元素在集合中的行为方式建立任何顺序。

堆栈（LIFO - 后进先出）和队列（FIFO - 先进先出）建立并排序元素插入到集合中并从中移除。

您可以使用数组或链接列表作为存储结构来实现堆栈或队列模式。甚至可以使用这些基本结构创建更复杂的模式，如二叉树或优先级队列，这可能不仅会导致插入和移除元素的顺序，还会在集合中对它们进行排序。

来源

2010-01-15 22:12:20 jmayor

你去过一家自助餐厅吧？看到一堆盘子？当一个干净的盘子被添加到堆栈时，它被放在最上面。当平板被移除时，它会从顶部移除。所以它被称为后进先出（LIFO）。一个计算机堆栈就是这样，除了它包含数字，并且如果你喜欢，你可以从数组或列表中创建一个。（如果堆叠的盘子下面有一个弹簧，他们说你“推”一个到顶部，当你移除一个时，你会“弹出”它。）

在食堂，回去，他们在那里洗碗。他们有一条传送带，在那里他们把盘子一端洗净，然后从另一端排出，顺序相同。这是一个队列或先进先出（FIFO）。如果你愿意的话，你也可以从数组或列表中创建一个。

它们有什么用？那么，假设你有一个树形数据结构（它像木头制成的真正的树，除了它是颠倒的），并且你想写一个程序完全穿过它，以便打印出所有的叶子。

一种方法是做一个深度优先散步。你从树干开始，转到第一个分支，然后转到该分支的第一个分支，依此类推，直到你到达叶子并打印出来。但你如何备份到下一个分支？那么，每次你下了一个分支时，你都会“推”一些信息到你的堆栈中，而当你备份时，将它“弹出”回来，并告诉你下一个分支。这就是你如何跟踪每个点下一步要做哪个分支。

另一种方式是宽度优先散步。从中继线开始，将所有分支从中继线上编号，并将这些号码放入队列中。然后你从另一端取一个数字，转到那个分支，并且对于每个分支从开始，你再次对它们进行编号（与第一个连续）并将它们放入队列中。当你继续这样做时，你将首先访问距离树干1分支的树枝。然后，您将访问距离行李箱2个分支的所有分支，等等。最终你会到树叶上去打印它们。

这些是编程中的两个非常基本的概念。

来源

2010-05-08 15:32:30

我认为堆栈和队列都是内存访问的概念，根据应用需求使用。另一方面，数组和列表是两种内存访问技术，它们用于实现堆栈（LIFO）和队列（FIFO）概念。

来源

2013-02-22 06:21:11

堆栈和队列，为什么？

回答

相关问题