☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Implement Stack using Queue

Easy TUF ID 392 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Implement a last-in-first-out stack (push, pop, top, isEmpty, size) using only the standard operations of a queue: add to the rear (offer), remove from the front (poll), read the front (peek), size and isEmpty. You may use one or two queues, but you may not peek at the rear, iterate, or index into them.

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

Example 1 (LeetCode 225)

push(1), push(2), top(), pop(), isEmpty()
output: 2, 2, false            // 2 was pushed last, so it is on top

Example 2

push(1), push(2), push(3), top(), top(), pop(), pop(), size()
output: 3, 3, 3, 2, 1          // top() must not disturb the stack

The three implementations share this interface so one test script can drive all of them:

interface IntStack {
    void push(int x);
    int pop();
    int top();
    boolean isEmpty();
    int size();
}

Approach 1: Two queues, cheap push, costly pop

Intuition. A queue hands back elements oldest first; a stack wants newest first. If the elements are stored in insertion order, the stack top is the element at the rear of the queue, which a queue cannot reach directly. We can reach it indirectly: move every element except the last one into a spare queue, in order, and what remains at the front is the newest element. After taking it, the spare queue holds the rest in the original order, so just swap the two references and the spare is empty again.

Algorithm.

  1. push(x): q1.offer(x).
  2. pop(): while q1 has more than one element, q2.offer(q1.poll()). Take the single remaining element of q1 as the answer. Swap q1 and q2.
  3. top(): perform pop() and then offer the popped value back into q1. It becomes the rear again, which is where the top lives.
  4. isEmpty() and size() delegate to q1.
static class TwoQueuesCostlyPop implements IntStack {
    private Queue<Integer> q1 = new ArrayDeque<>();     // holds the stack, oldest at the front
    private Queue<Integer> q2 = new ArrayDeque<>();     // always empty between operations

    public void push(int x) {
        q1.offer(x);
    }

    public int pop() {
        if (q1.isEmpty()) throw new NoSuchElementException("stack underflow");
        while (q1.size() > 1) q2.offer(q1.poll());      // everything except the most recent element
        int x = q1.poll();                              // the most recent element is the stack top
        Queue<Integer> t = q1;                          // swap roles; q2 is empty again
        q1 = q2;
        q2 = t;
        return x;
    }

    public int top() {
        int x = pop();
        q1.offer(x);                                    // re-append: it is the newest element again
        return x;
    }

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

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

Complexity. Time O(1) for push, O(n) for pop and top (each moves n - 1 elements). Space O(n) across the two queues; at most one of them is non-empty between operations.

Why the swap is safe: after the loop q2 holds n - 1 elements in the same relative order they had in q1, which is exactly the stack with its top removed. Renaming the queues costs nothing and avoids copying everything back.

Approach 2: Two queues, costly push, cheap pop

Intuition. Flip the trade. Instead of hunting for the newest element at pop time, arrange on every push that the newest element is at the front. Put x into the empty spare queue first, then append all existing elements behind it; the spare now contains the stack in newest-first order, so swap. pop and top are then plain poll and peek.

Algorithm.

  1. push(x): q2.offer(x); while q1 is non-empty, q2.offer(q1.poll()); swap q1 and q2.
  2. pop(): q1.poll(). top(): q1.peek().
  3. isEmpty() and size() delegate to q1.
static class TwoQueuesCostlyPush implements IntStack {
    private Queue<Integer> q1 = new ArrayDeque<>();     // holds the stack, newest at the front
    private Queue<Integer> q2 = new ArrayDeque<>();     // always empty between operations

    public void push(int x) {
        q2.offer(x);                                    // x first, so it ends up at the front
        while (!q1.isEmpty()) q2.offer(q1.poll());      // older elements behind it, order kept
        Queue<Integer> t = q1;
        q1 = q2;
        q2 = t;
    }

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

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

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

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

Complexity. Time O(n) for push, O(1) for everything else. Space O(n).

Choose between approaches 1 and 2 by workload: if reads (top) dominate, pay on push; if writes dominate, pay on pop. In an interview, be ready to state that trade-off.

Approach 3: One queue with rotation

Intuition. The second queue in approach 2 exists only to hold the old elements while x is placed in front of them. A single queue can do that itself: after offer(x), the queue is [old_1, ..., old_{n-1}, x]. Polling the front and offering it back to the rear once moves old_1 behind x. Doing that n - 1 times moves all the old elements behind x, leaving [x, old_1, ..., old_{n-1}]. The front of the queue is now the top of the stack and the rest of the queue is the rest of the stack in order, so the invariant “queue order equals stack order, top first” is restored.

Algorithm.

  1. push(x): q.offer(x); then repeat q.offer(q.poll()) exactly size - 1 times.
  2. pop(): q.poll(). top(): q.peek().
  3. isEmpty() and size() delegate to q.
static class OneQueue implements IntStack {
    private final Queue<Integer> q = new ArrayDeque<>();   // newest at the front

    public void push(int x) {
        q.offer(x);
        for (int i = 1; i < q.size(); i++) q.offer(q.poll());   // n-1 rotations move x to the front
    }

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

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

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

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

Dry run of push(1), push(2), push(3) followed by pop():

operation after offer rotations queue (front → rear)
push(1) [1] 0 [1]
push(2) [1, 2] 1: move 1 behind 2 [2, 1]
push(3) [2, 1, 3] 2: move 2, then 1 [3, 2, 1]
pop()     returns 3, queue [2, 1]

Complexity. Time O(n) for push, O(1) for pop, top, isEmpty, size. Space O(n) in a single queue, the smallest footprint of the three.

The loop bound i < q.size() is evaluated each iteration, but size() does not change during a rotation (one poll, one offer), so the loop runs exactly n - 1 times.

Edge cases and pitfalls