Implement Queue using Stacks

NeetCode: Implement Queue using Stacks · LeetCode: 232. Implement Queue using Stacks · Difficulty: Easy

Implement a first-in-first-out queue using only stack operations. The queue supports push(x), pop(), peek() and empty().

Example

Text

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

Brute force: keep the newest element at the bottom

The stacks are ArrayDeque<Integer> objects used only through push, pop, peek, and isEmpty, which act on the head of the deque. ArrayDeque is used instead of the legacy Stack class. Keep the queue front on top of a main stack. To push x, move all elements to a helper stack, place x on the empty main stack, then move everything back on top of it. Reversing twice restores the order with x at the bottom. Push is O(n); pop and peek are O(1).

Java

import java.util.ArrayDeque;
import java.util.Deque;

class MyQueue {
    private final Deque<Integer> main = new ArrayDeque<>();
    private final Deque<Integer> helper = new ArrayDeque<>();

    public void push(int x) {
        while (!main.isEmpty()) {
            helper.push(main.pop());
        }
        main.push(x);
        while (!helper.isEmpty()) {
            main.push(helper.pop());
        }
    }

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

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

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

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

Output

1
1
false
2
true

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

Optimal: input and output stacks with lazy transfer

Push everything onto an input stack in O(1). Elements only need to be reversed when the front is requested. An output stack handles that: when pop or peek finds output empty, move every element from input to output. That reverses their order, so the oldest element ends up on top. While output is non-empty, its top is always the correct front, because everything in input is newer.

Each element is moved at most once from input to output in its lifetime, so any sequence of n operations costs O(n) in total: pop and peek are amortized O(1), even though a single call can take O(n).

Java

import java.util.ArrayDeque;
import java.util.Deque;

class MyQueue {
    private final Deque<Integer> input = new ArrayDeque<>();
    private final Deque<Integer> output = new ArrayDeque<>();

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

    private void shift() {
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
    }

    public int pop() {
        shift();
        return output.pop();
    }

    public int peek() {
        shift();
        return output.peek();
    }

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

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

Output

1
1
false
2
true

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

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