Queue Using Stacks

Question: How would you use stacks to implement a queue?

Answer: So how could we go about doing this? What if we used two stacks and used one as the incoming stack and the other as the outgoing stack? A queue is a FIFO structure, so when we enqueue something, we need to make sure that it does not get popped off before something that was already there. Similarly, when we dequeue something, we have to make sure that elements that were inserted earlier get ejected first.

What’s better than some code!

Stack in;
Stack out;
void enqueue( int value ) {
    while( !out.isEmpty() ) {
        in.push( out.pop() );
    in.push( value );

int dequeue() {
    while( !in.isEmpty() ) {
        out.push( in.pop() );
    return out.pop();

Isn’t that cool? Help share this on Twitter!

If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:

Book Cover

3 Responses

  1. Phani says:

    AW has shown a more efficient solution than the published one!

  2. kumarm says:

    I have a solution on this.

    When we insert elements on stacks, indexex are maintained. Let a, b,c are inserted in stack in that order so that c is last element with index 3 , b having indes 2 and a having index 1. While poping out the element we can reverse the indexes i.e. a is having index 3, bis having 2 and c having 1 and then do the operation.

    It can be implemented with single stack….

    In case anypne disagree please let me know..!!!

  3. AW says:

    push(in, x);

    while(!empty(in)) push(out, pop(in));

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>