Legends ofPythos
Claim your name
Working with Data

Stacks, queues and heaps

Lesson 13 of 14
Watch the lesson1:18 · with Torsten
You already know how to add items to the end of a list with append(). But what if you want to take them off in a specific order? Python gives you a few patterns for that: stacks, queues, priority queues, and sorted lists kept in order with bisect. Each one fits a different real-world problem.

Stacks: last-in, first-out

# An undo history is a stack.
# Push actions onto the top; pop them off in reverse order.
history = []
history.append('typed "hello"')   # push
history.append('deleted line 2') # push
last_action = history.pop()       # take most recent back -> 'deleted line 2'
print(last_action)
pop() removes and returns the last item added
append() adds to the end, pop() removes from the end. Together they make a stack. Think of a stack of plates: you put one on top, take one off the top. The most recent item is always first out.

Queues and why list.pop(0) is slow

# collections.deque (double-ended queue) fixes this.
from collections import deque
queue = deque()
queue.append('task A')   # add to the right
first = queue.popleft()  # remove from the left -> 'task A'
print(first)
deque keeps both ends fast
append() and popleft() on a deque take the same short time however long the queue gets. You can also cap the size with maxlen: older items drop off automatically.
# Keep only the newest 3 log lines.
from collections import deque
log = deque(maxlen=3)
for msg in ['boot', 'login', 'error', 'retry']:
    log.append(msg)
print(list(log))  # -> ['login', 'error', 'retry']
maxlen discards the oldest item when full

Priority queues with heapq

# A priority queue always hands back the most urgent task.
import heapq
heap = []
# (priority, label) — smaller number means more urgent
heapq.heappush(heap, (2, 'send email'))
heapq.heappush(heap, (1, 'fix crash'))   # highest priority
heapq.heappush(heap, (3, 'write report'))
top = heapq.heappop(heap)  # -> (1, 'fix crash')
print(top)
heappop always returns the smallest item
heapq turns a plain list into a min-heap. heappush adds an item, heappop removes and returns the smallest one. Because Python compares tuples left-to-right, storing (priority, task) gives you exactly what you want: lowest priority number first.
# Grab the 3 smallest without sorting the whole list yourself.
import heapq
scores = [85, 42, 91, 73, 60]
lowest_3 = heapq.nsmallest(3, scores)
print(lowest_3)  # -> [42, 60, 73]
nsmallest returns the k smallest items

Keeping a list sorted with bisect

# insort keeps a list in order as you add values.
import bisect
scores = []
bisect.insort(scores, 85)
bisect.insort(scores, 42)   # -> [42, 85]
bisect.insort(scores, 91)   # -> [42, 85, 91]
print(scores)
insort finds the right spot via binary search
bisect.bisect_right(sorted_list, value) tells you where a new item would fit. That makes it easy to map a raw number onto bands — like turning an exam score into a letter grade.
# Turn a numeric score into a band.
import bisect
breakpoints = [40, 60, 80, 90]   # F | D | C | B | A edges
def grade(score):
    idx = bisect.bisect_right(breakpoints, score)
    return 'FDCBA'[idx]
print(grade(72))  # -> 'C'
bisect gives you the index of the band

Your turn

0 of 3 solved

Exercise 1

+35 XP
An editor keeps an undo stack. Write apply(actions), where actions is a list of strings: 'type WORD' pushes WORD onto a list used as a stack, and 'undo' pops the most recent word off, or does nothing if the stack is empty. Return the words left on the stack, joined with spaces. For example, apply(['type hello', 'type there', 'undo', 'type world']) is 'hello world'.
def apply(actions):
    # A list as a stack: push on 'type', pop on 'undo'
    pass

Run your code to check it against the tests.

Exercise 2

+35 XP
Write serve(arrivals, n): arrivals lists customers in the order they joined a queue, and the first n of them are served. Put them in a collections.deque, take them from the front with popleft(), and return the list of names served, stopping early if the queue runs out. Then write recent(events), which returns a list of the last 3 events, using a deque with maxlen=3. For example, recent(['boot', 'login', 'save', 'logout']) is ['login', 'save', 'logout'].
from collections import deque




def serve(arrivals, n):
    # First in, first out with popleft()
    pass




def recent(events):
    # A deque that only ever holds 3 items
    pass

Run your code to check it against the tests.

Exercise 3

+35 XP
Write by_urgency(tasks), where each task is a (priority, name) tuple and a lower number is more urgent. Push them all onto a heap with heapq.heappush, pop them off with heapq.heappop, and return the names in the order they come off. Then write insert_sorted(board, score), which puts score into the already sorted list board with bisect.insort and returns board. For example, insert_sorted([10, 20, 30], 25) is [10, 20, 25, 30].
import bisect
import heapq




def by_urgency(tasks):
    # heappush every task, then heappop until the heap is empty
    pass




def insert_sorted(board, score):
    # Keep board sorted as the score goes in
    pass

Run your code to check it against the tests.