Implement a Stack Using Queues

The last part of this tutorial series was about implementing a stack with a linked list. In this part, I'll show you how to implement a stack with a queue (or rather, with two queues).

This variant has hardly any practical use and is primarily used as an exercise (as a counterpart, I also have an exercise for implementing a queue with stacks). Therefore: Maybe you want to try to find the solution yourself first!

As a reminder, a queue is a data structure where you insert elements on one side and take them out on the other – i.e., a first-in-first-out (FIFO) data structure.

How can we use this to implement a stack, that is, a last-in-first-out (LIFO) data structure?

The Solution – Step by Step

We insert the first element that we want to push onto the stack (in the example: "apple") into a queue. To remove it from the stack, we take it out of the queue again:

We cannot simply write the second element into this queue as well. That's because the queue works according to the FIFO principle. If we push "apple" and then "orange" into the queue, we also have to take "apple" out again first:

In a stack, however, we must first take out the last element pushed onto the stack ("orange") – and not the first element inserted ("apple").

That is not possible with a single queue.

Instead, we proceed as follows when inserting an element:

1. We create a new queue (shown in orange in the image below) and move the element to be inserted into it.
2. We move the element from the first queue to the newly created queue.
3. We replace the existing queue with the new queue.

The following image shows these three steps:

After that, the elements are in the queue in such a way that we can take out the last inserted element, "orange", first and then the first inserted element, "apple".

This works not only with two elements but with as many as you like. The following image shows how we move the third element, "pear", onto the stack. I've split the second step from the previous image into steps 2a and 2b here: We first move "orange" from the old queue to the new one, then "apple".

After that, we can take the elements out of the stack in last-in-first-out order, so first the last inserted "pear", then the "orange", then the first inserted "apple".

Source Code for the Stack with Queues

Below you can see that the source code for the solution is quite simple.

For the queue, I use the simplest queue implementation, ArrayDeque. The fact that it is also a deque doesn't bother us because we assign it to a variable whose type is the Queue interface.

You can find the source code in the QueueStack class in the GitHub repository.

public class QueueStack<E> implements Stack<E> {

  private Queue<E> queue = new ArrayDeque<>();

  @Override
  public void push(E element) {
    Queue<E> newQueue = new ArrayDeque<>();
    newQueue.add(element);

    while (!queue.isEmpty()) {
      newQueue.add(queue.remove());
    }

    queue = newQueue;
  }

  @Override
  public E pop() {
    return queue.remove();
  }

  @Override
  public E peek() {
    return queue.element();
  }

  @Override
  public boolean isEmpty() {
    return queue.isEmpty();
  }
}Code language: Java (java)

The demo program StackDemo shows you how to use QueueStack.

Outlook

In the next and last part of the tutorial, we'll cover another exercise: How to reverse a stack via recursion?

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.