Java Stack – What’s the Point of Implementing a Stack Using Two Queues?

javastack

I have the following homework question:

Implement the stack methods push(x) and pop() using two queues.

This seems odd to me because:

  • A Stack is a (LIFO) queue
  • I don't see why you would need two queues to implement it

I searched around:

and found a couple solutions. This is what I ended up with:

public class Stack<T> {
    LinkedList<T> q1 = new LinkedList<T>();
    LinkedList<T> q2 = new LinkedList<T>();

    public void push(T t) {
        q1.addFirst(t);
    }

    public T pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException(
                "Can't pop from an empty stack!");
        }

        while(q1.size() > 1) {
            q2.addFirst( q1.removeLast() );
        }

        T popped = q1.pop();

        LinkedList<T> tempQ = q1;
        q1 = q2;
        q2 = tempQ;

        return popped;
    }
}

But I don't understand what the advantage is over using a single queue; the two queue version seems pointlessly complicated.

Say we choose for pushes to be the more efficient of the 2 (as I did above), push would remain the same, and pop would simply require iterating to the last element, and returning it. In both cases, the push would be O(1), and the pop would be O(n); but the single queue version would be drastically simpler. It should only require a single for loop.

Am I missing something? Any insight here would be appreciated.

Best Answer

There is no advantage: this is a purely academic exercise.

A very long time ago when I was a freshman in college I had a similar exercise1. The goal was to teach students how to use object-oriented programming to implement algorithms instead of writing iterative solutions using for loops with loop counters. Instead, combine and reuse existing data structures to achieve your goals.

You will never use this code in the Real WorldTM. What you need to take away from this exercise is how to "think outside the box" and reuse code.

Please note that you should be using the java.util.Queue interface in your code instead of using the implementation directly:

Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();

This allows you to use other Queue implementations if desired, as well as hiding2 methods that are on LinkedList that might get around the spirit of the Queue interface. This includes get(int) and pop() (while your code compiles, there is a logic error in there given the constraints of your assignment. Declaring your variables as Queue instead of LinkedList will reveal it). Related reading: Understanding “programming to an interface” and Why are interfaces useful?

1 I still remember: the exercise was to reverse a Stack using only methods on the Stack interface and no utility methods in java.util.Collections or other "static only" utility classes. The correct solution involves using other data structures as temporary holding objects: you have to know the different data structures, their properties, and how to combine them to do it. Stumped most of my CS101 class who had never programmed before.

2 The methods are still there, but you cannot access them without type casts or reflection. So it is not easy to use those non-queue methods.

Related Topic