Implement Queue using Stacks

EASY✓ CHIP-TIMEDLC #232 — FULL STATEMENT ↗

The drill: Build a FIFO queue — push, pop, peek, empty — using only LIFO stack operations underneath. Reversing the order has to happen somewhere in your own code.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

This drill asks for a working queue — first-in-first-out order — built entirely on top of stack operations, which are naturally last-in-first-out.

Four operations get exercised: push adds a value to the back, pop removes and returns the value at the front, peek reads that front value without removing it, and empty reports whether anything remains.

The underlying stacks only support push and pop directly, so restoring FIFO order out of two LIFO structures has to happen inside the implementation itself.

EX 01

MyQueue()

push(1)

push(2)

peek() → 1

pop() → 1

empty() → false

PEEK THEN POP RETURN THE SAME FRONT

EX 02

MyQueue()

empty() → true

push(9)

empty() → false

pop() → 9

empty() → true

EMPTY TRACKED BEFORE AND AFTER

EX 03

MyQueue()

push(1)

push(2)

push(3)

pop() → 1

pop() → 2

pop() → 3

FIFO ORDER PRESERVED

operations arrive as a sequence of push, pop, peek, and empty calls
pushed values can be any integer, including duplicates
pop and peek are only ever called on a non-empty queue
only real stack operations may be used underneath

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A single stack reverses order once. You need it reversed twice to land back on FIFO — what if a second stack held that second reversal?

HINT 2 THE STRUCTURE

Push always lands on an “in” stack. Whenever you need the front and the “out” stack is empty, dump all of “in” into “out” — that dump is the reversal back to FIFO order.

HINT 3 ONE STEP FROM THE ANSWER

Only refill “out” from “in” when “out” is empty. Each element crosses from “in” to “out” exactly once no matter how many pushes and pops interleave, so the cost amortizes to O(1).

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE LAZY DUMPPATTERN · TWO STACKS, LAZY TRANSFERpush(1) · push(2) · peek() · pop() · empty()

push 1

push 2

peek

pop

empty

IN / OUT STACKS

— empty —

STEP 1

Push always lands on the 'in' stack. When the front is needed and 'out' is empty, dump all of 'in' into 'out' — that dump reverses it back to FIFO order.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/implement-queue-using-stacks.py — RACE PACE

LANG ▸

PACE ▸

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

    def _transfer(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

TIME O(1) AMORTIZEDSPACE O(N)PYTHON · RACE PACE · 23 LN

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        while self.in_stack:
            self.out_stack.append(self.in_stack.pop())
        val = self.out_stack.pop()
        while self.out_stack:
            self.in_stack.append(self.out_stack.pop())
        return val

    def peek(self) -> int:
        while self.in_stack:
            self.out_stack.append(self.in_stack.pop())
        val = self.out_stack[-1]
        while self.out_stack:
            self.in_stack.append(self.out_stack.pop())
        return val

    def empty(self) -> bool:
        return len(self.in_stack) == 0

TIME O(N) EVERY CALLSPACE O(N)PYTHON · TRAINING PACE · 26 LN

class MyQueue {
    private final Deque<Integer> inStack = new ArrayDeque<>();
    private final Deque<Integer> outStack = new ArrayDeque<>();

    public MyQueue() {
    }

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

    public int pop() {
        transfer();
        return outStack.pop();
    }

    public int peek() {
        transfer();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void transfer() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

TIME O(1) AMORTIZEDSPACE O(N)JAVA · RACE PACE · 33 LN

class MyQueue {
    private final Deque<Integer> inStack = new ArrayDeque<>();
    private final Deque<Integer> outStack = new ArrayDeque<>();

    public MyQueue() {
    }

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

    public int pop() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
        int val = outStack.pop();
        while (!outStack.isEmpty()) {
            inStack.push(outStack.pop());
        }
        return val;
    }

    public int peek() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
        int val = outStack.peek();
        while (!outStack.isEmpty()) {
            inStack.push(outStack.pop());
        }
        return val;
    }

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

TIME O(N) EVERY CALLSPACE O(N)JAVA · TRAINING PACE · 37 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED