☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Implement Stack using Queue (using single queue)

Easy TUF ID 2808 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Implement a last-in-first-out stack of integers using only first-in-first-out queue operations: add to the back (offer), remove from the front (remove), look at the front (element), size and isEmpty. The stack must support:

The title’s restriction is the interesting part: use a single queue. We start from the classic two-queue solution and then remove the second queue.

Constraints: up to 10^5 calls; pop and top are only called on a non-empty stack in the judge’s version. Here they throw NoSuchElementException on an empty stack (the behaviour of Queue.remove() and Queue.element()).

Example 1

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

Example 2

push(10), push(20), push(30), pop(), push(40), size(), pop(), pop(), top()
output: 30, 3, 40, 20, 10

All three implementations share one interface, so a single script tests them against ArrayDeque used as a stack:

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

Approach 1: Two queues, costly push

Intuition. A queue releases its oldest element first; a stack must release its newest first. So arrange for the queue to always hold the elements in stack order: newest at the front. To push x, put it into an empty helper queue first, then move every element of the main queue behind it. Now x is at the front, followed by the old contents in their old order. Swap the names of the two queues.

Algorithm.

  1. push(x): helper.offer(x); move all of main into helper; swap main and helper.
  2. pop(): main.remove().
  3. top(): main.element().
static class TwoQueues implements IntStack {
    private Queue<Integer> main = new ArrayDeque<>();
    private Queue<Integer> helper = new ArrayDeque<>();

    public void push(int x) {
        helper.offer(x);                               // the newest element enters an empty queue first
        while (!main.isEmpty()) helper.offer(main.remove());
        Queue<Integer> t = main;                       // swap roles: helper now holds stack order
        main = helper;
        helper = t;
    }

    public int pop() {
        return main.remove();                          // throws NoSuchElementException when empty
    }

    public int top() {
        return main.element();
    }

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

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

Complexity. push is O(n) because every existing element moves; pop, top, size and isEmpty are O(1). Space O(n). The helper queue is always empty between operations, which is the hint that it is not really needed.

Approach 2: One queue, costly pop

Intuition. Keep the queue in plain arrival order: newest at the back. The top of the stack is then the last element, which a queue cannot reach directly. But a queue can rotate: removing the front and offering it at the back keeps all elements and shifts the cycle by one. Rotate n - 1 times and the newest element arrives at the front, with the others behind it in their original order. Remove it, and the queue is back in arrival order.

top() is a pop followed by putting the element back at the back of the queue, which is exactly where the newest element lives in this layout.

Algorithm.

  1. push(x): q.offer(x).
  2. pop(): repeat n - 1 times q.offer(q.remove()); then q.remove().
  3. top(): x = pop(); q.offer(x); return x.
static class OneQueueCostlyPop implements IntStack {
    private final Queue<Integer> q = new ArrayDeque<>();

    public void push(int x) {
        q.offer(x);                                    // the newest element sits at the back
    }

    public int pop() {
        if (q.isEmpty()) throw new NoSuchElementException("stack is empty");
        int n = q.size();
        for (int i = 0; i < n - 1; i++) q.offer(q.remove());  // cycle the older n - 1 behind the newest
        return q.remove();                             // the newest is now at the front
    }

    public int top() {
        int x = pop();
        q.offer(x);                                    // back at the back: original order restored
        return x;
    }

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

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

Complexity. push is O(1); pop and top are O(n). Space O(n). Prefer this when pushes greatly outnumber pops.

Approach 3: Optimal, one queue, costly push

Intuition. Use the same rotation, but do it at push time so the queue is always in stack order, like Approach 1 without the helper. After offering x at the back, rotate the n - 1 older elements behind it. x is now at the front, and the old elements follow in their old (already stack) order. pop and top become plain remove and element.

Algorithm.

  1. push(x): q.offer(x); then repeat size - 1 times q.offer(q.remove()).
  2. pop(): q.remove().
  3. top(): q.element().
static class OneQueueCostlyPush implements IntStack {
    private final Queue<Integer> q = new ArrayDeque<>();

    public void push(int x) {
        q.offer(x);
        int n = q.size();
        for (int i = 0; i < n - 1; i++) q.offer(q.remove());  // cycle older elements behind x
    }

    public int pop() {
        return q.remove();                             // throws NoSuchElementException when empty
    }

    public int top() {
        return q.element();
    }

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

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

Dry run of push(1), push(2), push(3), pop() (queue shown front to back):

operation after offer rotations queue after returns
push(1) [1] 0 [1]  
push(2) [1, 2] 1 [2, 1]  
push(3) [2, 1, 3] 2 [3, 2, 1]  
pop()     [2, 1] 3

Complexity. push is O(n); pop, top, size and isEmpty are O(1). Space O(n) with a single queue.

Side by side, the three designs trade the same O(n) cost between operations:

approach queues push pop top
Two queues, costly push 2 O(n) O(1) O(1)
One queue, costly pop 1 O(1) O(n) O(n)
One queue, costly push 1 O(n) O(1) O(1)

This is the standard answer to the follow-up because reads (pop, top) are usually more frequent than writes, and it uses one queue. Neither single-queue version gets every operation below O(n): a queue only exposes its oldest element, so one side of the stack always has to be reached by cycling past the others.

Edge cases and pitfalls