Implement a Queue using two stacks

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/implement-queue-using-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

1. Enqueue 3, 4, 
2. Dequeue 
3. Enqueue 5, 6
4. Dequeue
5. 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