CODEWITHSUNDEEP
listabstract-data-type
Tom
Tom

Reputation: 6971

Why use two stacks to make a queue?

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.

Upvotes: 25

Views: 11927

Answers (4)

liwp
liwp

Reputation: 6926

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.

Upvotes: 32

atzz
atzz

Reputation: 18010

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.

Upvotes: 8

Craig Gidney
Craig Gidney

Reputation: 18266

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.

Upvotes: 3

Dean J
Dean J

Reputation: 40298

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

Upvotes: -3

Related Questions