Queue Using Stacks

How It Works

Two LIFO stacks compose into one FIFO queue because two reversals restore original order. Pushes go onto an inbox stack. To dequeue or peek, pop from an outbox stack; if the outbox is empty, first pour the entire inbox into it, which reverses the elements so the oldest sits on top. Crucially, transfer only when the outbox runs dry — the outbox already holds older elements in correct order, and pouring early would interleave them wrongly.

A single dequeue can cost O(n) during a transfer, but each element is moved exactly once in its lifetime: pushed to the inbox, poured once, popped from the outbox. Total work over any n operations is O(n), so every operation is amortized O(1).

Step-by-Step Visualization

Code

class QueueUsingStacks {
  Stack<Integer> inbox = new Stack<>();
  Stack<Integer> outbox = new Stack<>();

  void push(int x) { inbox.push(x); }

  int pop() {
    if (outbox.isEmpty())
      while (!inbox.isEmpty()) outbox.push(inbox.pop());
    return outbox.pop();
  }

  int peek() {
    if (outbox.isEmpty())
      while (!inbox.isEmpty()) outbox.push(inbox.pop());
    return outbox.peek();
  }
}

Tips & Gotchas

Practice Problems

• 1Implement Queue using Stacks
• 2Implement Stack using Queues
• 3Design Circular Queue

About the Queue Design Pattern

Classic design problems that test your understanding of how queues work internally.

Common Queue / Deque Interview Problems

• Binary Tree Level Order Traversal
• Sliding Window Maximum
• Rotting Oranges
• Shortest Path in Binary Matrix
• Implement Queue using Stacks

Frequently Asked Questions

Other Queue Design Techniques