可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):

问题:

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.

回答1:

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...):

use a pair of lists to represent a queue where elements are in FIFO order in the first list and in LIFO order in the second list
enqueue to the queue by prepending to the second list
dequeue from the queue by taking the first element of the first list
if the first list is empty: reverse the second list and replace the first list with it, and replace the second list with an empty list

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

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.

回答2:

This approach may be used to build a lock-free queue using two atomic single-linked list based stacks, such as provided by Win32: Interlocked Singly Linked Lists. The algorithm could be as described in liwp's answer, though the repacking step (bullet 4) can be optimized a bit.

Lock-free data structures and algorithms is a very exciting (to some of us) area of programming, but they must be used very carefully. In a general situation, lock-based algorithms are more efficient.