<分区>
Possible Duplicate:
Why use two stacks to make a queue?
我收到了一道作业题，要求我使用两个堆栈实现一个队列。我的问题不是怎么做，而是为什么要这样做？我不是计算机背景的，我试图找到这个问题的答案，但真的找不到为什么要这样做？我想你们这些专家可以帮助我理解实现这样的事情有什么好处。我找到了一篇相关文章Why use two stacks to make a queue?说到这里，但想知道还有没有什么。
<分区>
Possible Duplicate:
Why use two stacks to make a queue?
我收到了一道作业题，要求我使用两个堆栈实现一个队列。我的问题不是怎么做，而是为什么要这样做？我不是计算机背景的，我试图找到这个问题的答案，但真的找不到为什么要这样做？我想你们这些专家可以帮助我理解实现这样的事情有什么好处。我找到了一篇相关文章Why use two stacks to make a queue?说到这里，但想知道还有没有什么。
最佳答案
这样做有几个很好的理由。
首先，一些函数式编程语言(如 Haskell、ML 或 Lisp)支持将列表作为内置类型。列表通常表示为单个前向链接列表，这意味着它们支持 O(1) 前置但 O(n) 连接。在这样的语言中，创建堆栈非常容易 - 您只需在列表前添加以推送和删除要弹出的第一个元素。由于内部实现，它在 O(1) 时间内运行。如果您尝试使用此类列表创建队列，则入队将花费 O(n) 时间，因为您必须添加到不存储指向最后一个元素的指针的单链表的末尾。另一方面，如果您使用两个堆栈(或更多；Hood-Melville queue 使用六个!)实现队列，那么即使您在您的语言中只有堆栈，也可以分摊 O(1) 入队和出队。尽管已经设计出更高级的数据结构来支持纯功能队列和列表(例如 2-3 finger tree )，但双堆栈结构在许多应用程序中仍然非常有用。
除此之外，在某些情况下，您可能希望使用特殊的堆栈来实现队列以获得额外的功能。例如，您可以 augment a stack data structure支持 O(1) 查找最小值/查找最大值。如果你有这样的堆栈，那么你可以 use the two-stack construction to make a queue that also has O(1) find-min/find-max .尝试直接解决这个问题要困难得多(查看我的 considerably more complex construction 以使用这些属性创建队列!)
最后，从理论的角度知道一个队列可以用两个栈来模拟是很有趣的。在可计算性理论中，一个two-stack pushdown automaton是一种理论上的计算设备，其功率相当于图灵机。 queue automaton是一个类似的结构，它使用一个队列而不是两个堆栈。因为我们知道您可以用两个堆栈模拟队列，所以您可以立即证明队列自动机至少与图灵机一样强大，因此队列自动机是图灵完备的。
希望这对您有所帮助!
关于algorithm - 为什么我们做 "implement a queue using 2 stacks"？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7395400/