36

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.

Improve this question
12
  • 17
    A queue is typically referring to a FIFO structure while the stack is a LIFO structure. The interface for LinkedList in Java is that of a deque (double ended queue) which allows both FIFO and LIFO access. Try changing programming to the Queue interface rather than the LinkedList implementation. Commented Jun 16, 2015 at 20:12
  • 13
    The more usual problem is to implement a queue using two stacks. You might find Chris Okasaki's book on purely functional data structures interesting. Commented Jun 17, 2015 at 0:21
  • 3
    Building off what Eric said, you can sometimes find yourself in a stack based language (such as dc or a push down automaton with two stacks (equivalent to a turing machine because, well, you can do more)) where you may find yourself with multiple stacks, but no queue. Commented Jun 17, 2015 at 2:04
  • 1
    @MichaelT: Or you can also find yourself running on a stack based CPU Commented Jun 17, 2015 at 3:22
  • 11
    "A stack is a (LIFO) queue"... uhm, a queue is a waiting line. Like the line for using a public restroom. Do the lines you wait in ever behave in a LIFO fashion? Stop using the term "LIFO queue", it's nonsensical. Commented Jun 17, 2015 at 7:25

6 Answers 6

Reset to default
46

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.

Improve this answer
1
  • 1
    Thanks. I guess that makes sense. I also realized that I'm using "illegal" operations in the above code (pushing to the front of a FIFO), but I don't think that changes anything. I reversed all of the operations, and it still works as intended. I'm going to wait a bit before I accept as I don't want to discourage any other people from giving input. Thank you though. Commented Jun 16, 2015 at 20:20
21

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 :)

Improve this answer
2
  • 3
    @JohnKugelman Thanks for your edit, but I really meant “horrible time complexity”. For a linked-list-based stack push, peek and pop operations are in O(1). The same for a resizeable array-based stack, except that push is in O(1) amortized, with O(n) worst case. Compared with that, a queue-based stack is vastly inferior with O(n) push, O(1) pop and peek, or alternatively O(1) push, O(n) pop and peek. Commented Jun 17, 2015 at 8:34
  • 2
    "horrible time complexity" and "vastly inferior" is not exactly right. Amortized complexity is still O(1) for push and pop. There's a fun question in TAOCP (vol1?) about that (basically you have to show that the number of times an element can switch from one stack to the other is constant). Worst case performance for one operation is different, but then I rarely hear anybody talking about O(N) performance for push in ArrayLists - not the usually interesting number. Commented Jun 17, 2015 at 14:23
6

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.)

Improve this answer
2
  • Hmm.. this made me think about using shift registers as the basis of computing and about the belt/mill architecture Commented Jun 17, 2015 at 3:25
  • wow, the Mill CPU is indeed interesting. A "Queue Machine" for sure. Commented Jun 17, 2015 at 20:30
3

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).

Improve this answer
3

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.

Improve this answer
2
  • Good point about the size() method. However, in the absence of an O(1) size() method, it's trivial for the stack to keep track of its current size itself. Nothing to stop a one-queue implementation. Commented Jun 18, 2015 at 20:31
  • It all depends on the implementation. If you have a queue, implemented with only forward pointers and pointers to first and last element, you could still write and algorithm which removes an element, saves it to a local variable, adds the element previously in that variable to the same queue until the first element is seen again. This only works if you can uniquely identify an element (e.g. via pointer) and not just something with the same value. O(n) and only uses add() and remove(). Anyway, it is easier to optimize, that to find a reason to actually do that, except thinking about algorithms. Commented Jun 19, 2015 at 15:08
1

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.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.