SyntaxPilot
Courses/Python Coding Questions/Lesson 24
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 24 of 30

Stack and queue questions

min stackqueue with two stacks (and why list.pop(0) is slow, collections.deque)next greater element

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 list is a perfect stack: append and pop() 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), and mins.append(min(x, mins[-1])) (just x when mins is 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 outbox is empty, pour all of inbox into it; then outbox.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 than h, pop it; its answer is h.
  • 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

  1. 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).
  2. Why is a Python list a good stack but a bad queue? append and pop() work at the end in O(1); pop(0) and insert(0, x) shift every item, O(n).
  3. How is collections.deque different from a list? O(1) at both ends (appendleft, popleft), optional maxlen; but indexing in the middle is O(n).
  4. Design a min stack. A second stack of running minimums; push/pop both; get_min reads the top. O(1) each, O(n) extra space.
  5. 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.
  6. 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).
  7. What does amortised mean? The average cost per operation over a whole sequence, even if one operation is occasionally expensive (like list.append resizing).
  8. 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).
  9. Why is the monotonic stack O(n) when it has a while inside a for? Each index is pushed once and popped at most once, so the inner loop runs at most n times in total.
  10. Where does queue.Queue fit? It's a thread-safe queue for passing work between threads; for an ordinary queue in one program, use deque.

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 (a deque: append, popleft()).
  • Min stack: one variable forgets history; a second stack of running minimums makes push, pop and get_min O(1). Always handle the empty stack.
  • list.pop(0) is O(n): never use it in a loop. collections.deque is 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.