Posted on 12 March 2010
Recently, a casual conversation in the office brought me to an observation, most
of the candidates we had interviewed had flunked the question,
How do you implement a Queue using two Stack's? Hence, I take today’s opportunity to
discuss the implementation for the problem stated above.
Let’s consider two stacks called A and B. A stream of numbers is coming in as part of the
enqueue function. The stream is numbered as 1, 2, 3, and so on for ease of understanding.
Say, there are three
enqueue calls with numbers 1, 2 and 3 in the respective order. Store
them in Stack A on top of each other. Thus the stacks should look like,
Now, say I call a
dequeue. We now need to get 1 back and return it. To achieve the same
pop all numbers from stack A and push them to stack B. Thus the stacks would now look like,
Return 1, and the stacks are,
Now we have more
enqueue calls for say up to 7. Push all of these to stack A. Stacks would look like,
Now for every
dequeue call return elements from stack B till it gets empty.
Once stack B is empty, on the next
dequeue call, pop all elements from stack A and push to stack B. Stacks are,
Continue this way and we now have a queue implementation with least amount of overhead.
Hope this helps!