DSA sheet · Stack · Stack-based design pattern

Implement Stack using Queues

This is the mirror of the previous problem. Last time we built a queue out of stacks; now we build a stack (last in, first out) out of queues (first in, first out). The teacher shows two designs with two queues: one where push is costly and pop/top are cheap, and one where push is cheap and pop/top are costly. Both are correct. Which one to pick depends on which operation you need to be fast.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run (operation-sequence table) → ⑨ complexity & remember

• Part 0 · Stacks, queues and cost from scratch
• Part A · Approach 1: costly push, O(1) pop and top
• Part B · Approach 2: O(1) push, costly pop and top
• Part C · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of plates: you can only add or remove at the top. The last item in is the first out, called LIFO (Last In, First Out). Its operations: push(x) puts x on top, pop() removes and returns the top, top() (also called peek) reads the top without removing it, empty() says whether it has nothing.

st = []
st.append(1); st.append(2)   # push 1, push 2   -> [1, 2], top = 2
st[-1]                       # top              -> 2
st.pop()                     # pop              -> 2
if st: print(st[-1])         # always check "not empty" before pop / top

What is a queue?

A queue is a line of people: you join at the back and leave from the front. The first item in is the first out, called FIFO (First In, First Out). In Java the teacher calls joining offer and leaving poll.

from collections import deque
q = deque()
q.append(1); q.append(2)     # offer 1, offer 2 (join at the back)  -> front [1, 2] back
q[0]                         # peek at the front                      -> 1
q.popleft()                  # poll the front                         -> 1
len(q), not q                # size, is it empty?

A deque could also remove from the right end, but that would make it a stack and defeat the purpose. So in this problem we only use append, popleft, [0] and len. Always check the queue isn't empty before popleft or [0].

In these notes we draw a queue as front on the left, back on the right.

The key fact that makes this problem different from the last one

So simply pouring one queue into another does nothing useful. We need a smarter trick.

Cost words: O(1), O(n) and "amortised"

O(1) means a fixed small amount of work. O(n) means work that grows with the number of items. Amortised O(1) means a single call may be slow, but over a long run of calls the average is constant, because the slow calls are rare (like Problem 18, where each item was poured only once). We'll see below that this problem has no such trick: the slow operation is slow every time.

Part A · Approach 1: costly push, O(1) pop and top

LeetCode 225

1The question in simple words

Build a class MyStack with push(x), pop(), top() and empty() that behaves exactly like a stack, but inside you may only keep queues and use queue operations (add at back, remove/peek at front, size, is-empty).

The teacher's example: push 1, push 2, push 3, then pop → must give 3 (the newest), then push 4, then pop → must give 4.

2What the constraints tell us

• 1 ≤ x ≤ 9, at most 100 calls → O(n) per call is completely fine.
• Every pop and top is called on a non-empty stack → no "empty" error handling needed.
• LeetCode's follow-up asks: can you do it with one queue? (Answered in a doubt at the end of Part A.)

3Intuition: make the newest item sit at the FRONT

Put 1, 2, 3 into a queue: front [1, 2, 3] back. A queue hands out 1 first, but a stack must hand out 3. The newest is stuck at the back.

The teacher first tries the stack-style trick: pour q1 into a second queue q2. Poll 1 → it joins q2 at the back. Poll 2 → behind 1. Poll 3 → behind 2. q2 is [1, 2, 3], the same order. Polling q2 still gives 1. Pouring alone doesn't reverse a queue.

The real idea: when the new item arrives, let it enter an EMPTY queue first. In an empty queue, the newcomer is automatically at the front. Then let all the older items line up behind it. Now the newest is at the front and the rest are behind it in newest-to-oldest order. That is exactly a stack, read from the front.

4Building the logic from the example

push 1

Put 1 into the empty helper q2: q2 = [1]. q1 has nothing to move. Now make q2 the main queue (swap names): q1 = [1], q2 = [].

push 2

Put 2 into the empty q2: q2 = [2]. Now poll everything from q1 and add it to q2: 1 joins behind 2 → q2 = [2, 1]. Swap: q1 = [2, 1], q2 = []. The front of q1 is 2, the newest ✓.

push 3

q2 = [3], then 2 and 1 join behind (in their order) → [3, 2, 1]. Swap → q1 = [3, 2, 1].

pop → 3

The newest is at the front of q1, so just q1.popleft() → 3 ✓. top is q1[0].

5Approach steps

1. Keep q1 (main: front = top of stack) and q2 (helper, empty between calls).
2. push(x): add x to q2 → move every item from q1 to q2 → swap q1 and q2.
3. pop(): q1.popleft().
4. top(): q1[0].
5. empty(): not q1.

6Code (Python)

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()   # main queue: FRONT = top of the stack
        self.q2 = deque()   # helper, always empty between calls

    def push(self, x):
        self.q2.append(x)                       # newcomer enters an empty queue: it's at the front
        while self.q1:                          # older items line up behind it
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1     # q2 becomes the main queue; old q1 (now empty) is the helper

    def pop(self):
        return self.q1.popleft()

    def top(self):
        return self.q1[0]

    def empty(self):
        return not self.q1

7Code line by line

8Dry run: operation-sequence table

The teacher's sequence: push 1, push 2, push 3, pop, push 4, pop, plus top and empty checks. Queues are drawn front on the left. "ops" counts single enqueue/dequeue steps.

Inside one push, moment by moment (pushing 3 onto [2, 1]):

(Step 3 of the table. Yellow = the top of the stack.)

9Complexity & remember

• push: O(n): all n items already in q1 are moved once (n polls + n appends) plus 1.
• pop, top, empty: O(1).
• Space: O(n).

from collections import deque

class MyStackOneQueue:
    def __init__(self):
        self.q = deque()

    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):     # send every older item to the back
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

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

    def empty(self):
        return not self.q

Part B · Approach 2: O(1) push, costly pop and top

1The question again, with the new goal

Same four operations. This time the teacher wants push in O(1). She says she likes this version more because it is easier to picture.

2What the constraints tell us now

• Still at most 100 calls, so both approaches pass. The choice is about which operation should be cheap.
• pop and top are only called when the stack has at least one item, so q1 is never empty when we start moving.

3Intuition: leave the items in arrival order, and dig out the LAST one when asked

Just append every push to q1. Then q1 is in arrival order: front [1, 2, 3] back. The top of the stack is the item at the back (3). A queue can't reach its back directly, but we can move every item EXCEPT the last one into q2. Then the only item left in q1 is the newest one. Take it (pop) or read it (top), then make q2 the main queue again.

4Building the logic from the example

push 1, push 2, push 3

Just append: q1 = [1, 2, 3]. One step each.

pop → we want 3

1. While q1 has more than one item, poll from q1 and append to q2: 1 moves, then 2 moves. q1 = [3], q2 = [1, 2].
2. The last item in q1 is the newest: poll it → 3.
3. Swap: q1 = [1, 2], q2 = [] (the teacher writes "q1 = q2; q2 = new queue").

top → we want to READ 3 without removing it

Same moving loop, so 3 is alone in q1. Take it out and remember it in val. Then put it into q2 too (at the back, after 1 and 2), and swap. q1 = [1, 2, 3] again. Return val.

empty

After every pop/top, q2 is empty again and all items are in q1. So check only q1.

5Approach steps

1. push(x): q1.append(x).
2. pop(): move items from q1 to q2 while q1 has more than 1 → poll the last one → swap → return it.
3. top(): same move → poll the last one → append it to q2 → swap → return it.
4. empty(): not q1.

6Code (Python)

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()   # items in arrival order: BACK = top of the stack
        self.q2 = deque()   # helper, empty between calls

    def push(self, x):
        self.q1.append(x)                       # O(1)

    def pop(self):
        while len(self.q1) > 1:                 # move all but the newest
            self.q2.append(self.q1.popleft())
        val = self.q1.popleft()                 # the newest, now alone
        self.q1, self.q2 = self.q2, self.q1     # helper becomes main
        return val

    def top(self):
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        val = self.q1.popleft()
        self.q2.append(val)                     # put it back: top must not remove
        self.q1, self.q2 = self.q2, self.q1
        return val

    def empty(self):
        return not self.q1

7Code line by line

8Dry run: operation-sequence table

Same answers as Part A (3, 4, 4, False), just with the work done at a different time.

9Complexity & remember (with a counted example)

• push: O(1).
• pop, top: O(n): n − 1 items move every time.
• empty: O(1). Space: O(n).

Is this "amortised O(1)" like the queue-from-stacks problem? No.

In Problem 18, once items were poured into the out-stack they stayed there in the right order, so the next pops were free. Here, after a pop, q1 is back in arrival order with the newest at the back again, so the very next pop has to move n − 2 items again. The slow step repeats on every call. Let's count: push 1 … 100, then pop 100 times.

Both total about n² here, so neither is amortised O(1). The difference is where the cost lands: push-heavy work with few pops favours Approach 2; pop/top-heavy work favours Approach 1.

Part C · Revision page

s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.pop())     # 3
s.push(4)
print(s.top())     # 4
print(s.pop())     # 4
print(s.empty())   # False
print(s.pop(), s.pop(), s.empty())   # 2 1 True

Based on this video: Implement Stack using Queues