Implementing a stack using queue

This is the exact reverse of the problem discussed in my earlier post. We have to use only Queue operations like enqueue(), dequeue() and size() operations to implement push() and pop() operations of the stack.

This can be done using two queues. One queue acts as the main queue while the other acts as the helper queue.

There are two approaches to solve this problem.

• Making the pop operation costly and push operation simple
• Making the push operation costly and pop operation simple

First approach:
 

• Push operation is simple. It always adds the element to the main queue.

• To implement pop operation, we remove all but one element from the main queue and add them to the helper queue. We finally remove the remaining one element from main queue and return it. Mark the helper queue as main queue.

Second approach:

• Pop operation is simple. It simply removes element from the main queue and return it.

• Push operation first adds the element to the helper queue. Then it removes elements from main queue one by one and add them to the helper queue. The intent behind this is to make the last inserted element to be available for removing. Finally make the helper queue as main queue.

The following table gives snapshots of the algorithm at different stages. Assume the queue is presented from left to right. The left most element is at the front of the queue and right most element is at the rear of the queue.

Observe that the elements are popped in the LIFO order.

We will see the implementation of first approach in this post. Implementation of second approach can be taken as an exercise.

/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 8/26/13
 * Time: 4:47 PM
 */
import java.util.LinkedList;
import java.util.Queue;
public class Main {
    public static void main(String[] args)
    {
        Stack2Queues stck = new Stack2Queues();
        stck.push(1);
        stck.push(2);
        System.out.println(stck.pop());
        stck.push(3);
        System.out.println(stck.pop());
        System.out.println(stck.pop());
        stck.push(4);
        stck.push(5);
        System.out.println(stck.pop());
        System.out.println(stck.pop());
    }
    static class Stack2Queues
    {
        Queue<Integer> q1;
        Queue<Integer> q2;
        int activeQ;
        public Stack2Queues()
        {
            q1 = new LinkedList<Integer>();
            q2 = new LinkedList<Integer>();
            activeQ = 1;
        }
        public void push(int data)
        {
            Queue<Integer> q;
            if( activeQ == 1)
                q = q1;
            else
                q = q2;
            q.add(data);
        }
        public int pop()
        {
            Queue<Integer> mainQ;
            Queue<Integer> helperQ;
            if( activeQ == 1)
            {
                mainQ = q1;
                helperQ = q2;
                activeQ = 2;
            }
            else
            {
                mainQ = q2;
                helperQ = q1;
                activeQ = 1;
            }
            while( mainQ.size() > 1 )
            {
                helperQ.add(mainQ.remove());
            }
            return mainQ.remove();
        }
    }
}