Implement a Queue Using Stacks in Java

In this part of the tutorial series, I’ll show you how to implement a queue using two stacks – first the simple way, where every insertion moves all elements around, and then the way the classic interview question expects it: with amortized constant running time.

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 (the light blue “Temporary stack” 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. The first and the third step are split into 1a/1b and 3a/3b here, since the elements are always moved one at a time:

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 a Deque implementation such as ArrayDeque – or the JDK class Stack, though its own documentation advises against it. You can read why in “Java Deque vs. Stack: Why Deque Is the Better Choice”.

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();
  }
}

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();
}

To see the queue in use, have a look at the demo program QueueDemo.

Running Time

Every enqueue() operation moves all elements that are already on the stack to the temporary stack and back again. With n elements, that is 2 n moves – so enqueue() costs O(n). dequeue(), peek(), and isEmpty() only access the top element of the stack and run in constant time, O(1).

You can also reverse the costs: the new element simply goes on top of the stack, and enqueue() then runs in O(1). In return, dequeue() has to move all elements but the bottom one to the temporary stack, remove the bottom one, and move the others back – and costs O(n), just like peek().

But we can do better than either of these two variants.

Queue Using Two Stacks in Amortized O(1)

The trick: we keep both stacks permanently and give them fixed roles. enqueue() pushes new elements onto the input stack. dequeue() pops them from the output stack. Only when the output stack is empty do we move the entire input stack over to the output stack – that reverses the order of the elements, and the element inserted first is on top.

The following illustration shows this for “banana”, “cherry”, and “grape”:

The TwoStackQueue class in the GitHub repository implements it like this:

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

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

  @Override
  public void enqueue(E element) {
    inputStack.push(element);
  }

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

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

  @Override
  public boolean isEmpty() {
    return inputStack.isEmpty() && outputStack.isEmpty();
  }

  private void refillOutputStackIfEmpty() {
    if (outputStack.isEmpty()) {
      while (!inputStack.isEmpty()) {
        outputStack.push(inputStack.pop());
      }
    }
  }
}

A single dequeue() call can still cost O(n) – namely when it has to refill the output stack. But in doing so, each element is popped from the input stack exactly once and pushed onto the output stack exactly once; add the one push() when it is inserted and the one pop() when it is removed. No element ever incurs more than these four stack operations, no matter how many calls lie in between. For any sequence of n enqueue() and dequeue() calls, that is at most 4 n operations in total – on average, a constant number per call. This way of looking at it is called amortized running time: enqueue() and dequeue() run in amortized O(1).

This is exactly the solution to the well-known interview question “Implement Queue using Stacks”. Even with amortized constant running time, it remains an exercise as far as practical use is concerned: an ArrayDeque does the same with a single array and without moving elements around.

Outlook

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