Implement a Queue using two Stacks

Problem: Implement a queue using 2 stacks

Solution: The solution involves using one of the stacks as inbox stack. Incoming items are pushed onto this stack. The other stack is used as an outbox. When items need to be dequeued from the Queue and the outbox stack is empty, all the items from the inbox stack are popped and pushed on to the outbox stack. From there they can be popped until the outbox stack is empty. If the outbox is not empty then Dequeue operation is just a simple Pop() on the outbox stack.

The Enqueue and Dequeue methods for the Queue are as follows:
void Enqueue(int item)
{ 
  // all incoming items go on to the inboxStack
  inboxStack.push(item);
}

int Dequeue()
{
  //if the outbox stack has items in it just pop it from there and return
  if(outboxStack.Count > 0)
  {
     return outboxStack.Pop();
  }
  else
  {
     // move all items from the inbox stack to the outbox stack
     while(inboxStack.Count > 0)
     {
        outboxStack.Push(inboxStack.Pop());
     }
     if(outboxStack.Count > 0)
     {
        return outboxStack.Pop();
     }
  }
}

7 comments:

  1. thanks for your explanation

    ReplyDelete
  2. Your else block needs to return an int (outbockStack.Pop). Also you need to handle a pop when both inboxStack and outboxstack are empty

    Great site.

    ReplyDelete
  3. Thanks for pointing out that. I updated the code to return outBoxStack.Pop()

    ReplyDelete
  4. Thanks for the code and explaination :)

    ReplyDelete
  5. Thanks a lot for making this clear :)

    ReplyDelete
  6. it is nice approach

    ReplyDelete