Implement Stack using Two Queues

TechTravelThink picture TechTravelThink · Mar 27, 2009 · Viewed 200.9k times · Source

A similar question was asked earlier there, but the question here is the reverse of it, using two queues as a stack. The question...

Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size).

There should be two versions of the solution.

  • Version A: The stack should be efficient when pushing an item; and
  • Version B: The stack should be efficient when popping an item.

I am interested in the algorithm more than any specific language implementations. However, I welcome solutions expressed in languages which I am familiar (,,,,,).

Answer

Svante picture Svante · Mar 27, 2009

Version A (efficient push):

  • push:
    • enqueue in queue1
  • pop:
    • while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
    • dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Version B (efficient pop):

  • push:
    • enqueue in queue2
    • enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2
  • pop:
    • deqeue from queue1