Design with Stacks and Queues

This family asks you to build a primitive out of the wrong primitive: a queue from stacks, a stack from queues, a stack that also reports its minimum. They look like puzzles, and they are really testing two things:

Can you carry auxiliary state alongside the data, rather than computing properties on demand?
Can you reason about amortised cost — recognising that an occasional expensive operation is still $O(1)$ per operation on average?

The second point is the real content. An operation that is usually free and occasionally $O(n)$ can still be $O(1)$ amortised, and being able to prove that is what the two-stack queue exists to elicit.

What you’ll learn

The paired-state trick: store (value, min_so_far)(value, min_so_far) instead of recomputing.
The two-stack queue, and the amortised argument that makes it $O(1)$ .
Why “only refill when empty” is essential, not an optimisation.
Circular buffers — fixed capacity with modular index arithmetic.
Three real LeetCode problems solved in the browser: 155, 232, 622.

The cue

Term	Meaning
$O(1)$ worst case	Every call is constant time
$O(1)$ amortised	Any sequence of `nn` calls costs $O(n)$ total, so the average is constant — individual calls may be slower

The two-stack queue is $O(1)$ amortised but $O(n)$ worst case for a single poppop. LC 232 explicitly asks for amortised $O(1)$ , which is the problem telling you the expensive-refill design is the intended answer.

Being precise about this distinction is worth real credit. Claiming ” $O(1)$ ” flat for a two-stack queue is wrong, and interviewers notice.

Trick 1 — paired state (Min Stack)

The naive getMingetMin scans the stack: $O(n)$ . Keeping a single minmin variable fails, because popping the minimum leaves you with no way to recover the previous minimum.

The fix is to store, with every element, what the minimum was at the moment it was pushed:

min_stack.py

class MinStack:
    def __init__(self):
        self.stack = []                   # entries are (value, min_at_this_depth)
 
    def push(self, val):
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))
 
    def pop(self):
        self.stack.pop()
 
    def top(self):
        return self.stack[-1][0]
 
    def getMin(self):
        return self.stack[-1][1]          # O(1) -- already computed

min_stack.py

class MinStack:
    def __init__(self):
        self.stack = []                   # entries are (value, min_at_this_depth)
 
    def push(self, val):
        current_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, current_min))
 
    def pop(self):
        self.stack.pop()
 
    def top(self):
        return self.stack[-1][0]
 
    def getMin(self):
        return self.stack[-1][1]          # O(1) -- already computed

Every operation is $O(1)$ worst case, at the cost of $O(n)$ extra space.

Trick 2 — the two-stack queue

A stack reverses order; two stacks reverse it twice, giving you back FIFO.

inboxinbox receives every push.
outboxoutbox serves every pop and peek.
When outboxoutbox is empty, pour the whole inboxinbox into it — which reverses it, putting the oldest element on top.

two_stack_queue.py

class MyQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []
 
    def push(self, x):
        self.inbox.append(x)              # always O(1)
 
    def _shift(self):
        if not self.outbox:               # ONLY when empty -- see below
            while self.inbox:
                self.outbox.append(self.inbox.pop())
 
    def pop(self):
        self._shift()
        return self.outbox.pop()
 
    def peek(self):
        self._shift()
        return self.outbox[-1]
 
    def empty(self):
        return not self.inbox and not self.outbox

two_stack_queue.py

class MyQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []
 
    def push(self, x):
        self.inbox.append(x)              # always O(1)
 
    def _shift(self):
        if not self.outbox:               # ONLY when empty -- see below
            while self.inbox:
                self.outbox.append(self.inbox.pop())
 
    def pop(self):
        self._shift()
        return self.outbox.pop()
 
    def peek(self):
        self._shift()
        return self.outbox[-1]
 
    def empty(self):
        return not self.inbox and not self.outbox

Note also that empty()empty() must check both stacks. An element sitting in inboxinbox with an empty outboxoutbox still means the queue is non-empty.

Trick 3 — circular buffers

Fixed capacity with wraparound: keep a list of size kk, a headhead index, and a count.

circular_queue.py

class MyCircularQueue:
    def __init__(self, k):
        self.data = [0] * k
        self.head = 0
        self.count = 0
        self.cap = k
 
    def enQueue(self, value):
        if self.count == self.cap:
            return False
        tail = (self.head + self.count) % self.cap      # modular arithmetic
        self.data[tail] = value
        self.count += 1
        return True
 
    def deQueue(self):
        if self.count == 0:
            return False
        self.head = (self.head + 1) % self.cap
        self.count -= 1
        return True
 
    def Front(self):
        return -1 if self.count == 0 else self.data[self.head]
 
    def Rear(self):
        return -1 if self.count == 0 else self.data[(self.head + self.count - 1) % self.cap]

circular_queue.py

class MyCircularQueue:
    def __init__(self, k):
        self.data = [0] * k
        self.head = 0
        self.count = 0
        self.cap = k
 
    def enQueue(self, value):
        if self.count == self.cap:
            return False
        tail = (self.head + self.count) % self.cap      # modular arithmetic
        self.data[tail] = value
        self.count += 1
        return True
 
    def deQueue(self):
        if self.count == 0:
            return False
        self.head = (self.head + 1) % self.cap
        self.count -= 1
        return True
 
    def Front(self):
        return -1 if self.count == 0 else self.data[self.head]
 
    def Rear(self):
        return -1 if self.count == 0 else self.data[(self.head + self.count - 1) % self.cap]

Design	Per-operation cost	Space
Min Stack (paired)	$O(1)$ worst case	$O(n)$
Min Stack (second stack)	$O(1)$ worst case	$O(n)$ , smaller in practice
Two-stack queue	$O(1)$ amortised	$O(n)$
Stack from one queue	$O(n)$ push or $O(n)$ pop	$O(n)$
Circular queue	$O(1)$ worst case	$O(k)$ fixed

The variant map

Variant	The auxiliary state	Canonical problem
Stack + minimum	`(value, min_so_far)(value, min_so_far)` pairs	155
Queue from stacks	Two stacks, refill on empty	232
Stack from queues	One queue, rotate on push	225
Fixed-capacity queue	Array + `headhead` + `countcount`	622 · 641
Max in a sliding window	A monotonic deque	239
Stack with increment	Lazy pending increments per depth	1381

Building a stack from a queue cannot be $O(1)$ amortised for both operations; you must choose which side pays.

The tidiest version is costly push: after enqueueing the new element, rotate the queue by size - 1size - 1 elements so the newcomer ends up at the front. Then poppop and toptop are $O(1)$ , and pushpush is $O(n)$ .

python

def push(self, x):
    self.q.append(x)
    for _ in range(len(self.q) - 1):
        self.q.append(self.q.popleft())      # rotate the newcomer to the front

python

def push(self, x):
    self.q.append(x)
    for _ in range(len(self.q) - 1):
        self.q.append(self.q.popleft())      # rotate the newcomer to the front

Contrast with LC 232, where two stacks genuinely achieve $O(1)$ amortised on every operation. Being able to say why the queue version cannot — a single queue offers no second place to reverse into — is the interesting part.

Practice — real LeetCode problems

LC 155 — Min Stack · Medium

Problem. Design a stack supporting pushpush, poppop, toptop and getMingetMin, each in $O(1)$ time.

Constraints. -2^31 <= val <= 2^31 - 1-2^31 <= val <= 2^31 - 1, up to 3 * 10^43 * 10^4 calls, and poppop, toptop and getMingetMin are only called on a non-empty stack.

Examples. push(-2)push(-2), push(0)push(0), push(-3)push(-3), getMin()getMin() gives -3-3, pop()pop(), top()top() gives 00, getMin()getMin() gives -2-2

Editorial — approach, complexity, follow-ups

Precompute rather than query. At push time you already know the minimum of everything currently on the stack, so record it alongside the new value.

Time $O(1)$ worst case for every operation. Space $O(n)$ .

The reason a single minmin variable fails is worth stating explicitly: the minimum is not a property of the stack’s top, it is a property of the whole stack, and popping changes it in a way you cannot undo without history. Attaching the answer to each depth makes the history implicit in the structure.

The test sequence checks exactly this: after popping -3-3, getMingetMin must return -2-2 — the minimum of what remains — not -3-3, and not a rescanned value.

Follow-ups you should expect:

“Reduce the space.” A second stack holding only new minima, pushed when val <= current_minval <= current_min and popped when the popped value equals its top. Use <=<=, or duplicate minima break it.
“A max stack too?” Store a triple, or keep a symmetric second stack.
”getMingetMin on an empty stack?” LC 155 guarantees it will not happen; a robust version raises or returns a sentinel — say which you would choose.
“Increment the bottom kk elements (LC 1381)?” Keep a parallel array of pending increments and push the pending value down on pop, so the update is $O(1)$ rather than $O(k)$ .

LC 232 — Implement Queue using Stacks · Easy

Problem. Implement a FIFO queue using only two stacks. Support pushpush, poppop, peekpeek and emptyempty. Each operation must be $O(1)$ amortised.

Constraints. 1 <= x <= 91 <= x <= 9, up to 100100 calls, and poppop/peekpeek are only called on a non-empty queue.

Examples. push(1)push(1), push(2)push(2), peek()peek() gives 11, pop()pop() gives 11, empty()empty() gives FalseFalse

Editorial — approach, complexity, follow-ups

A stack reverses; two stacks reverse twice and restore FIFO order. Pushes go to inboxinbox; pops come from outboxoutbox, which is refilled by pouring inboxinbox into it (reversing it in the process).

Time $O(1)$ for pushpush and emptyempty; $O(1)$ amortised for poppop and peekpeek, with an $O(n)$ worst case on the refill. Space $O(n)$ .

The amortised proof, which is the point of the problem: each element is pushed to inboxinbox once, moved to outboxoutbox at most once, and popped from outboxoutbox at most once. So a sequence of nn operations performs at most $3n$ stack operations in total — $O(1)$ each on average.

The refill-only-when-empty condition is what guarantees the “at most once”. Refilling while outboxoutbox still has items would also be wrong, not merely slow: pouring newer elements on top of older ones destroys the FIFO order.

empty()empty() checking both stacks is the small detail that a quick implementation misses — after push(1)push(1) with nothing shifted yet, outboxoutbox is empty but the queue is not.

Follow-ups you should expect: “Prove the amortised bound” — the counting argument above. “Implement a stack using queues (LC 225)?” — asymmetric; one side must be $O(n)$ , because a single queue gives you nowhere to reverse into. “What if you could use only one stack?” — possible with recursion, using the call stack as the second stack. “Make poppop $O(1)$ worst case?” — not with this design; you would need a real deque.

LC 622 — Design Circular Queue · Medium

Problem. Implement a circular queue of fixed size kk with enQueueenQueue, deQueuedeQueue, FrontFront, RearRear, isEmptyisEmpty and isFullisFull. enQueueenQueue and deQueuedeQueue return a boolean indicating success; FrontFront and RearRear return -1-1 when empty.

Constraints. 1 <= k <= 10001 <= k <= 1000, 0 <= value <= 10000 <= value <= 1000, up to 30003000 calls.

Examples. With k = 3k = 3: enQueue(1)enQueue(1) gives TrueTrue, enQueue(2)enQueue(2) gives TrueTrue, enQueue(3)enQueue(3) gives TrueTrue, enQueue(4)enQueue(4) gives FalseFalse (full), Rear()Rear() gives 33, isFull()isFull() gives TrueTrue, deQueue()deQueue() gives TrueTrue, enQueue(4)enQueue(4) gives TrueTrue, Rear()Rear() gives 44

Editorial — approach, complexity, follow-ups

A fixed array used cyclically. headhead marks the front; the tail is derived as (head + count) % cap(head + count) % cap, so it never needs storing.

Time $O(1)$ worst case for every operation. Space $O(k)$ , fixed and allocated once.

The design decision that matters is count over tail. With headhead and tailtail alone, an empty queue and a full queue both satisfy head == tailhead == tail, so you must either sacrifice a slot (capacity kk needs k+1k+1 storage) or carry an extra boolean. Storing the count removes the ambiguity and makes isEmptyisEmpty and isFullisFull one comparison each.

The test sequence deliberately wraps: after filling all three slots and dequeuing one, enQueue(4)enQueue(4) must write into the freed slot at index 0 while headhead points at index 1. Rear()Rear() then gives 44 and Front()Front() gives 22, which only works if the modular arithmetic is right.

Returning FalseFalse rather than raising on a full enQueueenQueue is part of the specified interface — a small reminder to implement the contract you were given rather than the one you would have designed.

Follow-ups you should expect: “Why not collections.dequecollections.deque?” — a dequedeque with maxlenmaxlen silently discards on overflow instead of refusing, so it does not meet this spec; and the point is to implement the mechanics. “A circular deque (LC 641)?” — add insertFrontinsertFront, which decrements headhead modulo the capacity. “Make it resizable?” — on full, allocate a bigger array and copy in logical order; amortised $O(1)$ , exactly how dynamic arrays grow. “Thread-safe ring buffer?” — the classic single-producer/single-consumer lock-free structure, which is where this design is used in practice.

LeetCode problem set

#	Problem	Difficulty	The twist
232	Implement Queue using Stacks	Easy	Refill only when empty — the amortised argument
225	Implement Stack using Queues	Easy	Asymmetric: rotate on push, so one side is $O(n)$
155	Min Stack	Medium	Pair each value with the minimum at its depth
622	Design Circular Queue	Medium	`headhead` + `countcount`, not `headhead` + `tailtail`
641	Design Circular Deque	Medium	622 plus `insertFrontinsertFront`, decrementing `headhead` modulo capacity
1381	Design a Stack With Increment Operation	Medium	Lazy pending increments make `incrementincrement` $O(1)$ instead of $O(k)$

Interview follow-ups

They ask	What they’re checking	The answer
“Amortised or worst case?”	Precision	The two-stack queue is $O(1)$ amortised, $O(n)$ worst case for one `poppop`; Min Stack is $O(1)$ worst case
“Prove the amortised bound”	Rigour	Each element moves from `inboxinbox` to `outboxoutbox` exactly once, so `nn` operations cost $O(n)$ total
“Why not a single `minmin` variable?”	The paired-state insight	Popping the minimum leaves no record of the previous one
“Reduce Min Stack’s space”	Optimisation	A second stack holding only new minima, using `<=<=` so duplicates are handled
“Why can’t a stack-from-queues be $O(1)$ both ways?”	Understanding the asymmetry	One queue gives no second place to reverse into, so one operation must rotate
“Why `headhead` + `countcount`?”	Design judgement	`headhead` + `tailtail` makes full and empty indistinguishable
“Make it thread-safe”	Production thinking	Locks per operation, or a lock-free ring buffer for single producer/consumer

Edge-case checklist

Operations on an empty structure — LC 155 and 232 guarantee they will not happen; LC 622 requires -1-1 / FalseFalse. Implement the stated contract.
Duplicate minima (LC 155) — push(1), push(1), pop()push(1), push(1), pop(); the case that breaks a strict-<< optimisation.
Negative values — do not initialise a minimum to 00.
empty()empty() with items only in inboxinbox (LC 232) — must check both stacks.
Full queue (LC 622) — enQueueenQueue returns FalseFalse, not an exception.
Wraparound (LC 622) — dequeue then enqueue so the tail passes index 0.
Capacity 1 — a single slot that is alternately full and empty.
peekpeek not consuming — a peekpeek that pops is a common slip.

Recap

These problems test auxiliary state and amortised reasoning, not algorithms.
Min Stack: store (value, min_at_this_depth)(value, min_at_this_depth). The minimum is a property of the whole stack, so attach the answer to each depth and popping restores it for free.
Two-stack queue: inboxinbox for pushes, outboxoutbox for pops, and refill only when outboxoutbox is empty. Each element moves once, so it is $O(1)$ amortised — be ready to prove it, and to say “amortised” rather than plain $O(1)$ .
Circular buffer: track headhead and countcount, never headhead and tailtail, or full and empty become indistinguishable.
A stack from queues is inherently asymmetric — one operation must be $O(n)$ .
Deferring work until it is observed (LC 1381) turns $O(k)$ updates into $O(1)$ .

Next: Design Iterators and Flatteners — exposing a traversal one element at a time, and doing it lazily.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Design with Stacks and Queues

What you’ll learn

The cue

Trick 1 — paired state (Min Stack)

Trick 2 — the two-stack queue

Trick 3 — circular buffers

The variant map

Practice — real LeetCode problems

LC 155 — Min Stack · Medium

LC 232 — Implement Queue using Stacks · Easy

LC 622 — Design Circular Queue · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?