Implement Stack using Queues

NeetCode: Implement Stack using Queues · LeetCode: 225. Implement Stack using Queues · Difficulty: Easy

Implement a last-in-first-out stack using only queue operations (push to back, pop from front, peek at front, size, is-empty). The stack supports push(x), pop(), top() and empty().

Example

Text

push(1), push(2), top() -> 2, pop() -> 2, empty() -> false

Brute force: two queues

The queues are typed as Queue<Integer> and created as ArrayDeque, so only queue operations are available: add (to the back), remove (from the front), peek (the front), size, and isEmpty. Keep the top of the stack at the front of the main queue q1. To push x, put it into the empty helper queue q2, then move every element of q1 behind it, and swap the two queues. Now x is at the front and older elements follow in order. pop and top only use the front. Push is O(n), the others O(1).

Java

import java.util.ArrayDeque;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q1 = new ArrayDeque<>();
    private Queue<Integer> q2 = new ArrayDeque<>();

    public void push(int x) {
        q2.add(x);
        while (!q1.isEmpty()) {
            q2.add(q1.remove());
        }
        Queue<Integer> tmp = q1; // swap the two queues
        q1 = q2;
        q2 = tmp;
    }

    public int pop() {
        return q1.remove();
    }

    public int top() {
        return q1.peek();
    }

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

public class Main {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        System.out.println(s.top());
        System.out.println(s.pop());
        System.out.println(s.empty());
        System.out.println(s.pop());
        System.out.println(s.empty());
    }
}

Output

2
2
false
1
true

Time: push O(n), pop/top/empty O(1). Space: O(n) (two queues, but only one is non-empty between calls).

Optimal: one queue, rotate after push

The second queue is unnecessary. After pushing x to the back of the single queue, rotate the queue: pop the len - 1 older elements from the front and push each to the back. That leaves x at the front, in the same state as before, using one queue. The costs match the two-queue version with half the structure.

Moving the work to pop instead (push O(1), pop O(n)) is the mirror-image design.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class MyStack {
    private final Queue<Integer> q = new ArrayDeque<>();

    public void push(int x) {
        q.add(x);
        for (int i = 1; i < q.size(); i++) {
            q.add(q.remove());
        }
    }

    public int pop() {
        return q.remove();
    }

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

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

public class Main {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        System.out.println(s.top());
        System.out.println(s.pop());
        System.out.println(s.empty());
        System.out.println(s.pop());
        System.out.println(s.empty());
    }
}

Output

2
2
false
1
true

Time: push O(n), pop/top/empty O(1). Space: O(n).

LeetCode guarantees pop and top are only called on a non-empty stack. On an empty queue, remove() throws NoSuchElementException and peek() returns null, which would fail when unboxed to int.