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:

1. Can you carry auxiliary state alongside the data, rather than computing properties on demand?
2. 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) 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

You are looking at this pattern when…

• “Implement X using Y” where X and Y are different primitives — 232, 225.
• A stack or queue must also answer a query about its contents in $O(1)$ — 155 minimum, 895 maximum frequency.
• Fixed capacity with wraparound — 622, 641.
• You are asked for $O(1)$ amortised rather than $O(1)$ worst case. That wording is a strong hint that an occasional expensive step is expected.

Amortised versus worst case — say which you mean

Term	Meaning
$O(1)$ worst case	Every call is constant time
$O(1)$ amortised	Any sequence of n 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 pop. 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.

Visual intuition

Every design in this page keeps a second piece of state alongside the stack — a running minimum, a second stack, a pair of indices. Watch the stack panel here: the input row is consumed left to right while the stack holds only what is still unresolved.

stackThe stack holds exactly what is still outstandingthe shape every design on this page reuses

(0[1{2}3]4)5(6)7

stack (top)

empty

bottom

open0

1def is_valid(s):2    pairs = {')': '(', ']': '[', '}': '{'}3    stack = []4    for ch in s:5        if ch not in pairs:6            stack.append(ch)          # an opener7        elif not stack or stack.pop() != pairs[ch]:8            return False              # mismatch, or nothing to close9    return not stack                  # leftovers mean unclosed

setupThe stack holds openers that have not been closed yet. Its depth is the current nesting level, and the top is always the one that must close next — which is exactly what "properly nested" means.

Play‹›1/10⟲

That framing is what the design problems build on: a Min Stack pairs each pushed value with the minimum at the time of pushing, so the extra state is popped in lockstep; the two-stack queue keeps an inbox and an outbox and moves items across only when the outbox runs dry. In both cases the second structure is maintained by the same push/pop rhythm you see here.

Trick 1 — paired state (Min Stack)

The naive getMin scans the stack: $O(n)$. Keeping a single min 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

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

Why a single min variable cannot work

Push 5, then 3. min is 3. Now pop. The minimum should return to 5, but that value was never recorded anywhere — you would have to rescan.

Pairing each element with the minimum below or at its own depth means popping automatically restores the correct earlier minimum, because the previous entry still carries it. The stack’s structure does the bookkeeping for you.

The space optimisation worth mentioning: keep a second stack that only receives a value when it is less than or equal to the current minimum, and pops only when the popped value equals its top. That uses less space in the common case. The <= matters — with strict <, duplicate minima are recorded once but popped twice, and you lose the minimum early.

Trick 2 — the two-stack queue

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

• inbox receives every push.
• outbox serves every pop and peek.
• When outbox is empty, pour the whole inbox 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

“Only when empty” is the entire algorithm

Shifting unconditionally — on every pop — would move elements repeatedly and make the whole thing $O(n)$ per operation.

Shifting only when outbox is empty means each element is moved exactly once from inbox to outbox in its whole lifetime. So n operations perform at most n moves in total: $O(1)$ amortised.

That is the amortised argument, and it is the answer to “prove your complexity”. The accounting view: each push pre-pays for the one move its element will eventually make.

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

Trick 3 — circular buffers

Fixed capacity with wraparound: keep a list of size k, a head 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]

Track a count, not a tail pointer

Storing head and tail alone makes full and empty indistinguishable — both give head == tail. The classic workarounds are to waste one slot or keep a boolean flag.

Storing head and count avoids the ambiguity entirely: empty is count == 0, full is count == cap, and the tail is derived. Fewer states, fewer bugs.

Dry run

The two-stack queue, counting the moves

Eight operations on MyQueue. The column that matters is the last one — how many elements crossed from inbox to outbox on this call.

#	Call	inbox	outbox	Returns	Moves this call
1	push(1)	[1]	[]	—	0
2	push(2)	[1, 2]	[]	—	0
3	pop()	[]	[2]	1	2
4	push(3)	[3]	[2]	—	0
5	push(4)	[3, 4]	[2]	—	0
6	pop()	[3, 4]	[]	2	0
7	pop()	[]	[4]	3	2
8	pop()	[]	[]	4	0

Total moves across all eight calls: 4 — exactly the number of pushes, no more. Two calls did $O(n)$ work and six did $O(1)$, but no element was ever moved twice.

Step 6 is the one to point at in an interview. outbox is non-empty, so _shift returns immediately even though inbox has two items waiting. Those items are not stale — they are younger than 2, and FIFO says they must not be served yet. The “only when empty” guard is what enforces the ordering and what bounds the total work; it is one condition doing both jobs.

Step 3 also shows the reversal: inbox was [1, 2] with 2 on top, and after pouring, outbox is [2, 1] with 1 on top — popped immediately as the return value, leaving [2]. Two reversals restore the original order.

The circular queue wrapping around

Capacity 3, and the interesting moment is the enqueue after a dequeue, when tail wraps to index 0 while head sits at 1.

Call	data	head	count	derived tail	Returns	Front / Rear
enQueue(1)	[1, 0, 0]	0	1	0	True	1 / 1
enQueue(2)	[1, 2, 0]	0	2	1	True	1 / 2
enQueue(3)	[1, 2, 3]	0	3	2	True	1 / 3
enQueue(4)	[1, 2, 3]	0	3	2	False	1 / 3
deQueue()	[1, 2, 3]	1	2	2	True	2 / 3
enQueue(5)	[5, 2, 3]	1	3	0	True	2 / 5
deQueue()	[5, 2, 3]	2	2	0	True	3 / 5
deQueue()	[5, 2, 3]	0	1	0	True	5 / 5
deQueue()	[5, 2, 3]	1	0	—	True	-1 / -1
deQueue()	[5, 2, 3]	1	0	—	False	-1 / -1

Three things the trace makes concrete:

• data is never cleared. After the last dequeue the array still reads [5, 2, 3], and that is correct — count == 0 is the only thing that makes the queue empty. Zeroing slots on dequeue is wasted work, and reading a slot outside the live window is the actual bug.
• The wrap is invisible in the state. At enQueue(5), head = 1 and count = 2, so tail = (1 + 2) % 3 = 0. Nothing special-cased it; the modulo did all of it.
• Rows 4 and 9 are the ambiguity that count removes. After enQueue(3) the queue is full with head = 0; after the third dequeue it is empty with head = 1 — but run one more cycle and the pointers coincide. A head/tail pair gives head == tail for both full and empty and cannot tell them apart. count distinguishes 3 from 0 with no extra slot and no flag.

Min Stack with duplicate minima

Push 5, 3, 7, 3, then pop twice. Each entry carries the minimum at its own depth.

Call	Stack (value, min)	getMin()
push(5)	(5,5)	5
push(3)	(5,5) (3,3)	3
push(7)	(5,5) (3,3) (7,3)	3
push(3)	(5,5) (3,3) (7,3) (3,3)	3
pop()	(5,5) (3,3) (7,3)	3
pop()	(5,5) (3,3)	3

The duplicate 3 is recorded twice, once at depth 2 and once at depth 4. That redundancy is the point: after the first pop the minimum is still 3, because the deeper copy survives. This is the case that breaks the space-optimised second-stack variant when it is written with a strict < — the duplicate never gets pushed to the min stack, so the first pop removes the only copy and getMin starts reporting 5 while a 3 is still in the main stack. Use <=.

Complexity

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) pairs	155
Queue from stacks	Two stacks, refill on empty	232
Stack from queues	One queue, rotate on push	225
Fixed-capacity queue	Array + head + count	622 · 641
Max in a sliding window	A monotonic deque	239
Stack with increment	Lazy pending increments per depth	1381

LC 225 — a stack from queues is asymmetric

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 - 1 elements so the newcomer ends up at the front. Then pop and top are $O(1)$, and push 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

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 push, pop, top and getMin, each in $O(1)$ time.

Constraints. -2^31 <= val <= 2^31 - 1, up to 3 * 10^4 calls, and pop, top and getMin are only called on a non-empty stack.

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

pch.exerciseTag pch.exerciseTitle

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 min 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, getMin must return -2 — the minimum of what remains — not -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_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.
• “getMin 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 k 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 push, pop, peek and empty. Each operation must be $O(1)$ amortised.

Constraints. 1 <= x <= 9, up to 100 calls, and pop/peek are only called on a non-empty queue.

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

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

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

Time $O(1)$ for push and empty; $O(1)$ amortised for pop and peek, 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 inbox once, moved to outbox at most once, and popped from outbox at most once. So a sequence of n 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 outbox still has items would also be wrong, not merely slow: pouring newer elements on top of older ones destroys the FIFO order.

empty() checking both stacks is the small detail that a quick implementation misses — after push(1) with nothing shifted yet, outbox 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 pop $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 k with enQueue, deQueue, Front, Rear, isEmpty and isFull. enQueue and deQueue return a boolean indicating success; Front and Rear return -1 when empty.

Constraints. 1 <= k <= 1000, 0 <= value <= 1000, up to 3000 calls.

Examples. With k = 3: enQueue(1) gives True, enQueue(2) gives True, enQueue(3) gives True, enQueue(4) gives False (full), Rear() gives 3, isFull() gives True, deQueue() gives True, enQueue(4) gives True, Rear() gives 4

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

A fixed array used cyclically. head marks the front; the tail is derived as (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 head and tail alone, an empty queue and a full queue both satisfy head == tail, so you must either sacrifice a slot (capacity k needs k+1 storage) or carry an extra boolean. Storing the count removes the ambiguity and makes isEmpty and isFull one comparison each.

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

Returning False rather than raising on a full enQueue 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.deque?” — a deque with maxlen 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 insertFront, which decrements head 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

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 1381 is the laziness trick in miniature

“Increment the bottom k elements” is $O(k)$ if you do it eagerly. The $O(1)$ design keeps a parallel pending array: increment(k, v) records v at index k - 1 only. On pop, you add the pending value at that index to the returned element and push the pending value down one slot before discarding it.

Each element therefore collects every increment that applied to it, but only at the moment it leaves. Deferring work until someone actually observes the result is a broadly useful design idea — the same instinct behind lazy propagation in segment trees.

6 problems

2 easy4 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○225Implement Stack using QueueseasyAsymmetric: rotate on push, so one side is $O(n)$
• ○232Implement Queue using StackseasyRefill only when empty -- the amortised argument
• ○155Min StackmediumPair each value with the minimum at its depthNeetCode 150LeetCode Top Interview 150
• ○622Design Circular Queuemedium`head` + `count`, not `head` + `tail`
• ○641Design Circular Dequemedium622 plus `insertFront`, decrementing `head` modulo capacity
• ○1381Design a Stack With Increment OperationmediumLazy pending increments make `increment` $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 pop; Min Stack is $O(1)$ worst case
“Prove the amortised bound”	Rigour	Each element moves from inbox to outbox exactly once, so n operations cost $O(n)$ total
“Why not a single min 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 head + count?”	Design judgement	head + tail 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 / False. Implement the stated contract.
• Duplicate minima (LC 155) — push(1), push(1), pop(); the case that breaks a strict-< optimisation.
• Negative values — do not initialise a minimum to 0.
• empty() with items only in inbox (LC 232) — must check both stacks.
• Full queue (LC 622) — enQueue returns False, 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.
• peek not consuming — a peek that pops is a common slip.

Self-check

pch.quizTag pch.quizDefaultTitle

1. In the two-stack queue, why does `_shift` refill `outbox` only when it is empty?

   A It is a micro-optimisation; refilling every time is also O(1) amortised B Refilling while `outbox` is non-empty would both break FIFO order and make every operation O(n) C Python lists cannot be extended while non-empty D It keeps the two stacks the same length
   pch.quizShowAnswer

   B — Refilling while `outbox` is non-empty would both break FIFO order and make every operation O(n) — Two separate failures in one guard. Correctness: items still in `outbox` are older than everything in `inbox`, so pouring on top would serve younger items first. Cost: the guard is what makes each element move exactly once in its lifetime, giving n operations at most n moves. Refill unconditionally and a single element can be moved on every call -- O(n) per operation, not amortised anything.

2. You claim your two-stack queue is O(1). The interviewer asks you to be precise. What is the honest answer?

   A O(1) worst case -- each call touches a constant number of stack slots B O(1) amortised; a single `pop` is O(n) worst case when it triggers the refill C O(log n) amortised, because the refill halves the inbox D O(n) -- the amortised bound only applies to `push`
   pch.quizShowAnswer

   B — O(1) amortised; a single `pop` is O(n) worst case when it triggers the refill — The refilling `pop` moves the whole inbox and is genuinely O(n). What is bounded is the total: across n operations the refills move at most n elements, so the average is constant. LC 232 asks for amortised O(1) precisely because it wants this design. Quoting flat O(1) is wrong and interviewers do notice.

3. Min Stack: you store only a single `min` variable instead of pairing each element with its minimum. What breaks?

   A `push` becomes O(n) B `getMin` returns a stale value after popping the current minimum, because the previous minimum was never recorded C Nothing -- a single variable is the standard space optimisation D It breaks only when the stack contains negative numbers
   pch.quizShowAnswer

   B — `getMin` returns a stale value after popping the current minimum, because the previous minimum was never recorded — Push 5 then 3, so `min` is 3. Pop. The answer should return to 5, but 5 was overwritten and nothing remembers it -- you would have to rescan the stack, which is the O(n) you were avoiding. Pairing each element with the minimum at its own depth means popping automatically uncovers the correct earlier minimum.

4. In the space-optimised Min Stack (a second stack holding only the minima), why must the push condition be `<=` rather than `<`?

   A `<` would push too many duplicates and waste space B With `<`, a duplicated minimum is recorded once but popped twice, so `getMin` reports a value that is too large while the real minimum is still in the stack C `<` breaks when the stack is empty D The two are equivalent; `<=` is only a style convention
   pch.quizShowAnswer

   B — With `<`, a duplicated minimum is recorded once but popped twice, so `getMin` reports a value that is too large while the real minimum is still in the stack — Push 3, then 3 again. With strict `<` the second 3 is not recorded. Now pop once: the popped value equals the min-stack top, so the min stack pops too -- and the surviving 3 in the main stack has no representative. `getMin` jumps to whatever is below. With `<=` both copies are recorded and the pops stay in lockstep.

5. A circular queue stores `head` and `tail` instead of `head` and `count`. What goes wrong?

   A Wraparound requires a special case that modular arithmetic cannot express B Full and empty both satisfy `head == tail`, so the two states are indistinguishable C `Rear` becomes O(k) D Nothing -- but it uses more memory
   pch.quizShowAnswer

   B — Full and empty both satisfy `head == tail`, so the two states are indistinguishable — That collision is the whole reason ring buffers are fiddly. The classic workarounds are to waste one slot (full means the next tail would land on head) or to carry a boolean flag. Storing `count` removes the ambiguity outright: empty is `count == 0`, full is `count == cap`, and the tail is derived.

6. Implementing a stack from a single queue: what is the cost profile?

   A O(1) for both push and pop B O(n) on one of the two operations -- you rotate the queue so the newest element is at the front C O(log n) push, O(1) pop D It is impossible with one queue
   pch.quizShowAnswer

   B — O(n) on one of the two operations -- you rotate the queue so the newest element is at the front — Push, then rotate the other n-1 elements to the back so the just-pushed element sits at the front: O(n) push, O(1) pop. Or push cheaply and rotate at pop time instead. Either way the cost is paid on one side and it is genuinely O(n) per call -- unlike the two-stack queue, no amortisation saves you, because the rotation repeats on every operation.

Recall card

• The shape — a design problem is a data structure plus one extra piece of state maintained by the same push/pop rhythm. Find the extra state and the problem is solved.
• Min Stack — store (value, min_at_this_depth). Popping restores the earlier minimum for free. $O(1)$ worst case, $O(n)$ space. Second-stack variant: push on <=, never <.
• Two-stack queue — inbox takes pushes, outbox serves pops, refill only when outbox is empty. Each element moves exactly once, so $O(1)$ amortised, $O(n)$ worst case on a single pop. Say “amortised” out loud.
• empty() must check both stacks — an item in inbox with an empty outbox is still an item.
• Circular queue — keep head and count, derive the tail. A head/tail pair cannot distinguish full from empty.
• Never clear slots on dequeue. count defines what is live; the stale bytes are harmless.
• Stack from one queue is $O(n)$ on one side, with no amortisation to rescue it — the rotation repeats every call.

Recap

• These problems test auxiliary state and amortised reasoning, not algorithms.
• Min Stack: store (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: inbox for pushes, outbox for pops, and refill only when outbox 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 head and count, never head and tail, 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.