Implement a Queue using two stacks

Problem
Implement a Queue using two stacks.

Solution
Logic :

We’ll implement a FIFO queue using two stacks.Lets call the stacks Instack and Outstack.

Enqueue:

An element is inserted in the queue by pushing it into the Instack.

** Dequeue:**

An element is extracted from the queue by popping it from the Outstack.
If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order.

Example

Enqueue 3, 4,
Dequeue
Enqueue 5, 6
Dequeue
Dequeue

At step 1, InStack={4, 3} , OutStack = {}. Top in stack points to 4.
At step 2, InStack={} , OutStack{3,4}, note that order is reversed. Top points to 3. Now, we pop the item, hence we pop out 3. OutStack={4}
At Step 3, InStack={6, 5}, OutStack={4}
At Step 4, InStack={6, 5}, OutStack={}, 4 is popped out of OutStack
At Step 5, again, InStack={}, OutStack={5,6} = OutStack{6} , and 5 is popped out.

Stack interface

public interface Stack {  
        void push( Object x );  
        Object pop( );  
        Object top( );  
        boolean isEmpty( );  
        void makeEmpty( );  
}

Now we come to actual class that implements a Queue using two stacks.

Code(Java):

public class StackQueue {  
  
       ArrayStack inStack = new ArrayStack();  
       ArrayStack outStack = new ArrayStack();  
  
  
       public void enqueue(Object value)  
       {  
               inStack.push(value);  
       }  
       public Object dequeue()  
       {  
               if(outStack.isEmpty())  
               {  
                       while( ! inStack.isEmpty())  
                       {  
                               outStack.push(inStack.pop());  
                       }  
               }  
               return outStack.pop();  
       }  
  
  
       public static void main(String\[\] args)  
       {  
               stackQueue queue = new stackQueue();  
               queue.enqueue(new String("first"));  
               queue.enqueue(new String("second"));  
               queue.enqueue(new String("third"));  
               queue.enqueue(new String("fourth"));  
               queue.enqueue(new String("fifth"));  
               System.out.println("1. " + queue.dequeue());  
               System.out.println("2. " + queue.dequeue());  
               System.out.println("3. " + queue.dequeue());  
               System.out.println("4. " + queue.dequeue());  
               System.out.println("5. " + queue.dequeue());  
       }  
}

But can we implement queue, using 1 stack only?
Answer is yes, We can have 1 primary stack. We can get another temporary stack using call stack of recursion.

Steps remain the same:

You need to transfer elements from one stack to another temporary stack, to reverse their order.
Then push the new element to be inserted, onto the temporary stack
Then transfer the elements back to the original stack
The new element will be on the bottom of the stack, and the oldest element is on top (first to be popped)

Here is the code(java):

public class SimulatedQueue<E> {  
    private java.util.Stack<E> stack = new java.util.Stack<E>();  
  
    public void insert(E elem) {  
        if (!stack.empty()) {  
            E topElem = stack.pop();  
            insert(elem);  
            stack.push(topElem);  
        }  
        else  
            stack.push(elem);  
    }  
  
    public E remove() {  
        return stack.pop();  
    }  
}

Source

http://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks

Example

See also