What's the point of implementing a Stack using two queues?

Question

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:

• GeeksForGeeks
• StackOverflow

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.

Answer 1

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 exercise¹. 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 World^TM. 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 hiding² 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.}}

Answer 2

There is no advantage. You have correctly realized that using Queues to implement a Stack leads to horrible time complexity. No (competent) programmer would ever do something like this in “real life”.

But it's possible. You can use one abstraction to implement another, and vice versa. A Stack can be implemented in terms of two Queues, and likewise you could implement a Queue in terms of two stacks. The advantage of this exercise is:

• you recap Stacks
• you recap Queues
• you get accustomed to algorithmic thinking
• you learn stack-related algorithms
• you get to think about tradeoffs in algorithms
• by realizing the equivalence of Queues and Stacks, you connect various topics of your course
• you gain practical programming experience

Actually, this is a great exercise. I should do it myself right now :)

Answer 3

There is definitely a real purpose for making a queue out of two stacks. If you use immutable data structures from a functional language, you can push into a stack of pushable items, and pull from a list of poppable items. The poppable items gets created when all items have been popped out, and the new poppable stack is the reverse of the pushable stack, where the new pushable stack is now empty. It's efficient.

As for a stack made of two queues? That might make sense in a context where you have a bunch of large and fast queues available. It's definitely useless as this sort of Java exercise. But it might make sense if those are channels or messaging queues. (ie: N messages enqueued, with an O(1) operation to move (N-1) items at the front into a new queue.)

Answer 4

The exercise is needlessly contrived from a practical standpoint. The point is to force you to use the interface of the queue in a clever way to implement the stack. For example, your "One queue" solution requires that you iterate over the queue to get the last input value for stack "pop" operation. However, a queue data structure does not allow to iterate over the values, you are restricted to access them in the first-in, first-out (FIFO).

Answer 5

As others already noted: there is no real-world advantage.

Anyway, one answer to the second part of your question, why not simply to use one queue, is beyond the Java.

In Java even the Queue interface has a size() method and all the standard implementations of that method are O(1).

That is not necessarily true for the naive/canonical linked list as a C/C++ programmer would implement, which would just keep pointers to the first and last element and each element a pointer to the next element.

In that case size() is O(n) and should be avoided in loops. Or the implementation is opaque and only provides the bare minimum add() and remove().

With such an implementation you'd have to count the number of elements first by transfering them into the second queue, transfer n-1 elements back to the first queue and return the remaining element.

That said, it would probably not make up something like this if you live in Java-land.

Answer 6

It's hard to imagine a use for such an implementation, it's true. But most of the point is to prove that it can be done.

In terms of actual uses for these things, however, I can think of two. One use for this is implementing systems in constrained environments that weren't designed for it: for example, Minecraft's redstone blocks turn out to represent a Turing-complete system, which people have used to implement logic circuits and even entire CPUs. In the earliest days of script-driven gaming, many of the first game bots were also implemented this way.

But you can also apply this principle in reverse, ensuring that something isn't possible in a system when you don't want it to be. This can come up in security contexts: for example, powerful configuration systems can be an asset, but there are still degrees of power that you might rather not give to users. This constrains what you can allow the configuration language to do, lest it be subverted by an attacker, but in this case, that's what you want.