These are the notes for Python Coding Questions, episode 24: stack and queue questions. A stack that always knows its smallest item, why list.pop(0) is painfully slow, a queue built from two stacks, collections.deque, and the monotonic stack that turns the next greater element from O(n²) into O(n).
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Timings depend on the machine and change from run to run; what matters is how they grow.
Two words we use all the time today:
- A stack is last in, first out (LIFO): you add on top (push) and take from the top (pop). A Python
listis a perfect stack:appendandpop()both work on the end in O(1). - A queue is first in, first out (FIFO): you join at the back (enqueue) and leave from the front (dequeue).
Q1: Min stack
Real-life example: a teacher's pile of checked answer sheets. Sheets go on top and come off the top. The principal keeps asking "what is the lowest mark on the pile right now?", and the answer must be instant, even while sheets come and go.
| On the teacher's desk | In Python |
|---|---|
| put a sheet on the pile | push(x): items.append(x) |
| take the top sheet | pop(): items.pop() |
| the lowest mark on the pile | get_min(), must be O(1) |
| search the whole pile | min(items): correct but O(n) per call |
The question: design a stack with push, pop and get_min, all in O(1) time.
Attempt 1: one variable for the minimum
class MinStack:
def __init__(self):
self.items = []
self.smallest = None # one variable for the minimum
def push(self, x):
self.items.append(x)
if self.smallest is None or x < self.smallest:
self.smallest = x
def pop(self):
return self.items.pop()
def get_min(self):
return self.smallest
s = MinStack()
for marks in [52, 38, 71, 25]:
s.push(marks)
print("min:", s.get_min())
print("popped:", s.pop())
print("min:", s.get_min(), " pile:", s.items)
Output:
min: 25
popped: 25
min: 25 pile: [52, 38, 71]
Wrong. After 25 leaves, the minimum should be 38, but smallest still says 25. Why: one variable remembers only the current smallest. When that item is popped, we have forgotten what the smallest was before it arrived. Recomputing with min(self.items) after every pop would be correct, but O(n).
The fix: a second stack of minimums
Keep a second stack mins next to items. mins[i] is the smallest value in items[0..i], the minimum at every height of the pile.
| items (bottom → top) | 52 | 38 | 71 | 25 |
|---|---|---|---|---|
| mins | 52 | 38 | 38 | 25 |
- push x:
items.append(x), andmins.append(min(x, mins[-1]))(justxwhenminsis empty). - pop: pop both stacks, so they always have the same height.
- get_min:
mins[-1].
All three are O(1) time. The price is O(n) extra space for mins: trading memory for speed.
class MinStack:
def __init__(self):
self.items = []
self.mins = [] # mins[i] = smallest of items[:i+1]
def push(self, x):
self.items.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop()
return self.items.pop()
def get_min(self):
return self.mins[-1]
s = MinStack()
for marks in [52, 38, 71, 25]:
s.push(marks)
print("push", marks, "-> min", s.get_min())
while s.items:
print("pop", s.pop(), "-> min", s.get_min() if s.items else None)
s.pop()
Output:
push 52 -> min 52
push 38 -> min 38
push 71 -> min 38
push 25 -> min 25
pop 25 -> min 38
pop 71 -> min 38
pop 38 -> min 52
pop 52 -> min None
Traceback (most recent call last):
File "main.py", line 23, in <module>
s.pop()
~~~~~^^
File "main.py", line 11, in pop
self.mins.pop()
~~~~~~~~~~~~~^^
IndexError: pop from empty list
Popping an empty stack raises IndexError: pop from empty list, exactly like an empty Python list. A finished class checks first and raises a clearer error, and get_min returns None on an empty stack. Note that duplicates work too: two 38s give two 38s in mins, so popping one 38 still leaves 38 as the minimum.
class MinStack:
def __init__(self):
self.items = []
self.mins = []
def push(self, x):
self.items.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
if not self.items:
raise IndexError("pop from an empty MinStack")
self.mins.pop()
return self.items.pop()
def get_min(self):
return self.mins[-1] if self.mins else None
def __len__(self):
return len(self.items)
s = MinStack()
for marks in [52, 38, 38, 71]:
s.push(marks)
s.pop(); s.pop()
print(len(s), s.get_min()) # the duplicate 38 is still counted
s.pop(); s.pop()
print(len(s), s.get_min())
try:
s.pop()
except IndexError as e:
print("IndexError:", e)
Output:
2 38
0 None
IndexError: pop from an empty MinStack
Q2: Queues, list.pop(0) and collections.deque
Real-life example: the railway ticket counter. You join at the back; the person at the front is served first.
| At the station | In Python |
|---|---|
| join at the back | append(x) |
| everyone steps forward when one person leaves | list.pop(0): every item shifts left, O(n) |
| the clerk calls the next token, nobody moves | deque.popleft(): O(1) |
A Python list stores its items side by side in memory. Removing the first item means moving every other item one place to the left. One pop(0) is O(n), so serving a whole line of n people is O(n²).
A deque (say "deck"), a double-ended queue from collections, adds and removes at both ends in O(1): append, appendleft, pop, popleft.
import time
from collections import deque
n = 200_000
line = list(range(n)) # people waiting at the ticket counter
start = time.perf_counter()
while line:
line.pop(0) # serve the person at the front
print(f"list.pop(0): {time.perf_counter() - start:.3f} s")
line = deque(range(n))
start = time.perf_counter()
while line:
line.popleft()
print(f"deque.popleft(): {time.perf_counter() - start:.3f} s")
Output (one run; your times will differ):
list.pop(0): 3.236 s
deque.popleft(): 0.007 s
Hundreds of times faster for the same line. time.perf_counter() is a high-resolution clock for measuring short durations.
Interview twist: a queue from two stacks
Real-life example: an office clerk with two trays. New forms go into the inbox tray (a stack: newest on top). To serve the oldest form, flip the whole inbox into the outbox tray: flipping a stack reverses it, so the oldest form is now on top.
Attempt 1: pour every time
class Queue:
def __init__(self):
self.inbox = [] # new people join here
self.outbox = [] # people are served from here
def enqueue(self, x):
self.inbox.append(x)
def dequeue(self):
while self.inbox: # pour inbox into outbox, every time
self.outbox.append(self.inbox.pop())
return self.outbox.pop()
q = Queue()
q.enqueue("Asha"); q.enqueue("Ravi")
print(q.dequeue())
q.enqueue("Neha")
print(q.dequeue())
print(q.dequeue())
Output:
Asha
Neha
Ravi
Wrong order: Ravi was waiting before Neha joined. Why: Ravi was already in the outbox; pouring Neha in put her on top of Ravi, so she jumped the line.
The fix: pour only when the outbox is empty
- enqueue:
inbox.append(x). - dequeue: if
outboxis empty, pour all ofinboxinto it; thenoutbox.pop().
One pour can take O(n), but each item is moved at most once in its life (inbox → outbox). Over any sequence of operations the total work is O(number of operations), so each operation costs amortised O(1): O(1) on average, even if a single one is occasionally slow.
class Queue:
def __init__(self):
self.inbox = []
self.outbox = []
def enqueue(self, x):
self.inbox.append(x)
def dequeue(self):
if not self.outbox: # pour ONLY when outbox is empty
while self.inbox:
self.outbox.append(self.inbox.pop())
return self.outbox.pop()
q = Queue()
q.enqueue("Asha"); q.enqueue("Ravi")
print(q.dequeue())
q.enqueue("Neha")
print(q.dequeue())
print(q.dequeue())
from collections import deque
d = deque(["Asha", "Ravi"])
d.append("Neha")
print(d.popleft(), d.popleft(), d)
d.popleft(); d.popleft()
Output:
Asha
Ravi
Neha
Asha Ravi deque(['Neha'])
Traceback (most recent call last):
File "main.py", line 26, in <module>
d.popleft(); d.popleft()
~~~~~~~~~^^
IndexError: pop from an empty deque
The right order. And popleft() on an empty deque raises IndexError: pop from an empty deque: check if line: first. In real code, use deque; the two-stack queue is an interview question about thinking.
A few more deque tools: maxlen keeps only the last few items (old ones fall off the other end), rotate, indexing at the ends, len and in.
from collections import deque
d = deque(maxlen=3) # keeps only the last 3 items
for order in ["chai", "samosa", "vada pav", "dosa"]:
d.append(order)
print(d)
d.rotate(1) # the last item moves to the front
print(d, d[0], d[-1])
print(len(d), "dosa" in d)
Output:
deque(['samosa', 'vada pav', 'dosa'], maxlen=3)
deque(['dosa', 'samosa', 'vada pav'], maxlen=3) dosa vada pav
3 True
Q3: Next greater element
Real-life example: a row of buildings with heights 4, 5, 2, 10, 8. Each building looks to its right for the first building that is taller (the one that blocks its view). Four sees 5, five sees 10, two sees 10. Ten and eight have nobody taller to their right: answer -1.
The question: for each item, the first item to its right that is strictly greater, or -1.
Attempt 1: look right, one by one
import time
def next_greater(heights):
result = []
for i in range(len(heights)):
answer = -1
for j in range(i + 1, len(heights)): # look right, one by one
if heights[j] > heights[i]:
answer = heights[j]
break
result.append(answer)
return result
print(next_greater([4, 5, 2, 10, 8]))
for n in [3_000, 6_000, 12_000]:
falling = list(range(n, 0, -1)) # nobody taller to the right
start = time.perf_counter()
next_greater(falling)
print(n, f"{time.perf_counter() - start:.2f} s")
Output (one run):
[5, 10, 10, -1, -1]
3000 0.11 s
6000 0.44 s
12000 1.85 s
Correct, but double n → about 4× the time. With falling heights every building scans to the end: about n²/2 comparisons, O(n²). A million buildings would take hours.
The fix: a monotonic stack of buildings still waiting
Flip the question: instead of each building looking right, let each new building answer everyone on its left who is still waiting.
- Keep a stack of indexes still waiting for a taller building.
- For a new height
h: while the top of the stack is shorter thanh, pop it; its answer ish. - Then push the new index (it is waiting too). Whatever is left at the end keeps -1.
The heights on the stack always decrease from bottom to top, so it is called a monotonic stack (monotonic = always going one way). Every index is pushed once and popped at most once: O(n) time, O(n) space.
| new height | pops (answer = new height) | stack after (heights) |
|---|---|---|
| 4 | - | 4 |
| 5 | 4 → 5 | 5 |
| 2 | - | 5 2 |
| 10 | 2 → 10, 5 → 10 | 10 |
| 8 | - | 10 8 |
import time
def next_greater(heights):
result = [-1] * len(heights)
stack = [] # indexes still waiting for an answer
for i, h in enumerate(heights):
while stack and heights[stack[-1]] < h:
result[stack.pop()] = h # h is their next greater
stack.append(i)
return result
print(next_greater([4, 5, 2, 10, 8]))
print(next_greater([3, 3, 1]), next_greater([]))
for n in [12_000, 1_000_000]:
falling = list(range(n, 0, -1))
start = time.perf_counter()
next_greater(falling)
print(n, f"{time.perf_counter() - start:.2f} s")
Output (one run):
[5, 10, 10, -1, -1]
[-1, -1, -1] []
12000 0.00 s
1000000 0.08 s
Equal heights are not "greater" (we use <, strict), so [3, 3, 1] gives all -1. We store indexes, not heights, so we know where to write each answer.
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
one self.smallest variable |
min: 25 after 25 was popped |
it forgets the earlier minimum | a second stack mins |
stack.pop() on an empty list |
IndexError: pop from empty list |
nothing to pop | if stack: first, or raise a clear error |
mins[-1] on an empty stack |
IndexError: list index out of range |
no top | return None when empty |
line.pop(0) in a loop |
seconds for 200,000 items | every pop shifts all items: O(n) | collections.deque.popleft() |
| pouring inbox → outbox every time | Asha, Neha, Ravi |
new items land on older ones | pour only when outbox is empty |
deque.popleft() on an empty deque |
IndexError: pop from an empty deque |
the line is empty | if line: first |
| nested loops for next greater | double n → 4× the time | O(n²) | a monotonic stack, O(n) |
| storing heights instead of indexes | can't tell where to write the answer | values repeat | push indexes |
<= instead of < in the stack loop |
equal heights counted as "greater" | wrong comparison | strict < |
Your turn: days until a warmer day (solution)
Question: a summer in Delhi. For each day, how many days until a warmer day? 0 if it never gets warmer. For [31, 33, 30, 29, 35, 34] the answer is [1, 3, 2, 1, 0, 0].
Idea: the same waiting stack, but store days (indexes); when a warmer day pops an earlier one, the answer is day - earlier. O(n) time, O(n) space.
def days_to_warmer(temps):
wait = [0] * len(temps)
stack = [] # days still waiting for a warmer one
for day, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
earlier = stack.pop()
wait[earlier] = day - earlier
stack.append(day)
return wait
print(days_to_warmer([31, 33, 30, 29, 35, 34]))
Output:
[1, 3, 2, 1, 0, 0]
Mini project: browser Back and Forward
A browser's history is two stacks: Back holds the pages you came from, Forward holds the pages you went back from. A new visit clears Forward. Every operation is O(1).
class History:
"""Browser history: Back and Forward are two stacks."""
def __init__(self, home):
self.current = home
self.back_stack = []
self.forward_stack = []
def visit(self, page):
self.back_stack.append(self.current)
self.current = page
self.forward_stack.clear() # a new visit wipes Forward
def back(self):
if self.back_stack:
self.forward_stack.append(self.current)
self.current = self.back_stack.pop()
return self.current
def forward(self):
if self.forward_stack:
self.back_stack.append(self.current)
self.current = self.forward_stack.pop()
return self.current
h = History("syntaxpilot.in")
h.visit("notes"); h.visit("python"); h.visit("quiz")
print(h.back(), h.back(), h.forward())
h.visit("compiler")
print(h.forward(), h.back(), h.back(), h.back(), h.back())
Output:
python notes python
compiler python notes syntaxpilot.in syntaxpilot.in
Practice questions (with solutions)
1. A max stack: push, pop, get_max, all O(1).
Solution
The same idea as the min stack, with max. Each pair below is (max before the pop, popped value).
class MaxStack:
def __init__(self):
self.items, self.maxes = [], []
def push(self, x):
self.items.append(x)
self.maxes.append(x if not self.maxes else max(x, self.maxes[-1]))
def pop(self):
self.maxes.pop()
return self.items.pop()
def get_max(self):
return self.maxes[-1]
s = MaxStack()
for x in [3, 9, 4, 9, 1]:
s.push(x)
out = []
while s.items:
out.append((s.get_max(), s.pop()))
print(out)
Output:
[(9, 1), (9, 9), (9, 4), (9, 9), (3, 3)]
2. A stack from two queues (the reverse of today's twist).
Solution
Make push do the work: put the new item in a fresh queue, then move the old items behind it, so the newest is always at the front. Push is O(n), pop is O(1).
from collections import deque
class Stack:
"""A stack built from two queues: push is O(n), pop is O(1)."""
def __init__(self):
self.q = deque()
def push(self, x):
helper = deque([x])
while self.q: # put the old items behind x
helper.append(self.q.popleft())
self.q = helper
def pop(self):
return self.q.popleft()
s = Stack()
for x in "abc":
s.push(x)
print(s.pop(), s.pop())
s.push("d")
print(s.pop(), s.pop())
Output:
c b
d a
3. Previous smaller element: for each item, the nearest item to its left that is strictly smaller, or -1.
Solution
A monotonic stack again, walking left to right: pop everything >= x (it can never be the answer for anything after x), then the top is the answer. O(n).
def previous_smaller(nums):
result, stack = [], [] # stack of values, rising bottom to top
for x in nums:
while stack and stack[-1] >= x:
stack.pop()
result.append(stack[-1] if stack else -1)
stack.append(x)
return result
print(previous_smaller([4, 5, 2, 10, 8]))
print(previous_smaller([1, 2, 3]), previous_smaller([3, 2, 1]))
Output:
[-1, 4, -1, 2, 2]
[-1, 1, 2] [-1, -1, -1]
4. Next greater element in a circle: the buildings stand around a lake, so after the last one you continue from the first.
Solution
Walk the list twice (i % n), but only push indexes in the first round. O(n).
def next_greater_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n): # walk the circle twice
h = nums[i % n]
while stack and nums[stack[-1]] < h:
result[stack.pop()] = h
if i < n:
stack.append(i)
return result
print(next_greater_circular([4, 5, 2, 10, 8]))
print(next_greater_circular([1, 2, 1]))
Output:
[5, 10, 10, -1, 10]
[2, -1, 2]
Quick quiz
What does this print?
from collections import deque
d = deque([1, 2, 3])
d.append(4)
d.appendleft(0)
d.pop()
print(d.popleft(), list(d))
(A) 0 [1, 2, 3] (B) 1 [2, 3, 4] (C) 4 [0, 1, 2] (D) 0 [1, 2, 3, 4]
Answer
(A). After append(4) and appendleft(0) the deque is [0, 1, 2, 3, 4]. pop() with no argument removes from the right end (the 4). popleft() returns 0, leaving [1, 2, 3].
from collections import deque
d = deque([1, 2, 3])
d.append(4)
d.appendleft(0)
d.pop()
print(d.popleft(), list(d))
Output:
0 [1, 2, 3]
Interview questions
- Stack vs queue? A stack is LIFO (undo, Back button, function calls, matching brackets); a queue is FIFO (print jobs, ticket lines, breadth-first search).
- Why is a Python list a good stack but a bad queue?
appendandpop()work at the end in O(1);pop(0)andinsert(0, x)shift every item, O(n). - How is
collections.dequedifferent from a list? O(1) at both ends (appendleft,popleft), optionalmaxlen; but indexing in the middle is O(n). - Design a min stack. A second stack of running minimums; push/pop both;
get_minreads the top. O(1) each, O(n) extra space. - Can a min stack use O(1) extra space? Yes, with a trick that stores encoded differences instead of a second stack; it's harder to read and rarely worth it in Python.
- Queue with two stacks: what is the cost? Amortised O(1) per operation: each item moves from inbox to outbox at most once. The worst single dequeue is O(n).
- What does amortised mean? The average cost per operation over a whole sequence, even if one operation is occasionally expensive (like
list.appendresizing). - What is a monotonic stack? A stack whose values always increase (or always decrease) from bottom to top; it answers "next/previous greater/smaller" questions in O(n).
- Why is the monotonic stack O(n) when it has a
whileinside afor? Each index is pushed once and popped at most once, so the inner loop runs at most n times in total. - Where does
queue.Queuefit? It's a thread-safe queue for passing work between threads; for an ordinary queue in one program, usedeque.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Stack | Last in, first out | a pile of answer sheets |
| LIFO | Last In, First Out | append then pop() |
| Push | Add to the top of a stack | items.append(x) |
| Pop | Remove from the top of a stack | items.pop() |
| Top | The last item pushed | items[-1] |
| Queue | First in, first out | a ticket counter line |
| FIFO | First In, First Out | append then popleft() |
| Enqueue / dequeue | Join the back / leave the front of a queue | q.enqueue("Asha") |
| Min stack | A stack that returns its minimum in O(1) | get_min() |
| Running minimum | The smallest value so far, at each position | mins = [52, 38, 38, 25] |
IndexError |
An index or pop that has nothing there | pop from empty list |
collections.deque |
A double-ended queue, O(1) at both ends | deque([1, 2]) |
popleft / appendleft |
Remove / add at the left end of a deque | d.popleft() |
maxlen |
A deque that keeps only the last N items | deque(maxlen=3) |
time.perf_counter() |
A precise clock for timing code | start = time.perf_counter() |
| Amortised O(1) | O(1) on average over many operations | the two-stack queue |
| Next greater element | The first strictly greater item to the right | 4 → 5 |
| Monotonic stack | A stack kept in increasing or decreasing order | today's Q3 |
enumerate |
Loop with index and value together | for i, h in enumerate(heights) |
| O(n²) | Time grows with the square of n: double n, 4× time | nested loops |
| O(n) | Time grows in step with n | one pass |
Summary
- Stack = LIFO (a list:
append,pop()); queue = FIFO (adeque:append,popleft()). - Min stack: one variable forgets history; a second stack of running minimums makes
push,popandget_minO(1). Always handle the empty stack. list.pop(0)is O(n): never use it in a loop.collections.dequeis O(1) at both ends.- Queue from two stacks: pour inbox into outbox only when outbox is empty; amortised O(1).
- Next greater element: nested loops are O(n²); a monotonic stack of indexes still waiting answers everyone in O(n).
- Next episode: hashing questions: an LRU cache with
OrderedDict, group anagrams, and the longest consecutive sequence.