堆栈和队列,为什么？

Question

为什么以及何时应该使用堆栈或队列数据结构而不是数组/列表？你能否请一个例子说明一个状态,如果你使用堆栈或队列会更好？

Answer 1

你去过一家自助餐厅吧？看到一堆盘子？当将干净的板添加到堆叠中时,将其放在顶部.当移除板时,将其从顶部移除.所以它被称为后进先出(LIFO).计算机堆栈就是这样,除了它包含数字,如果你愿意,你可以从数组或列表中创建一个.(如果一叠盘子下面有一个弹簧,他们会说你"推"一个弹簧在顶部,当你移开一个弹簧时,你将它"弹出"它.这就是那些单词来自的地方.)

在自助餐厅,回去,在那里洗碗.它们有一条传送带,它们将板材放在一端进行清洗,然后它们以相同的顺序从另一端出来.这是一个队列或先进先出(FIFO).如果您愿意,也可以从数组或列表中创建其中一个.

它们有什么用？好吧,假设你有一个树数据结构(它就像一棵真正的木头,除了它是颠倒的),你想写一个程序完全走过它,以便打印出所有的叶子.

一种方法是进行深度优先步行.从树干开始,然后转到第一个分支,然后转到该分支的第一个分支,依此类推,直到找到一个叶子并打印出来.但是你如何备份到下一个分支？好吧,每当你走下一个分支时,你就会"推送"你堆栈中的一些信息,当你备份时,你会"弹出"它,然后它会告诉你下一个分支.这就是你如何跟踪每个点下一个分支.

另一种方式是广度优先行走.从主干开始,对主干上的所有分支进行编号,并将这些数字放入队列中.然后你把一些从另一端,去那个分支,每一个分支脱落的它,你又数点(连续与第一),并把那些在队列中.当你继续这样做时,你将首先访问离树干一分支的树枝.然后你将访问距离行李箱2个分支的所有分支,依此类推.最终你会到达树叶,你可以打印它们.

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

Answer 2

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

队列是先进先出(FIFO)

堆栈是最后一个,先出(LIFO)

数组和列表是随机访问.它们非常灵活,也容易腐败.如果您想将数据作为FIFO或LIFO进行管理,最好使用那些已经实现的集合.

Answer 3

1. 如果您希望按照放入的顺序排除问题,请使用队列.
2. 如果您想以相反的顺序排出内容,请使用堆栈.
3. 当你想要把任何东西拿出来时,使用一个列表,无论你什么时候把它们放进去(当你不希望它们被自动删除时).

Answer 4

当您想在数据结构上强制使用某种使用模式时.这意味着当你调试问题时,你不必怀疑是否有人将一个元素随机插入到列表中间,弄乱了一些不变量.

Answer 5

堆

从根本上说，每当您需要倒档并在恒定时间内获取元素时，请使用堆栈。堆栈遵循 LIFO，它只是一种排列数据的方式。

应用：

1. 在记事本中实现撤消操作。
2. 浏览器后退按钮使用堆栈。

队列：

队列使用先进先出 (FIFO) 原则实现

应用：

1. 在现实生活中，呼叫中心电话系统将使用队列，让人们按顺序呼叫他们，直到服务代表有空。CPU调度，磁盘调度。当多个进程同时需要 CPU 时，会使用各种 CPU 调度算法，这些算法是使用 Queue 数据结构实现的。
2. 在打印假脱机
3. 图中的广度优先搜索
4. 处理实时系统中的中断。中断的处理顺序与它们到达时的顺序相同，先到先得。

Answer 6

除了其他人已经提到的使用实施之外,还存在性能问题.如果要从数组或List(ArrayList)的开头删除某些内容,通常需要O(n)时间,但对于队列,则需要O(1)时间.如果有很多元素,这会产生巨大的差异.

Answer 7

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

Answer 8

数组/列表和堆栈/队列不是互斥的概念.事实上,您找到的任何堆栈或队列实现几乎肯定都在使用数组或列表.

数组和列表结构提供了数据存储方式的描述,并保证了结构上基本操作的复杂性.

堆栈和队列提供了有关如何插入或删除元素的高级描述.队列的FIFO,堆栈的FILO.

例如.如果要实现消息队列,则将使用队列.但是队列本身可以将每个消息存储在列表中."推送"添加到列表前面的消息,"弹出"从列表末尾开始的消息.