为什么要使用两个堆栈来建立队列？

Question

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

Answer 1

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

• 使用一对列表来表示队列,其中元素在第一个列表中以FIFO顺序排列,在第二个列表中以LIFO顺序排列
• 通过前置到第二个列表排队到队列
• 通过获取第一个列表的第一个元素从队列中出队
• 如果第一个列表为空:反转第二个列表并用它替换第一个列表,并用空列表替换第二个列表

(除了任何可能的返回值之外,所有操作都返回新的队列对象)

关键是在纯函数列表的前面添加(删除)元素是O(1),并且O(n)的反向操作在所有出列上分摊,因此它接近于O(1) ),从而为您提供具有不可变数据结构的~O(1)队列实现.

Answer 2

此方法可用于使用两个基于原子单链接列表的堆栈构建无锁队列,例如由Win32:Interlocked Singly Linked Lists提供.该算法可以如liwp的回答中所述,尽管重新包装步骤(子弹4)可以稍微优化一下.

无锁数据结构和算法是一个非常令人兴奋的(对我们中的一些人)编程领域,但必须非常小心地使用它们.在一般情况下,基于锁的算法更有效.