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.

Solution

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!