Create a Queue from two Stacks
Solution:
Here we will be using stack1 to store the items as we Insert items in to it and the second stack will be used to rearrange the items as it should be when we use the Queue (FIFO).
We do this by looping through each item in stack1 and pop it and push it to stack2. But we do this only if there are no more items in stack2. In other words we don't shuffle every time we dequeue, instead we pop the top item from stack2 when asked which has the old elements at the top. But if there are no more items left in our stack2, then we will shuffle items from stack1 to stack2 again.
Therefore, at any given point, stack1 will be used as a temp storage while stack2 has all the items as they should be.
class QueueFromTwoStack {
Stack stack1 = new Stack();
Stack stack2 = new Stack();
public void Enqueue(int num) {
stack1.Push(num);
}
public int Dequeue() {
if(stack2.Count == 0)
while(stack1.Count !=0) {
stack2.Push(stack1.Pop());
}
return (stack2.Count == 0)? -1: (int)stack2.Pop();
}
}