Queue with Stacks and Other Design Problems
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Interviewers like to ask you to build one structure from another: a queue from stacks, a stack from a queue, a stack that knows its minimum. These questions test whether you understand how each structure behaves.
A queue built from two stacks
Amortized cost is the average cost of one operation over a long run of operations. One call can be slow, but when the total stays small, each call is cheap on average.
Stacks reverse order. Move items from one stack to another and the order flips back, so the oldest item ends on top. Two stacks make a queue.
Inbox and outbox
New items go on the inbox. To serve, take from the outbox. Only when the outbox is empty, move everything from the inbox over. Never move while the outbox still has items.
class MyQueue: def __init__(self): self.inbox, self.outbox = [], []
def push(self, x): self.inbox.append(x)
def pop(self): if not self.outbox: while self.inbox: self.outbox.append(self.inbox.pop()) return self.outbox.pop()Example 1 · Two stacks make a queue
class MyQueue: def __init__(self): self.inbox = [] self.outbox = []
def push(self, x): self.inbox.append(x)
def _move(self): if not self.outbox: while self.inbox: self.outbox.append(self.inbox.pop())
def pop(self): self._move() return self.outbox.pop()
def peek(self): self._move() return self.outbox[-1]
def empty(self): return not self.inbox and not self.outbox
q = MyQueue()q.push("order 1")q.push("order 2")q.push("order 3")print(q.pop())q.push("order 4")print(q.peek())print(q.pop(), q.pop(), q.pop())print(q.empty())order 1 order 2 order 2 order 3 order 4 True
What this code does
order 1is served first even though it was pushed on a stack.order 4waits in the inbox until the outbox is empty, so the order stays first in, first out.
Example 2 · Watch the transfer
inbox = []outbox = []for x in [1, 2, 3]: inbox.append(x)print(inbox, outbox)while inbox: outbox.append(inbox.pop())print(inbox, outbox)print(outbox.pop())[1, 2, 3] [] [] [3, 2, 1] 1
What this code does
- Moving reverses the order, so the first pushed value 1 ends on top of the outbox.
- Only an empty outbox may be refilled. Otherwise new items would jump the line.
One pop can move many items, but each item moves once, so the amortized cost is O(1) per operation.
Min stack: the minimum in O(1)
How do you know the smallest value in a stack at any moment? Keep a second stack. At each push store the smallest value seen so far. Popping removes from both.
class MinStack: def __init__(self): self.items, self.mins = [], []
def push(self, x): self.items.append(x) self.mins.append(min(x, self.mins[-1]) if self.mins else x)
def pop(self): self.mins.pop() return self.items.pop()
def get_min(self): return self.mins[-1]Example 3 · Min stack
class MinStack: def __init__(self): self.items = [] self.mins = []
def push(self, x): self.items.append(x) self.mins.append(min(x, self.mins[-1]) if self.mins else x)
def pop(self): self.mins.pop() return self.items.pop()
def top(self): return self.items[-1]
def get_min(self): return self.mins[-1]
s = MinStack()for x in [5, 3, 7, 3, 8]: s.push(x) print("push", x, "min", s.get_min())s.pop()s.pop()print("after two pops min", s.get_min())push 5 min 5 push 3 min 3 push 7 min 3 push 3 min 3 push 8 min 3 after two pops min 3
What this code does
- The second stack holds the smallest value so far at every depth.
- After removing 8 and 3, the minimum goes back to 3, because the first 3 is still there.
Every operation is O(1). The cost is O(n) extra space for the second stack.
A stack from one queue
To make a queue act like a stack, put the new item at the back, then rotate the older items behind it. The newest item is now at the front.
from collections import deque
class MyStack: def __init__(self): self.q = deque()
def push(self, x): self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft())
def pop(self): return self.q.popleft()Example 4 · A stack from one queue
from collections import deque
class MyStack: def __init__(self): self.q = deque()
def push(self, x): self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft())
def pop(self): return self.q.popleft()
def top(self): return self.q[0]
s = MyStack()for x in [1, 2, 3]: s.push(x)print(s.top())print(s.pop(), s.pop(), s.pop())3 3 2 1
What this code does
- After each push the rotation moves the newest item to the front.
popleftthen returns the newest item, which is last in, first out.
Example 5 · Circular queue of fixed size
class CircularQueue: def __init__(self, capacity): self.items = [None] * capacity self.head = 0 self.size = 0
def enqueue(self, x): if self.size == len(self.items): return False self.items[(self.head + self.size) % len(self.items)] = x self.size += 1 return True
def dequeue(self): if self.size == 0: return None x = self.items[self.head] self.head = (self.head + 1) % len(self.items) self.size -= 1 return x
q = CircularQueue(3)print([q.enqueue(x) for x in [10, 20, 30, 40]])print(q.dequeue(), q.enqueue(50), q.dequeue())[True, True, True, False] 10 True 20
What this code does
- The head moves forward and wraps around with
%, so freed cells are reused. The queue is full whensizeequals the capacity. - The fourth
enqueuefails withFalse. After onedequeue, a place is free again.
Example 6 · Recent requests in the last 3000 ms
from collections import deque
class RecentCounter: def __init__(self): self.times = deque()
def ping(self, t): self.times.append(t) while self.times[0] < t - 3000: self.times.popleft() return len(self.times)
counter = RecentCounter()print([counter.ping(t) for t in [1, 100, 3001, 3002, 7000]])[1, 2, 3, 3, 1]
What this code does
- Old requests leave from the front of the deque. Each time is added once and removed once, so a ping is O(1) amortized.
- The deque never holds more than the requests of the last 3000 ms, so the space stays small.
push is O(n) here, while pop and top are O(1). The other way, with an O(1) push, makes pop O(n). One side must pay.
Next step
Check your understanding
11 quick questions