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

Answer 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.