Implement a Queue Using Two Stacks

Easy20–25 min

Topics

StackQueueDesign

Companies

AmazonMicrosoftAdobe

Implement a FIFO queue using only stack operations — push onto the top, pop from the top, peek the top — supporting enqueue(v), dequeue(), front(), isEmpty(), and size(). This version takes a fixed sequence of operations and replays them, returning the result of every dequeue, front, isEmpty, and size call as an array. This is the mirror image of building a stack from queues: a stack always hands back its newest element, the opposite of what a queue needs. One fix reorders on every enqueue, keeping the oldest value permanently on top so dequeue and front stay cheap. A better fix defers that reordering: let values pile up cheaply, and only pay the reordering cost when something actually needs to come off the front — and crucially, that cost only recurs once the "read-out" side runs dry, not on every single call. Spread across a whole sequence of operations, each element is only ever moved between the two stacks a constant number of times, giving every operation O(1) time on average even though individual dequeues can occasionally do more work than others.

Test Case 1:

Input:ops = [enqueue, enqueue, enqueue, dequeue, dequeue, front], args = [5, 10, 15, -, -, -]

Output:[5, 10, 15]

Explanation:enqueue 5, 10, 15 (in that order); dequeue returns 5 (first in), dequeue returns 10, front peeks at 15 without removing it — FIFO order.

Test Case 2:

Input:ops = [isEmpty, enqueue, isEmpty, dequeue, isEmpty], args = [-, 7, -, -, -]

Output:[1, 0, 7, 1]

Explanation:Starts empty (isEmpty→1). After enqueue(7) it's non-empty (isEmpty→0). dequeue removes and returns 7. Now it's empty again (isEmpty→1).

Test Case 3:

Input:ops = [enqueue, enqueue, size, dequeue, size], args = [1, 2, -, -, -]

Output:[2, 1, 1]

Explanation:After two enqueues, size→2. dequeue removes the oldest value (1) and returns it. size→1 afterward.

Constraints

◆1 ≤ number of operations ≤ 12
◆Each operation is one of enqueue, dequeue, front, isEmpty, or size
◆0 ≤ enqueued value ≤ 1000
◆dequeue and front return -1 when the queue is empty
◆Only stack operations (push onto the top, pop from the top, peek the top) may be used to store elements
◆This version replays a fixed sequence of operations and reports the result of every dequeue, front, isEmpty, and size call, in order (enqueue has no return value)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Two Stacks, Enqueue Costly

Brute

Keep the queue's contents in stack s1, oldest value always on top, so dequeue and front are trivial O(1) pops/peeks. To enqueue a new value while preserving that ordering: pour every element out of s1 into a helper stack s2 (which naturally reverses them), push the new value onto s2 — putting it underneath everything, since it's the newest and belongs at the bottom — then pour s2 back into s1, restoring the oldest-on-top order with the new value correctly at the very bottom. Every enqueue touches every existing element twice, so it costs O(n).

TimeO(n) per enqueue, O(1) per dequeue/front

SpaceO(n)

Java

Try it out

class Solution {
    public int[] queueOpsFromStacks(String[] ops, int[] args) {
        Deque<Integer> s1 = new ArrayDeque<>();
        Deque<Integer> s2 = new ArrayDeque<>();
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < ops.length; i++) {
            String op = ops[i];
            if (op.equals("enqueue")) {
                while (!s1.isEmpty()) s2.push(s1.pop());
                s2.push(args[i]);
                while (!s2.isEmpty()) s1.push(s2.pop());
            } else if (op.equals("dequeue")) {
                results.add(s1.isEmpty() ? -1 : s1.pop());
            } else if (op.equals("front")) {
                results.add(s1.isEmpty() ? -1 : s1.peek());
            } else if (op.equals("isEmpty")) {
                results.add(s1.isEmpty() ? 1 : 0);
            } else {
                results.add(s1.size());
            }
        }
        int[] output = new int[results.size()];
        for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
        return output;
    }
}

Optimal — Two Stacks, Amortized O(1)

Optimal

Instead of reordering on every enqueue, defer the reordering until it's actually needed. enqueue always just pushes onto s1 — O(1), no matter what. dequeue and front first check a second stack, s2: if it's empty, pour all of s1 into it in one pass (which reverses the order, putting the oldest value on top of s2); then read from s2's top. Crucially, that pour only happens when s2 runs dry — every element gets poured across the two stacks at most once before it's eventually popped, so across any sequence of n operations the total pouring work is O(n), making every operation O(1) on average (amortized), even though a single dequeue can occasionally trigger an O(n) pour.

TimeO(1) per enqueue, O(1) amortized per dequeue/front