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!