# Queue using Stacks!

### 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.

## 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!