为什么要使用两个堆栈来排队? [英] Why use two stacks to make a queue?

问题描述

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

I can see the advantage of using two stacks if an array implementation is used since stacks are more easily implemented using arrays than queues are. But if linked-lists are used, what is the advantage? The act of popping the stack onto the queue increases overhead for both linked-list and array implementations.

推荐答案

这是在函数编程语言中使用纯函数(不可变，但共享结构)列表(例如Clojure，Haskell，Erlang ...)来实现队列的常用方法. ):

It's a common way to implement a queue in functional programming languages with purely functional (immutable, but sharing structure) lists (e.g. Clojure, Haskell, Erlang...):

• 使用一对列表表示一个队列，其中元素在第一个列表中按FIFO顺序排列，在第二个列表中按LIFO顺序排列
• 通过添加到第二个列表来排队进入队列
• 通过获取第一个列表的第一个元素从队列中退出
• 如果第一个列表为空:反转第二个列表并用它替换第一个列表，然后用一个空列表替换第二个列表

(除了所有可能的返回值之外，所有操作均返回新的队列对象)

(all operations return the new queue object in addition to any possible return values)

问题在于，向纯函数列表的前面添加元素(从中删除元素)是O(1)，而O(n)的反向操作在所有出队中均摊销，因此接近O(1)，从而为您提供具有不变数据结构的〜O(1)队列实现.

The point is that adding (removing) an element to (from) the front of a purely functional list is O(1) and the reverse operation which is O(n) is amortised over all the dequeues, so it's close to O(1), thereby giving you a ~O(1) queue implementation with immutable data structures.

这篇关于为什么要使用两个堆栈来排队?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！