Why use two stacks to make a queue?

Question

I can see the advantage of using two stacks if an array implementation is used since stacks are more easily implemented using arrays than stacks 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.

Answer 1

There is none that I can see. A linked list makes for a perfectly reasonable queue implementation. Why do you claim there is an advantage?

Answer 2

It's a good learning experience, but not a practical one.

Answer 3

You can make an immutable queue using two immutable stacks.

But, if you just want a mutable queue, using two stacks is a great way to make it slower and more complicated than just using a linked list.

Answer 4

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 queue
• 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.

Answer 5

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.