DSA sheet · Stack · Stack-based design pattern

Implement Queue using Stacks

This video opens a new pattern in the stack sheet: design problems. Instead of solving a puzzle on an array, we have to build a data structure using only another data structure. Here we build a queue (first in, first out) using only stacks (last in, first out). The teacher first shows a simple version where every push costs O(n), then improves it so that push is O(1) and pop is amortised O(1). That improvement, and being able to explain why it is better, is what interviewers look for.

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 "amortised" cost from scratch
• Part A · Version 1: costly push (reverse on every push)
• Part B · Version 2: lazy transfer, amortised O(1)
• Part C · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of plates. You can only touch the top plate. The last plate you put on is the first one you take off. This rule is called LIFO: Last In, First Out.

• push(x): put x on top.
• pop(): remove the top item and give it back.
• peek() (also called top): look at the top item without removing it.
• empty(): is the pile empty?

The Python list as a stack

st = []            # empty stack
st.append(5)       # push 5        -> [5]
st.append(7)       # push 7        -> [5, 7]   (right end = top)
top = st[-1]       # peek          -> 7
x = st.pop()       # pop           -> x = 7, st = [5]
if st:             # not empty?    (an empty list is False)
    print(st[-1])

All four operations are O(1). Always check that the stack is not empty before pop() or [-1]. On an empty list both of them crash with an IndexError.

In these notes we draw a stack left = bottom, right = top, like the list itself: [1, 2, 3] means 3 is on top.

What is a queue?

A queue is a line at a ticket counter. The person who came first is served first. This is FIFO: First In, First Out. New people join at the back; people leave from the front.

The rule of a design problem

We may use only the normal stack operations: push to top, pop from top, peek top, size and is-empty. In Python that means append, pop(), [-1] and len / truthiness. Using pop(0) or st[0] would be cheating, because a real stack cannot reach its bottom.

What does "amortised" cost mean?

Sometimes one operation is expensive, but it happens so rarely that if you add up the cost of a long run of operations and divide by how many there were, each one costs only a constant on average. That average over a whole sequence (not over random inputs) is the amortised cost.

A daily-life picture: you buy a monthly train pass once (expensive day), then ride for free for 30 days. The price per ride is small, even though one day was costly. In Part B, moving all items from one stack to the other is the "monthly pass"; it pays for many cheap pops after it.

Part A · Version 1: costly push (reverse on every push)

LeetCode 232

1The question in simple words

Build a class MyQueue that behaves exactly like a queue, but inside it you may only keep stacks. It must support:

• push(x): add x at the back of the queue.
• pop(): remove the front item and return it.
• peek(): return the front item without removing it.
• empty(): return True if the queue has no items.

Example call sequence: push(1), push(2), peek() → 1, pop() → 1, empty() → False.

2What the constraints tell us

• 1 ≤ x ≤ 9 → tiny values; nothing special to worry about.
• At most 100 calls → even O(n) per call is fine for passing. So Version 1 will be accepted. The reason to improve is the follow-up: "can each operation be amortised O(1)?". That is what Part B answers.
• Every pop and peek call is valid (the queue is not empty then). So we don't need to handle "pop from empty queue".

3Intuition: why one stack is not enough

Push 1 and then 2 onto one stack: [1, 2]. A queue's pop must return 1, but 1 is at the bottom. The only thing a stack lets us touch is the top (2). To reach 1, we must lift 2 off and put it somewhere for a while. That "somewhere" must be a second container, and since we may only use stacks, it is a second stack.

The teacher's idea for Version 1: keep stack 1 always in reversed order, so that the oldest item is always on top. Then pop and peek are just the normal stack pop and peek. Stack 2 is only a temporary holder ("keep my plates for a moment, I'll take them back").

4Building the logic from the example

Push 1 into an empty stack

Nothing is in st1, so just push: st1 = [1]. The oldest item (1) is on top ✓.

Push 2: the new item must go to the BOTTOM

2 is the newest, so in a queue it must come out last. In st1 "comes out last" means "sits at the bottom". But we can only push on top. So:

1. Move everything from st1 to st2 (pop from st1, push to st2): st1 = [], st2 = [1].
2. Now st1 is empty, so pushing 2 puts it at the bottom: st1 = [2].
3. Move everything back from st2 to st1: st1 = [2, 1], st2 = [].

Now 1 is on top again. A pop gives 1, exactly what a queue should give ✓.

Pop, peek and empty

• pop: the oldest is on top of st1, so st1.pop().
• peek: st1[-1].
• empty: check only st1.

5Approach steps

1. Keep two stacks: st1 (holds the queue, oldest on top) and st2 (temporary).
2. push(x): move all of st1 into st2 → push x into st1 → move all of st2 back into st1.
3. pop(): return st1.pop().
4. peek(): return st1[-1].
5. empty(): return not st1.

6Code (Python)

class MyQueue:
    def __init__(self):
        self.st1 = []     # the queue lives here, OLDEST item on top
        self.st2 = []     # temporary holder, empty between calls

    def push(self, x):
        while self.st1:                     # 1. lift everything off st1
            self.st2.append(self.st1.pop())
        self.st1.append(x)                  # 2. x lands at the bottom
        while self.st2:                     # 3. put everything back on top of x
            self.st1.append(self.st2.pop())

    def pop(self):
        return self.st1.pop()               # oldest is on top

    def peek(self):
        return self.st1[-1]

    def empty(self):
        return not self.st1

7Code line by line

8Dry run: operation-sequence table

The teacher pushes 1 and 2, pops, then keeps pushing. We use push 1, push 2, pop, push 3, push 4, peek, pop, empty. Stacks are drawn left = bottom, right = top. "moves" counts single stack pushes/pops so we can compare with Part B later.

Bottom of each picture is the bottom of the stack; the red box is the top. The oldest item (2) is always on top of st1, so pop is instant.

9Complexity & remember

• push: O(n). With n items already inside, we pop n, push n, push x, pop n, push n: about 4n + 1 moves.
• pop, peek, empty: O(1).
• Space O(n): every item lives in exactly one stack at any time.

It passes (100 calls is tiny), but the teacher asks: can we avoid paying O(n) on every push?

Part B · Version 2: lazy transfer, amortised O(1)

1The question again, with the new goal

Same four operations. Now we want push in O(1) and pop/peek in amortised O(1) (cheap on average over the whole run).

2What the constraints tell us now

• The follow-up on LeetCode asks exactly this: total time O(n) for n operations, even if one single operation is slow.
• pop/peek are always valid, so when st2 is empty, st1 is guaranteed to have something to move.

3Intuition: don't reverse until someone needs the front

Look at what Version 1 wastes. Push 1, 2, 3 in a row with no pop in between:

• push 1 → [1]
• push 2 → move 1 out, push 2, move 1 back → [2, 1]
• push 3 → move 1 and 2 out, push 3, move them back → [3, 2, 1]

Nobody asked for the front yet, yet we kept reshuffling. The teacher's fix: just pile up new items in st1, and reverse only when a pop or peek actually needs the front. And once reversed into st2, leave them there; st2's top stays the oldest item until st2 runs out.

So the two stacks get fixed jobs:

4Building the logic from the teacher's example

push 1, push 2, push 3 → just push

st1 = [1, 2, 3], st2 = []. Three moves in total.

pop → st2 is empty, so pour st1 into st2

Pop 3, 2, 1 from st1 and push them into st2 in that order: st2 = [3, 2, 1]. Now 1, the oldest, is on top. Pop it → 1 ✓.

push 4 → just push into st1

st1 = [4], st2 = [3, 2].

pop → st2 is NOT empty, so do NOT pour

The front of the queue is 2, and 2 is already on top of st2. Pop → 2 ✓.

pop → 3, then pop → 4

st2 = [3] → pop gives 3, st2 is empty. Next pop: st2 is empty, so pour st1 (just [4]) into st2 → pop gives 4 ✓.

peek uses the same rule as pop

peek also needs the front, so it does the same "if st2 is empty, pour" step, then returns st2[-1] instead of popping it.

empty must now check BOTH stacks

Items can sit in either stack. After 100 pushes and no pop, all of them are in st1 and st2 is empty. After 100 pushes and one pop, 99 of them are in st2 and st1 is empty. In neither case is the queue empty. So the queue is empty only when both st1 and st2 are empty.

5Approach steps

1. push(x): st1.append(x). Nothing else.
2. pop(): if st2 is empty, move every item from st1 into st2. Then return st2.pop().
3. peek(): same "if st2 is empty, pour" step, then return st2[-1].
4. empty(): return True only if both st1 and st2 are empty.

6Code (Python)

class MyQueue:
    def __init__(self):
        self.st1 = []     # "in" stack: every push lands here
        self.st2 = []     # "out" stack: oldest item on top

    def push(self, x):
        self.st1.append(x)                  # O(1), no reshuffling

    def _move(self):
        if not self.st2:                    # pour ONLY when st2 ran out
            while self.st1:
                self.st2.append(self.st1.pop())

    def pop(self):
        self._move()
        return self.st2.pop()

    def peek(self):
        self._move()
        return self.st2[-1]

    def empty(self):
        return not self.st1 and not self.st2

The teacher writes the "if st2 is empty, pour" loop twice, once inside pop and once inside peek. Putting it in a small helper _move is the same logic with less repetition.

7Code line by line

8Dry run: operation-sequence table

The teacher's sequence: push 1, push 2, push 3, pop, push 4, pop, pop, pop, then we add peek and empty checks.

The values came out 1, 2, 3, 4: the exact order they went in. That's FIFO ✓.

At step 6 the queue (front → back) is 2, 3, 4: read st2 from top to bottom, then st1 from bottom to top.

9Complexity & remember (with a counted example)

• push: O(1) always.
• pop / peek: O(1) amortised. One call can be O(n) (the pour), but it's rare.
• empty: O(1). Space: O(n).

Why the average is O(1): follow one item

Over its whole life, each item is touched at most 4 times: pushed onto st1, popped from st1, pushed onto st2, popped from st2. It never goes back from st2 to st1. So for any sequence of n operations, the total work is at most about 4n moves, which is O(1) per operation on average.

Counting it: push 1 … 100, then pop 100 times

This is the teacher's point: in Version 1 we reshuffle on every push, so 100 pushes cost about 100 × 100. In Version 2 we reverse once when the first pop arrives, and that single pour serves the next 100 pops.

Part C · Revision page

Interview tip from the teacher: companies like asking design questions (build a hash map, a linked list, a queue from stacks and the reverse). Show the simple version first, then explain why you moved the expensive work from push to a rare pour, and name it "amortised". That journey is what adds value.

q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek())    # 1
print(q.pop())     # 1
q.push(4)
print(q.pop())     # 2
print(q.empty())   # False
print(q.pop())     # 3
print(q.pop())     # 4
print(q.empty())   # True

Based on this video: Implement Queue using Stacks