sma*_*ape 11 algorithm queue stack data-structures
可能重复:
为什么要使用两个堆栈来建立队列？
我得到了这个赋值问题,要求我使用两个堆栈实现一个队列.我的问题不是如何做到,而是为什么这样做？我不是来自计算机背景,我试图找到答案,但无法真正找到原因吗？我认为你的专家可以帮助我理解实现这样一个东西有什么好处.我发现了一篇相关文章为什么要使用两个堆栈来建立队列？谈论这个,但想知道是否还有更多.
tem*_*def 15
这样做有几个很好的理由.
首先,一些函数式编程语言(如Haskell,ML或Lisp)支持列表作为内置类型.列表通常表示为单个前向链接列表,这意味着它们支持O(1)前置但O(n)连接.在这样的语言中,制作一个堆栈非常容易 - 你只需要一个列表就可以将第一个元素推送到pop中.由于内部实现,这在O(1)时间内运行.如果您尝试使用此类列表创建队列,则enqueue将花费O(n)时间,因为您必须添加到单个链接列表的末尾,该列表不存储指向最后一个元素的指针.另一方面,如果使用两个堆栈(或更多; Hood-Melville队列使用六个!)来实现队列,那么即使您只有您的语言堆栈,也可以分摊O(1)入队和出队.尽管已经设计了更高级的数据结构来支持纯功能队列和列表(例如2-3指树),但是在许多应用中,双栈结构仍然非常有用.
除此之外,在某些情况下,您可能希望使用特殊堆栈来实现队列以获得额外的功能.例如,您可以扩充堆栈数据结构以支持O(1)find-min/find-max.如果你有这样的堆栈,那么你可以使用双栈结构来创建一个也有O(1)find-min/find-max的队列.试图直接解决这个问题要困难得多(查看我的更复杂的构造,以便使用这些属性建立队列!)
最后,从理论角度来看,知道可以使用两个堆栈模拟队列是很有趣的.在可计算性理论中,双栈下推自动机是一种理论计算设备,其功率相当于图灵机.甲队列自动机是一种使用队列,而不是两个堆叠的类似的结构.因为我们知道您可以模拟具有两个堆栈的队列,所以您可以立即证明队列自动机至少与图灵机一样强大,因此队列自动机是图灵完备的.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
2273 次 |
| 最近记录： |