Implementing a Queue Using a Stack

In this part of the tutorial series, I'll show you how to implement a queue using a stack (more precisely, using two stacks).

This variant has no practical use but is primarily an exercise task. As such, it is the counterpart to implementing a stack with a queue.

As a reminder, a stack is a data structure where elements are retrieved in the reverse order of insertion, i.e., a last-in-first-out (LIFO) data structure.

How can we use it to implement a queue, that is, a first-in-first-out (FIFO) data structure?

The Solution – Step by Step

We put the first element that we insert into the queue on a stack (in the example: "banana"). To remove it from the queue, we take it from the stack again:

That will no longer work with the second element since the stack works according to the LIFO principle. If, for example, "banana" and "cherry" are on the stack, we would have to take "cherry" first:

In a queue, however, we want the first element inserted (i.e., "banana") to be the first to be removed.

With a stack alone, this is not possible.

Instead, we proceed as follows when inserting an element into the queue:

1. We create a temporary stack (shown in orange in the image below) and move all the elements of the original stack to the temporary stack.
2. We put the new element on the original stack.
3. We move all elements back from the temporary stack to the original stack. The temporary stack is then no longer needed.

The following illustration shows these three steps:

After that, the elements are on the stack in such a way that we can take the first inserted element, "banana", first and then the second inserted element, "cherry".

That works not only with two elements but with any number of elements. The following image shows how we insert the third element, "grape", into the queue:

After that, we can take the elements out of the queue in first-in-first-out order, so first, the "banana", which we inserted first, then the "cherry", and finally the "grape" inserted last.

Source Code for the Queue with Stacks

The source code for this algorithm requires only a few lines of code.

As a stack, I use the ArrayStack class presented in the Stack tutorial. You could just as well use the JDK class Stack or any Deque implementation, e.g., an ArrayDeque.

You can find the code in the StackQueue class in the tutorial's GitHub repository.

public class StackQueue<E> implements Queue<E> {

  private final Stack<E> stack = new ArrayStack<>();

  @Override
  public void enqueue(E element) {
    // 1. Move elements from main stack to a temporary stack
    Stack<E> temporaryStack = new ArrayStack<>();
    while (!stack.isEmpty()) {
      temporaryStack.push(stack.pop());
    }

    // 2. Push new element on the main stack
    stack.push(element);

    // 3. Move elements back from temporary stack to main stack
    while (!temporaryStack.isEmpty()) {
      stack.push(temporaryStack.pop());
    }
  }

  @Override
  public E dequeue() {
    return stack.pop();
  }

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

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

Note that we do not implement the java.util.Queue interface here. That interface inherits from java.util.Collection, so we would have to implement many more methods.

Instead, I wrote a custom Queue interface for this tutorial that defines only the enqueue(), dequeue(), peek(), and isEmpty() methods:

public interface Queue<E> {
  void enqueue(E element);
  E dequeue();
  E peek();
  boolean isEmpty();
}Code language: Java (java)

Outlook

In the next part of the tutorial, you will learn how to implement a queue with a linked list.

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.