Implementing Queue using Stack

We have to use only the operations that are supported by Stack ADT*. The methods supported by stack are push(), pop(), and isEmpty(). We have to use only these three operations to implement a Queue. The Queue data structure should primarily support enqueue() and dequeue() operations.

To quickly refresh Stacks, and Queues knowledge;
Stacks are the LIFO (Last-In-First-Out) list in which the last element inserted is the first to be removed.(Example: stack of plates kept in a cafeteria)
Queue is a FIFO ( First-In-First-Out) list in which the first element inserted is the first to be removed (Example: Line of people waiting for a ticket at any counter)

The trick here is to use two stacks, one for adding the data(push-stack), and one for removing the data(pop-stack). So we have to implement enqueue() and dequeue() operations in terms of only stack methods.

enqueue():
First check if the pop-stack is empty. If it is empty, we directly push the element onto the push-stack.
Otherwise We pop all the elements from the pop-stack one-by-one and push them onto the push-stack. Then we push the current element.

dequeue():
First check if the push-stack is empty. If it is empty, we directly pop the element from the pop-stack.
Otherwise we pop all the element from the push-stack one-by-one and push them onto the pop-stack.
Then we pop the element from the pop-stack and return that.

Let us understand this logic with an example. Let us represent the stacks from left to right assuming that the rightmost element is top.

The following table explains a series of enqueue() and dequeue() operations and the status of push and pop-stacks.

Observe that order of the removed elements. They are in the order of insertion. Performing a series of only enqueue/dequeue operations does not cause any performance problems, as it does not require the elements to be copied between the two stacks.

At any point of time, only one stack is occupied
The worst case occurs when enqueue, and dequeue operations are performed alternatively.

*Abstract Data type: A specification which gives the methods that should be supported by a data structure.

Following is the implementation in Java. I have omitted some exception handling to keep the code simple and clear.

/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 8/23/13
 * Time: 1:20 PM
 * To change this template use File | Settings | File Templates.
 */
import java.util.Stack;
public class Main {
    public static void main(String[] args)
    {
        Q2Stacks intQueue = new Q2Stacks();

        intQueue.enqueue(1);
        intQueue.enqueue(2);
        System.out.println(intQueue.dequeue());
        intQueue.enqueue(3);
        System.out.println(intQueue.dequeue());
        intQueue.enqueue(4);
        intQueue.enqueue(5);
        System.out.println(intQueue.dequeue());
        intQueue.enqueue(6);
        System.out.println(intQueue.dequeue());
        System.out.println(intQueue.dequeue());
        System.out.println(intQueue.dequeue());

    }
    static class Q2Stacks
    {
        private Stack<Integer> pushStack;
        private Stack<Integer> popStack;

        public Q2Stacks()
        {
            pushStack = new Stack<Integer>();
            popStack = new Stack<Integer>();
        }

        public void enqueue(int data)
        {
            if( !popStack.empty() )
            {
                while( !popStack.empty())
                {
                    pushStack.push(popStack.pop());
                }
            }
            pushStack.push(data);
        }

        public int dequeue()
        {
            if( !pushStack.empty() )
            {
                while( !pushStack.empty() )
                {
                    popStack.push( pushStack.pop() );
                }
            }
            return popStack.pop();
        }
    }
}