How to Simulate a Stack Using a Single Queue in Code

In a recent exchange with Leandro Proença on LinkedIn, we explored the possibility of implementing a stack using only a queue. This thought exercise led to a deeper dive into computational structures and their surprising interoperability. While the idea might seem counterintuitive at first, it reveals fundamental truths about how data structures can mimic each other’s behavior under the right conditions.

Understanding Stacks and Queues as Core Structures

Both stacks and queues are linear data structures that manage collections of elements, but they operate under fundamentally different principles. A stack follows the Last-In-First-Out (LIFO) principle, where the most recently added element is the first one removed. In contrast, a queue adheres to the First-In-First-Out (FIFO) principle, where elements are removed in the order they were added. Despite these differences, their core functionalities can be abstracted into three primary operations:

• push(element: T) => void – Adds an element to the structure.
• pop() => T – Removes and returns the top element (for stacks) or the front element (for queues).
• empty() => boolean – Checks if the structure contains any elements.

These operations define the shape of the data structure, allowing us to focus on behavior rather than implementation details. For this discussion, we will model both stacks and queues using these exact signatures, ensuring consistency across implementations.

Simulating a Queue with Two Stacks

The simplest way to implement a queue using stacks leverages two stacks to reverse the order of elements. The first stack acts as the primary storage, while the second stack temporarily holds elements during a pop operation. Here’s how it works:

1. Push Operation: Elements are added directly to the primary stack.
2. Pop Operation: All elements from the primary stack are moved to the secondary stack. The top element of the secondary stack—which was the bottom element of the primary stack—is then removed and returned. The remaining elements are moved back to the primary stack.

This approach ensures that the oldest element is always at the top of the secondary stack when a pop is requested. While this method involves multiple steps, it effectively transforms the LIFO behavior of stacks into FIFO behavior for queues. Here’s a basic implementation in pseudocode:

public class Fila<T> {
  private final Pilha<T> elementos = new Pilha<>();
  private final Pilha<T> secundaria = new Pilha<>();

  public void push(T t) {
    elementos.push(t);
  }

  public T pop() {
    while (!elementos.empty()) {
      secundaria.push(elementos.pop());
    }
    final var v = secundaria.pop();
    while (!secundaria.empty()) {
      elementos.push(secundaria.pop());
    }
    return v;
  }

  public boolean empty() {
    return elementos.isEmpty();
  }
}

An alternative implementation avoids moving elements back to the primary stack by using a sentinel value to detect the end of the primary stack during a pop operation. This variation reduces the number of operations but requires careful handling of the sentinel value to avoid conflicts with actual data.

Simulating a Stack with Two Queues

Extending this logic, we can also simulate a stack using two queues. The process mirrors the previous example but swaps the roles of stacks and queues. The primary queue holds the elements, and the secondary queue temporarily stores elements during a pop operation to isolate the most recently added element.

Here’s how the stack simulation works:

1. Push Operation: Elements are added directly to the primary queue.
2. Pop Operation: All elements except the last one are moved to the secondary queue. The remaining element in the primary queue is the most recently added and is returned. The elements in the secondary queue are then moved back to the primary queue.

This approach ensures that the newest element is always the first to be removed, adhering to the LIFO principle. Below is a pseudocode representation:

public class Pilha<T> {
  private final Fila<T> elementos = new Fila<>();
  private final Fila<T> secundaria = new Fila<>();

  public void push(T t) {
    elementos.push(t);
  }

  public T pop() {
    while (true) {
      final var candidato = elementos.pop();
      if (elementos.empty()) {
        while (!secundaria.empty()) {
          elementos.push(secundaria.pop());
        }
        return candidato;
      }
      secundaria.push(candidato);
    }
  }

  public boolean empty() {
    return elementos.empty();
  }
}

Reducing the Structure to a Single Queue

The real challenge—and the most elegant solution—lies in implementing a stack using only one queue. This requires rethinking how we manage the queue’s internal state. The key insight is to use the queue itself as both the primary storage and the buffer for isolating the most recently added element.

Here’s the step-by-step logic:

1. Push Operation: Add the new element to the queue.
2. Pop Operation: Rotate the queue by repeatedly dequeuing and enqueuing elements until the new element reaches the front. This effectively moves all older elements to the back of the queue, leaving the new element at the front to be removed.

This method ensures that the newest element is always the first to be dequeued, simulating stack behavior. Here’s a pseudocode implementation:

public class Pilha<T> {
  private final Fila<T> elementos = new Fila<>();

  public void push(T t) {
    elementos.push(t);
    // Rotate the queue to bring the new element to the front
    for (int i = 0; i < elementos.size() - 1; i++) {
      elementos.push(elementos.pop());
    }
  }

  public T pop() {
    return elementos.pop();
  }

  public boolean empty() {
    return elementos.empty();
  }
}

This approach eliminates the need for additional data structures, demonstrating how a single queue can dynamically adapt to simulate stack behavior through careful manipulation of its internal order.

Why This Matters for Computational Thinking

These implementations highlight the versatility of data structures and the power of abstract thinking in computer science. By understanding the underlying principles of stacks and queues, developers can design flexible solutions that optimize memory usage and computational efficiency. Whether for educational purposes, algorithmic challenges, or real-world applications, mastering these techniques provides a deeper appreciation for the elegance of computational structures.

As programming languages and frameworks evolve, the ability to manipulate fundamental data structures remains a critical skill. These examples serve as a reminder that even the most basic tools can be repurposed to solve complex problems with creativity and precision.