为什么使用两个堆栈来创建一个队列？

如果使用数组实现，我可以看到使用两个堆栈的优点，因为使用数组比堆栈更容易实现堆栈。但是，如果使用链表，优势是什么？将栈弹出到队列中的行为增加了链接列表和数组实现的开销。为什么使用两个堆栈来创建一个队列？

来源

2010-01-12 Tom

谁使用两个堆栈来创建队列？我不太了解情况（对不起（ – helios 2010-01-12 15:42:22

这是实现在函数式编程语言队列单纯的功能性的常用方法（不可变的，但在共享结构）列表（例如Clojure中，哈斯克尔，二郎...）：

用一双名单代表第一个列表中的元素处于FIFO顺序并且第二个列表中的LIFO顺序的队列
通过预先考虑到第二个列表排队到队列
通过取出队列中的第一个元素列表
如果第一个列表为空：反转第二列表，并与它代替第一列表中，并用一个空列表

更换第二列表

（所有的操作除了任何可能的返回值返回新的队列对象）

关键是将一个元素添加到（从）一个纯函数列表的前面是O（1），而反向操作是O（n）在所有出列处被分摊，所以它接近于O（ 1），从而为您提供一个具有不可变数据结构的队列实现。

来源

2010-01-12 16:20:03 liwp

第二步，我相信最后一个单词应该是'list'而不是'queue'，使它像'通过预先考虑第二个列表入队到队列中。] – 2014-05-27 09:41:43

谢谢@LihangLi，修正了！ – liwp 2014-05-27 09:50:12

-2

这是一个很好的学习经验，但不是一个实际的。

来源

2010-01-12 15:43:30

您可以使用两个不可变的堆栈来创建一个不可变的队列。

但是，如果你只是想要一个可变队列，使用两个栈是一个很好的方式，使它比使用链表更慢和更复杂。

来源

2010-01-12 15:44:11

此方法可用于使用两个原子单链表基于堆栈构建lock-free队列，如由Win32提供的：Interlocked Singly Linked Lists。该算法可能如liwp's answer中所述，尽管重新打包步骤（第4项）可以进行一些优化。

无锁数据结构和算法是一个非常令人兴奋的（对我们一些人）编程领域，但它们必须非常小心地使用。在一般情况下，基于锁的算法效率更高。

来源

2010-01-12 17:02:03 atzz

在一个多写入器的单个阅读器的情况下，很容易以高效的无锁方式处理“入队”操作，同样对于出列（无需锁定写入者，并假设一个读取器）如果一个人通过收件箱中的“全部弹出”操作（基本上是一个'Interlocked.Exchange'）开始出列，如果可能有多个读者，最好让他们使用锁定在彼此之间进行仲裁（他们的锁定会'不会影响作家） – supercat 2012-09-25 22:09:01

这是我来这里寻找的解释，有一个好的先生。 – 2017-05-01 14:30:51

为什么使用两个堆栈来创建一个队列？

回答

相关问题