Question: 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();
}
}
}