Implement Stack Using Queues

EASY✓ CHIP-TIMEDLC #225 — FULL STATEMENT ↗

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

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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

Four operations get exercised: push adds a value, pop removes and returns the most recently pushed value, top reads that same value without removing it, and empty reports whether anything remains.

The underlying queues only ever support enqueue and dequeue directly — any reordering needed to make pop return the newest element has to happen inside the implementation itself.

EX 01

MyStack()

push(1)

push(2)

top() → 2

pop() → 2

empty() → false

TOP THEN POP RETURN THE SAME VALUE

EX 02

MyStack()

empty() → true

push(5)

empty() → false

pop() → 5

empty() → true

EMPTY TRACKED BEFORE AND AFTER

EX 03

MyStack()

push(1)

push(2)

push(3)

pop() → 3

pop() → 2

pop() → 1

REVERSE POP ORDER

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

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A stack needs LIFO order but you only have FIFO queues — the trick is where the reordering happens: at push time, or at pop time?

HINT 2 THE STRUCTURE

Do the reordering on push: after enqueuing the new element, rotate the queue so every older element cycles behind it — the newest ends up at the front.

HINT 3 ONE STEP FROM THE ANSWER

push(x): enqueue x, then dequeue-and-requeue every element that was already there. The queue's front becomes the top instantly, so pop and top are just queue operations.

COACH'S BOARD — THE PATTERN, STEP BY STEP

ROTATE ON PUSHPATTERN · ONE QUEUE, ROTATE ON PUSHpush(1) · push(2) · top() · pop() · empty()

push 1

push 2

top

pop

empty

UNDERLYING QUEUE, FRONT→BACK

— empty —

STEP 1

Push does the reordering: after enqueuing, rotate the whole queue behind the new value so the newest sits at the front.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/implement-stack-using-queues.py — RACE PACE

LANG ▸

PACE ▸

class MyStack:
    def __init__(self):
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

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

TIME O(N) PUSH, O(1) POP/TOPSPACE O(N)PYTHON · RACE PACE · 17 LN

class MyStack:
    def __init__(self):
        self.q1 = collections.deque()
        self.q2 = collections.deque()

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

    def pop(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        val = self.q1.popleft()
        self.q1, self.q2 = self.q2, self.q1
        return val

    def top(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        val = self.q1[0]
        self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
        return val

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

TIME O(1) PUSH, O(N) POP/TOPSPACE O(N)PYTHON · TRAINING PACE · 25 LN

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

    public MyStack() {
    }

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

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

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

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

TIME O(N) PUSH, O(1) POP/TOPSPACE O(N)JAVA · RACE PACE · 26 LN

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

    public MyStack() {
    }

    public void push(int x) {
        q1.offer(x);
    }

    public int pop() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int val = q1.poll();
        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
        return val;
    }

    public int top() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int val = q1.peek();
        q2.offer(q1.poll());
        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
        return val;
    }

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

TIME O(1) PUSH, O(N) POP/TOPSPACE O(N)JAVA · TRAINING PACE · 38 LN

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