☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Implement Queue using Stack

Easy TUF ID 389 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Implement a first-in-first-out queue (push, pop, peek, isEmpty, size) using only the standard operations of a stack: push on top, pop the top, peek the top, size and isEmpty. You may use two stacks, but you may not look below the top, iterate, or index into them.

Constraints: up to 10^5 operations, values fit in int. pop and peek on an empty queue are errors; the code throws NoSuchElementException.

Example 1 (LeetCode 232)

push(1), push(2), peek(), pop(), isEmpty()
output: 1, 1, false            // 1 arrived first, so it leaves first

Example 2

push(1), push(2), pop(), push(3), push(4), pop(), pop(), peek()
output: 1, 2, 3, 4             // pushes after a pop must still queue up behind older elements

Both implementations share this interface so one test script drives them:

interface IntQueue {
    void push(int x);
    int pop();
    int peek();
    boolean isEmpty();
    int size();
}

Approach 1: Costly push

Intuition. A stack returns the newest element; a queue must return the oldest. If we could arrange the stack so that the oldest element is always on top, pop and peek would be trivial. We can, at a price: to push x so that it ends up at the bottom, first move everything out of the stack into a helper (which reverses it), push x into the now-empty stack, then move everything back (reversing again, which restores the original order on top of x). The oldest element returns to the top, x sits at the bottom, and the invariant holds.

Algorithm.

  1. push(x): while stack is non-empty, helper.push(stack.pop()). Then stack.push(x). Then while helper is non-empty, stack.push(helper.pop()).
  2. pop(): stack.pop(). peek(): stack.peek().
  3. isEmpty() and size() delegate to stack.
static class CostlyPushQueue implements IntQueue {
    private final Deque<Integer> stack = new ArrayDeque<>();    // top of stack is always the oldest element
    private final Deque<Integer> helper = new ArrayDeque<>();

    public void push(int x) {
        while (!stack.isEmpty()) helper.push(stack.pop());      // reverse into helper
        stack.push(x);                                          // x becomes the bottom
        while (!helper.isEmpty()) stack.push(helper.pop());     // old elements back on top, oldest ends on top
    }

    public int pop() {
        if (stack.isEmpty()) throw new NoSuchElementException("queue underflow");
        return stack.pop();
    }

    public int peek() {
        if (stack.isEmpty()) throw new NoSuchElementException("queue is empty");
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public int size() {
        return stack.size();
    }
}

Complexity. Time O(n) for push (every element moves twice), O(1) for pop, peek, isEmpty, size. Space O(n); the helper is empty between operations.

This is correct and simple, but it does O(n) work on every push even when no one is going to pop for a while. The next approach does the reversal lazily and only when it is needed.

Approach 2: Two stacks, amortised O(1)

Intuition. Keep two stacks. input receives every push, newest on top. output is where pops come from, oldest on top. When output is empty and someone asks for the front, pour input into output: popping input yields newest first, and pushing those onto output leaves the oldest on top, exactly the order a queue wants.

The key observation is when not to pour. If output still has elements, they are all older than anything in input, so the front of the queue is output.peek() and input must be left alone. Pouring while output is non-empty would put newer elements on top of older ones and break FIFO order. Test 2 in the Java file (push 1, push 2, pop, push 3, push 4, pop, pop, peek) exists to catch exactly that mistake.

Algorithm.

  1. push(x): input.push(x).
  2. refillOutputIfEmpty(): if output is empty, while input is non-empty do output.push(input.pop()).
  3. pop(): refill, then output.pop(). peek(): refill, then output.peek().
  4. isEmpty() is true when both stacks are empty; size() is the sum of the two sizes.
static class AmortizedQueue implements IntQueue {
    private final Deque<Integer> input = new ArrayDeque<>();    // newest on top
    private final Deque<Integer> output = new ArrayDeque<>();   // oldest on top

    public void push(int x) {
        input.push(x);
    }

    private void refillOutputIfEmpty() {
        if (output.isEmpty()) {
            while (!input.isEmpty()) output.push(input.pop());  // one reversal flips newest-first into oldest-first
        }
    }

    public int pop() {
        refillOutputIfEmpty();
        if (output.isEmpty()) throw new NoSuchElementException("queue underflow");
        return output.pop();
    }

    public int peek() {
        refillOutputIfEmpty();
        if (output.isEmpty()) throw new NoSuchElementException("queue is empty");
        return output.peek();
    }

    public boolean isEmpty() {
        return input.isEmpty() && output.isEmpty();
    }

    public int size() {
        return input.size() + output.size();
    }
}

Dry run on example 2:

operation input (top → bottom) output (top → bottom) returns
push(1) [1] []  
push(2) [2, 1] []  
pop() [] [1, 2] → [2] 1 (poured, then popped)
push(3) [3] [2]  
push(4) [4, 3] [2]  
pop() [4, 3] [] 2 (output non-empty: no pour)
pop() [] [3, 4] → [4] 3 (poured now)
peek() [] [4] 4

Complexity. Time amortised O(1) per operation. Each element is pushed onto input once, popped from input once, pushed onto output once and popped from output once: four stack operations in its whole lifetime, regardless of how the pushes and pops are interleaved. A single pop can cost O(n) when it triggers a pour, but n cheap pushes paid for it. Space O(n).

The amortised argument is worth saying out loud in an interview: “the pour moves each element exactly once, so total work over m operations is O(m).”

Edge cases and pitfalls