如果使用数组实现,我可以看到使用两个堆栈的优势,因为使用数组比使用队列更容易实现堆栈。
但是,如果使用链表,则有什么优势?
将堆栈弹出到队列中的行为增加了链表和数组实现的开销。
最佳答案
这是在函数式编程语言中使用具有纯函数性(不可变但共享结构)列表(例如Clojure,Haskell,Erlang ...)的常见方法来实现队列:
使用一对列表来表示一个队列,其中元素在第一个列表中按FIFO顺序在第二个列表中按LIFO顺序
通过添加到第二个列表来排队
通过获取第一个列表的第一个元素从队列中出队
如果第一个列表为空:反转第二个列表并用它替换第一个列表,然后用一个空列表替换第二个列表
(除了所有可能的返回值之外,所有操作都返回新的队列对象)
关键是,向纯函数列表的前面添加元素(从中删除元素)是O(1),而O(n)的反向操作将在所有出队中摊销,因此接近O(1 ),从而为您提供具有不变数据结构的〜O(1)队列实现。
关于list - 为什么要使用两个堆栈进行排队?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2050120/