Stacks and Queues Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes stacks, monotonic stacks, deques and design problems. Read the clue first, name the structure, then write the code and state its cost.
Stack clues: nested, newest first, undo
Brackets, undo, pending work and "cancel the last one" all point to a stack. Ask: does the newest unfinished item decide what happens next?
def clean(tokens): stack = [] for token in tokens: if token == "undo": if stack: stack.pop() else: stack.append(token) return stack
print(clean(["a", "b", "undo", "c"]))Example 1 · Score record with cancel and double
scores = []for token in ["5", "2", "C", "D", "+"]: if token == "C": scores.pop() elif token == "D": scores.append(scores[-1] * 2) elif token == "+": scores.append(scores[-1] + scores[-2]) else: scores.append(int(token))print(scores, sum(scores))[5, 10, 15] 30
What this code does
Ccancels the last score,Ddoubles it and+adds the last two. All of them look at the newest entries, so a stack fits.- After
5 2 Cthe list is[5].Dadds 10 and+adds 15.
Push normal work and pop on undo. The cost is O(n) time and O(n) space.
Monotonic stack clues: nearest bigger or smaller
A question about the next greater, next smaller, a span or the largest rectangle needs a stack that keeps one order. Keep unanswered items and pop those the new value answers.
def next_smaller(nums): result = [-1] * len(nums) stack = [] for i, value in enumerate(nums): while stack and nums[stack[-1]] > value: result[stack.pop()] = value stack.append(i) return result
print(next_smaller([4, 8, 5, 2, 7]))Example 2 · Next smaller to the right
def next_smaller(nums): result = [-1] * len(nums) stack = [] for i, value in enumerate(nums): while stack and nums[stack[-1]] > value: result[stack.pop()] = value stack.append(i) return result
print(next_smaller([4, 8, 5, 2, 7]))[2, 5, 2, -1, -1]
What this code does
- The waiting values rise from bottom to top. A smaller value answers every bigger one it pops.
- 4 waits for 2, 8 and 5 are answered by 5 and 2, and 7 has nothing after it.
Only the comparison changes from next greater. Every index is pushed and popped once, so the time is O(n).
Queue clues: first come, first served
Fair order, a line, level by level, and a window of the last items point to a queue. Use deque, never list.pop(0).
from collections import deque
last = deque(maxlen=3)total = 0for price in [10, 20, 30, 40, 50]: last.append(price) total = sum(last)print(list(last), total)Example 3 · Moving average of the last 3
from collections import deque
window = deque(maxlen=3)total = 0for value in [4, 6, 8, 2, 10]: if len(window) == 3: total -= window[0] window.append(value) total += value print(round(total / len(window), 2))4.0 5.0 6.0 5.33 6.67
What this code does
- The running total is updated in O(1): subtract the item that is about to leave and add the new one.
- Before three values exist, the average is over fewer items.
maxlen drops the oldest price on its own. Summing 3 items is O(1) because the window has a fixed size.
Design clues: build one from another
A queue from two stacks moves the inbox to the outbox only when the outbox is empty. A min stack keeps a second stack of minimums. State the cost in plain words: amortized O(1) per operation.
inbox, outbox = [1, 2, 3], []if not outbox: while inbox: outbox.append(inbox.pop())print(outbox.pop())Each item moves once, so a long run of operations is O(n) in total.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Check "{[()()]}" for valid brackets with a stack. Print True or False.
True
Exercise 2· Easy
Evaluate the postfix expression 2 3 4 * + and print the result.
14
Exercise 3· Easy
Print the next greater value of each item of [6, 3, 8, 1, 9], with -1 when there is none.
[8, 8, 9, 9, -1]
Exercise 4· Medium
Serve ["Asha", "Ben", "Chen", "Dia"] as a queue but Ben and Dia each let the others go first: they are sent to the back of the line once. Print the order in which people are finally served.
['Asha', 'Chen', 'Ben', 'Dia']
Exercise 5· Medium
Print the days to wait for a warmer day for [70, 71, 69, 72, 68, 73].
[1, 2, 1, 2, 1, 0]
Exercise 6· Medium
A min stack receives pushes [7, 4, 9, 4, 2]. Print the minimum after each push, then after one pop.
[7, 4, 4, 4, 2] 4
Exercise 7· Hard
Print the maximum of every window of 3 in [1, 5, 2, 8, 3, 9] using a deque of indexes.
[5, 8, 8, 9]
Exercise 8· Hard
Largest rectangle: print the area for the histogram [3, 1, 3, 2, 2].
6
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Stacks and Queues