list - 为什么要使用两个堆栈进行排队？

Question

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

Answer 1

这是在函数式编程语言中使用具有纯函数性（不可变但共享结构）列表（例如Clojure，Haskell，Erlang ...）的常见方法来实现队列：


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


（除了所有可能的返回值之外，所有操作都返回新的队列对象）

关键是，向纯函数列表的前面添加元素（从中删除元素）是O（1），而O（n）的反向操作将在所有出队中摊销，因此接近O（1 ），从而为您提供具有不变数据结构的〜O（1）队列实现。