Lecture IV · Data Structures & Algorithms
Stacks, queues, and the idea of an ADT
Last time we learned to measure cost without hand-waving. Today we meet the first place that measurement earns its keep: two data structures that look almost identical on the page and behave nothing alike when you time them. To get there we need one idea that the rest of this course leans on constantly, so let us start with it.
An ADT is a contract, not a class
Here is a distinction worth slowing down for. When I say “stack,” I am not
naming a piece of code. I am naming a promise: there is a thing you can
push items onto and pop items off of, and whatever you pop is always the
most recent thing you pushed. Last in, first out. That promise says nothing
about how the items are stored. Lists, linked nodes, a fixed array with a
counter: all of them can keep the promise. The promise is the abstract data
type, the ADT. The code that keeps it is an implementation, and there can
be many.
So a stack is defined by its operations and their guarantees, not by its
insides. push, pop, peek, and “how many are there” are the operations.
“The last thing in is the first thing out” is the guarantee. A queue is another
such contract: enqueue at the back, dequeue from the front, and the
guarantee is first in, first out. Same shape of interface, opposite discipline.
This is exactly the frame from Lecture II, seen from the other side. There we
insisted on testing against the interface rather than the implementation. The
reason that advice is even possible is that the interface is a real, separate
thing: a contract we can write tests against before a single line of storage
code exists. We agree on what push and pop mean; the storage is a separate
promise we can swap out underneath without a single test changing. Hold onto
that. By the end of the hour we will swap the storage under a queue and watch
its speed change by a factor that grows without bound, while every test stays
green.
A stack in six lines
Let us keep the first promise. A Python list already does everything a stack
needs at the right end: append adds at the back, pop removes from the
back, and both are constant time (amortized, in the case of append, for
reasons we will meet when we build our own dynamic array). So a stack is
almost nothing but a list wearing the stack contract.
class Stack:
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item) # O(1) amortized
def pop(self):
return self._items.pop() # O(1): removes the last item
def peek(self):
return self._items[-1] # look, do not remove
def __len__(self):
return len(self._items)
Notice what the wrapper buys us. A raw list exposes forty methods, most of
which would let a caller violate the stack discipline: they could insert in the
middle, sort the thing, index into the seventh slot. The Stack class exposes
four, and every one of them keeps the promise. The abstraction is not there to
add power; it is there to remove it, deliberately, so that the only moves
available are the legal ones. That is most of what a good data structure does
for you.
Errors are part of the contract
Now the question everyone skates past. What does pop do on an empty stack?
There is no last item to return. This is not an edge case to be embarrassed
about and hide; it is a real question about the contract, and the contract has
to answer it. “You may not pop an empty stack, and if you try, I will raise
IndexError” is a perfectly good answer. So is “popping an empty stack returns
None.” What is not acceptable is silence: an answer you discover only by
accident, in production, three months later.
Our six-line Stack inherits Python’s answer by default, because list.pop()
on an empty list already raises IndexError. That is fine, but “inherits by
default” is not the same as “chose on purpose.” The grown-up move is to state
the behavior in the class and, per Lecture II, write the test that pins it
down, so the raise is a documented, guaranteed feature rather than an artifact
of what list happened to do.
Before we leave the stack, let us make its insides visible. The wrapper keeps a plain list, and the entire “last in, first out” promise comes down to always adding and removing at one end of that list. Which end?
The Dairy Bar line
Before we build a queue, go stand in one. On the first warm Saturday of the semester the line at the Dairy Bar runs out the door, down the steps, and along the path, forty deep for ice cream churned from the university’s own herd. That line is a queue ADT with people in it, and almost everything worth saying about queues is visible while you are standing in it, melting.
Start with the contract, because the line has one and nobody had to write it on the wall. You are served in the order you arrived. That is not merely a nice custom, it is a guarantee with a number attached: if k people are ahead of you when you join, you will be served after exactly k cones, and not one more. Notice what the guarantee does not depend on. It does not depend on how many people arrive behind you, or how popular the flavour is, or how long you end up waiting in minutes. First in, first out converts an unbounded worry into a bounded promise, and that bound is the reason FIFO is the shape of fairness.
Now break it, and watch how precisely it breaks. Suppose the server, wanting to save a step, turns around and serves whoever walked up most recently. Every operation still “works”: people join, people leave, cones get handed out, nothing crashes, and on a quiet Tuesday you would never notice. But the person at the front has just lost their bound entirely. As long as anyone keeps arriving, they are never served. That failure has a name, starvation, and it is not a performance problem. It is a contract violation. The operations kept their names and lost their meaning, which is exactly the failure an ADT exists to rule out. A server that pops the most recent arrival is a perfectly good stack. It is simply not the thing the line was promised.
This is where Lecture II’s insistence on testing the interface pays off in one line of code. A test that merely asserts “dequeue returned somebody who was in the queue” passes happily on the wrong-end server. A test that enqueues 1, 2, 3 and demands 1, 2, 3 back catches it before the ice cream melts. The FIFO assertion is not a nitpick about ordering; it is the only test that can tell a queue from a stack, because ordering is the entire difference between them.
When a list is the wrong backing store
A queue asks for the opposite ends: add at the back, remove from the front.
The back is easy, append again. The front is where the trouble lives.
The obvious thing is list.pop(0), and it works, in the sense that it returns
the right element. Watch:
class ListQueue:
def __init__(self):
self._items = []
def enqueue(self, item):
self._items.append(item) # O(1): add at the back
def dequeue(self):
return self._items.pop(0) # correct... and O(n)
def __len__(self):
return len(self._items)
Every test you could write against the Queue contract passes. FIFO order is
perfect. And yet this class hides a quiet disaster, because pop(0) is not
free. A Python list stores its elements in one contiguous block. Remove the
element at index 0 and every remaining element has to slide down one slot to
close the gap, so the front element that was at index 1 becomes index 0, and so
on. Removing the front of a list of length costs element moves. One
dequeue, shifts. Do it as the queue drains and the bill compounds.
Take that back to the Dairy Bar, because pop(0) has a physical meaning and it
is absurd. Imagine the line painted onto the path as numbered spots, with a rule
that the person being served must always be standing on spot 1. Hand out a cone
and everyone still waiting shuffles forward one spot to close the gap. It is
tidy. Everybody can see where the line is. And it means that serving one cone to
a line of people costs separate forward steps by other people. Serve a
Saturday line of a hundred from full to empty and the shuffling comes to
, which is 4,950 individual sidesteps to hand out a hundred
cones. Double the line to two hundred and the shuffling does not double, it
nearly quadruples, to 19,900. No manager on earth would run a line this way, and
yet ListQueue runs it this way on every single dequeue.
What a real line does instead is the whole lesson of this section: nobody
moves. The line stays exactly where it is standing and the server, or the sign
that says “order here”, advances one place. The contents did not change; only the
marker for the front did. One step per cone, steps over the whole line, no
matter how long the line is. “Move the marker, not the people” is the entire
difference between and here, and it is precisely what
collections.deque and the ring buffer do underneath.
Let us not argue about it. Let us watch it. The plate below runs the identical
sequence of operations, enqueue everything then dequeue everything, through two
backings of the same Queue contract: a list using pop(0), the painted spots;
and a collections.deque using popleft, the moving sign. Both fill the queue
at the same steady rate, because joining the back of a line is cheap either way.
The instant we start serving, the list’s meter tears away from the deque’s. Drag
upward and watch the gap widen, not by a constant, but by a factor that grows
with the length of the line.
| queue backing | order | steps |
|---|---|---|
| list · pop(0) | O(n²) | 90 |
| deque · popleft | O(n) | 24 |
Same interface, same 12 enqueues then 12 dequeues. The list pays 90 element steps to the deque's 24, because every pop(0) shifts the whole tail forward one slot. Read it as a Dairy Bar line of 12: serve the front and make everybody shuffle forward a spot, or leave everybody standing and move the sign.
Put a number on what you are seeing. Draining a queue that grew to items costs the list shifts, which is , squarely . The deque pays one step per dequeue, over the whole drain. At that is ninety steps against twenty-four; at , three hundred and twenty-four against forty-eight. The ratio is not fixed. It is the size of the queue, give or take a constant, so it climbs forever as your program handles more work. This is the shape of bug that never shows up in a small test and quietly melts a server under load. The contract was kept flawlessly. The cost promise, the one nobody wrote down, was broken.
It is worth naming exactly which promise that is. Both backings keep the FIFO guarantee perfectly, so both are honest queues and both give you the bounded wait we admired at the Dairy Bar: k people ahead of you, k cones, then yours. What the list-backed one loses is the cost of keeping that promise, which degrades with the length of the line. A queue can be fair and still be unusable, and neither property implies the other. That is why we quote both, the contract and the class, whenever we describe a data structure.
Two stacks make a queue
The fix that ships in the standard library is collections.deque, a
double-ended queue with genuine at both ends, and in real code you should
simply reach for it:
from collections import deque
class DequeQueue:
def __init__(self):
self._items = deque()
def enqueue(self, item):
self._items.append(item) # O(1)
def dequeue(self):
return self._items.popleft() # O(1), nothing shifts
def __len__(self):
return len(self._items)
But I do not want the deque to feel like a magic word. The more instructive
fix is to build a fast queue out of nothing but the slow structure we already
have, the plain list, used only at its cheap end. Keep two stacks, an
inbox and an outbox. Enqueue means push onto the inbox. Dequeue means
pop off the outbox, and if the outbox is empty, first pour the whole inbox into
it, popping and pushing one at a time. Pouring reverses the order, so the
oldest item, buried at the bottom of the inbox, ends up on top of the outbox,
exactly where a pop from the back can reach it.
Now, pouring is , so is this really any better? Here is the beautiful part,
and it is your first taste of amortized analysis, which Lecture III set up
and which we will meet again for dynamic arrays. Each item is poured across
exactly once in its whole life: pushed to the inbox once, moved to the outbox
at most once, popped off the outbox once. Three cheap operations per item, no
matter how the enqueues and dequeues interleave. Spread the occasional
expensive pour across all the cheap pops it pays for, and the average cost
per dequeue is a constant. That is what “amortized ” means: not that every
call is cheap, but that any run of calls is cheap on average, because the rare
expensive one is bounded by all the cheap ones it enables. Same list, same
pop, one idea about which end, and the quadratic is gone.
The Dairy Bar gives the pour a body, and it is worth carrying the picture around, because the reversal is the part everyone gets backwards. On a cold day the line does not stand outside; people crowd into the vestibule, and the last one through the outer door is the one standing nearest it. When the serving hall empties out, the vestibule is let through all at once, and they file in through the inner door in the order they can reach it, nearest first. That reverses them, which is exactly the point: the person who has been waiting longest, buried at the back of the vestibule, comes through last and so ends up at the front of the hall, first in line for the next cone. Now count the doors. Every single person passes through the outer door once and the inner door once, no matter how many times the hall happens to empty. Two door-crossings each, over an entire afternoon of arrivals and departures. That is the amortized argument stated in people rather than in list operations, and it is the same argument: the occasional expensive flood is paid for in advance by everyone it moves.
The words “pour” and “reverse” are easy to nod along to and easy to get backwards, so let us open the two lists and watch them move.
A stack that matches your brackets
The stack can look too plain to deserve its own class. Here is the application
that changed my mind. Type a stray ) into any code editor and it flags the
error before your finger leaves the key. How does it know? Every bracket you
have ever written, (), [], {}, has to be closed, and closed in the right
order: the bracket you opened most recently is the one that must close next.
“Most recent first” is the stack’s entire personality, so bracket matching is
not merely solvable with a stack, it is the stack’s native problem.
The rule fits in three sentences. Walk the string left to right. When you meet an opener, push it; when you meet a closer, the opener on top of the stack must be its partner, and if the stack is empty or the top is the wrong kind, the string is broken. At the end the stack must be empty, because anything still sitting there is an opener that was never closed.
Trace ([)], the case that defeats every approach that just counts brackets.
The tally is even: two openers, two closers. And yet it is wrong, because the
) arrives while [ is still the innermost open bracket, so something is being
closed out of turn. A counter cannot see this; it only knows totals. The stack
sees it at once, because when ) arrives the top of the stack is [, not (,
and that single mismatch is the whole answer. Order is what matters here, and
the stack is the structure whose only job is to remember order.
The checks · run against your code
# the empty string has no brackets to close, so it is balanced
assert is_balanced("") is True
# simple and nested matches hold
assert is_balanced("()") is True
assert is_balanced("([]{})") is True
assert is_balanced("(a[b]{c})") is True # non-bracket chars ignored
# an unclosed opener is left waiting on the stack
assert is_balanced("(") is False
assert is_balanced("([]") is False
# a closer with nothing open sits above an empty stack
assert is_balanced(")") is False
# right count, wrong order: the bug a stack catches and a tally cannot
assert is_balanced("(]") is False
assert is_balanced("([)]") is False
Hint one
Two kinds of character do work; a third does nothing. If ch is
in openers, push it. If ch is a key of
match, it is a closer. Anything else is a letter or a space:
ignore it and move on.
Hint two
For a closer, two things can go wrong at once. There may be no opener at all
(not stack), or the opener on top may be the wrong one
(stack.pop() != match[ch]). Either failure means
return False immediately.
The solution
Push openers, check closers against the top, and let the final
return not stack handle the leftover-opener case for free: an
empty stack is balanced, a non-empty one is not.
for ch in s:
if ch in openers:
stack.append(ch)
elif ch in match:
if not stack or stack.pop() != match[ch]:
return False
return not stackEvery character is looked at once and touches the stack at most twice
(one push, one pop), so is_balanced is in the length of
the string. The stack never holds more than the current nesting depth.
The same push-and-pop shape does more than validate. Hand a stack the tokens of
an arithmetic expression in postfix, or reverse Polish, notation, 3 4 + 5 *,
and it evaluates them with no parentheses and no precedence rules at all: push
each number, and on each operator pop the top two, combine, push the result.
When the tokens run out the answer is the single value left on the stack. That
is not a toy; it is close to how a real interpreter runs the expressions in
your code, and you will build exactly this in the problems.
A queue is how work waits its turn
If the stack’s discipline is “most recent first,” the queue’s is its opposite, and the opposite turns out to be the shape of fairness. A print queue hands jobs to the printer in the order they were submitted, so the report you sent at nine does not sit forever behind a colleague’s thousand-page manual sent at nine-oh-one. That is the Dairy Bar’s bounded promise again, wearing a different hat: k jobs ahead of you, k jobs printed, then yours, whatever arrives behind you. A web server drains incoming requests first in, first out so the oldest waiting user is served next rather than starved. An operating system parcels out the processor to ready tasks in turn. Whenever “waited longest, served next” is the rule you want, FIFO is not one option among many, it is the definition of the thing, and a queue is how you spell it.
There is a deeper reason to care, and it points forward to Lecture XIII. The
most important algorithm on graphs, breadth-first search, is a queue with a
graph attached. To explore outward from a starting point in rings of equal
distance, you enqueue a node’s unvisited neighbors and dequeue the next node to
visit, over and over. Because the queue is FIFO, everything one step away is
handled before anything two steps away, which is exactly why breadth-first
search finds shortest paths in an unweighted graph. The reason we are so fussy
today about a queue whose dequeue is genuinely is that later we will call
it once per edge, on graphs far too large to forgive a hidden pop(0). The
quiet quadratic we raced against in Plate III is precisely the bug that would
turn a fast graph search into an unusable one.
The deque, and the ring that bounds it
Step back and notice we have now wanted three different disciplines: a stack
(one end), a queue (two ends, opposite roles), and, when we built the two-stack
queue, a structure we pushed and popped from both ends freely. There is one
tool that is all of these at once, the deque, or double-ended queue, with
append and pop at the right end and appendleft and popleft at
the left. Want a stack? Use one end. Want a queue? Enqueue at one end, dequeue
at the other. Want both? You already have them. This is why collections.deque
is the honest default in Python: it is the general tool, and a stack or a queue
is just a deque with half its doors politely left shut. The two-stack queue was
worth building to prove we could reach amortized from plain lists, but in
real code you reach for the deque and move on.
The deque grows without bound, which is usually what you want and occasionally exactly what you do not. When the number of items in flight has a known ceiling, a fixed-size ring queue, or circular buffer, is the leaner tool: one array of fixed length, an index for the head, and a running count. Enqueue writes just past the last item and wraps around to the front of the array with modular arithmetic; dequeue reads the head and advances it, also wrapping. Nothing ever shifts, both ends are truly with no amortization to argue about, and no memory is ever allocated after the first array.
class RingQueue:
"""A FIFO queue in a fixed array. Both ends are O(1) with no
shifting, but it holds at most `capacity` items: bounded on purpose."""
def __init__(self, capacity):
self._buf = [None] * capacity
self._head = 0 # index of the oldest item
self._size = 0
def enqueue(self, item):
if self._size == len(self._buf):
raise IndexError("enqueue on a full ring")
tail = (self._head + self._size) % len(self._buf)
self._buf[tail] = item
self._size += 1
def dequeue(self):
if self._size == 0:
raise IndexError("dequeue on an empty ring")
item = self._buf[self._head]
self._buf[self._head] = None
self._head = (self._head + 1) % len(self._buf)
self._size -= 1
return item
The tradeoff is written into the first line of enqueue: the ring is full at
capacity and refuses the next item. That looks like a limitation next to the
deque’s endless growth, and sometimes it is. But often the bound is the point. A
fixed audio buffer, a “last 100 log lines” window, a sensor feed you sample at a
steady rate: in all of these a hard ceiling on memory is a feature you want
guaranteed, not a compromise you tolerate. The deque asks “how do I never run
out of room”; the ring asks “how do I promise never to use more than this.” Two
honest answers to two different questions, and knowing which question you are
actually asking is most of the skill.
The ring is also the Dairy Bar’s own answer, if you look at the door. The room
holds however many people the fire code allows, and past that the next arrival
waits outside: a hard ceiling, enforced at the moment of entry, exactly like the
IndexError on a full enqueue. And the modular arithmetic is the part you have
already watched work. Nobody in a real line renumbers the floor when the front
person leaves. The head advances, wraps around the room when it reaches the far
wall, and the spot just vacated is reused by the next arrival. That is the same
“move the marker, not the people” trick as the deque, with the added promise that
the room can never grow.
A stack that remembers its minimum
Here is a small demand that turns out to teach the ADT lesson twice over. Suppose you want a stack that can also tell you, at any moment, the smallest item currently sitting in it. The lazy answer is to scan the whole list every time someone asks, but that is per question, and if the minimum is asked as often as items are pushed, you have quietly turned a stack into something slow. Can we answer in , the way a good stack answers everything else?
We can, with the very move that built the fast queue: keep a second stack
alongside the first. Every time you push an item, also push the smaller of that
item and the current minimum onto a parallel _mins stack. Then the two stacks
rise and fall together, and the current minimum is always the top of _mins,
one peek away. Popping is symmetric: pop both, so they stay the same height. The
cost is one extra list the same length as the first, and in return every
operation, push, pop, peek, and minimum, stays . That trade, a
little more memory for a lot less time, is one you will make again and again in
this course.
The one case worth thinking through is a repeated minimum. Push 3, then 1, then
1 again: the _mins stack holds 3, 1, 1, so when you pop the top 1 the minimum
is still 1, correctly, because a second 1 is still down in the stack. Storing
the running minimum at every level, rather than a single reigning champion, is
exactly what makes the rollback on pop come out right.
The checks · run against your code
# minimum reports the smallest item currently on the stack
m = MinStack()
m.push(5)
assert m.minimum() == 5
m.push(2)
assert m.minimum() == 2
m.push(7)
assert m.minimum() == 2 # 7 did not lower the floor
# pop returns the ITEM, and the minimum rolls back in step with it
assert m.pop() == 7
assert m.minimum() == 2
assert m.pop() == 2
assert m.minimum() == 5 # popping the 2 restores 5 as the floor
# a repeated minimum survives until its last copy is gone
m = MinStack()
for x in [3, 1, 1, 4]:
m.push(x)
assert m.minimum() == 1
assert m.pop() == 4
assert m.minimum() == 1
assert m.pop() == 1
assert m.minimum() == 1 # a second 1 still holds the floor
assert len(m) == 2 # len counts items, not minimums
# an empty pop raises IndexError, exactly like a plain stack
m = MinStack()
try:
m.pop()
raised = False
except IndexError:
raised = True
assert raised
Hint one
push does two appends. The first is the item onto
_items. The second is the new running minimum onto
_mins: if _mins is empty it is the item itself,
otherwise it is min(item, self._mins[-1]).
Hint two
pop has to keep the two stacks the same height, so pop both. Pop
_mins and throw it away; pop _items and return
that. minimum never pops at all: it just returns
self._mins[-1].
The solution
Both stacks move in lockstep, so _mins[-1] is always the
minimum of exactly the items currently present, and an empty
pop raises IndexError off the empty list for
free, just like the plain stack.
def push(self, item):
self._items.append(item)
if self._mins:
self._mins.append(min(item, self._mins[-1]))
else:
self._mins.append(item)
def pop(self):
self._mins.pop()
return self._items.pop()
def minimum(self):
return self._mins[-1]Every operation is a constant number of list touches, so all four are . The price is a second list the same length as the first: the familiar trade of space for time.
Exercises
Write the FIFO test suite for the Queue contract before looking at any implementation: enqueue three items, dequeue them, and assert they come out in the order they went in; then check that
lendrops as you dequeue. Convince yourself the same suite would pass againstListQueue,DequeQueue, and the two-stack queue below. That is the ADT idea made concrete.A stack reverses. Using only your
Stack, writereverse(seq)that returns a new list with the elements ofseqin reverse order. Explain in one sentence why the LIFO guarantee is the only property you used.Give
Stacka companionpeekthat raises a clearIndexErroron an empty stack, and argue whypeekandpopshould agree about the empty case rather than each inventing its own answer. This is the contract talking.Bounded on purpose. Explain in two or three sentences why the
RingQueueraises on a fullenqueuewhile the deque never does, and name one setting where that ceiling is a feature you want guaranteed rather than a limitation you regret. Then say what the ring’s_headand_sizewould be after you enqueue four items into acapacityof three and dequeue one, or explain why you cannot get that far.Evaluate an expression with a stack. Write
evaluate_rpn(tokens)wheretokensis a list like["3", "4", "+", "5", "*"]in reverse Polish notation: push each number, and on each of+,-,*pop the top two operands, combine them, and push the result. The answer is the single value left on the stack. Mind the order of the two operands for subtraction, and say what should happen if the stack does not hold exactly one value at the end.def evaluate_rpn(tokens): stack = [] for tok in tokens: if tok in ("+", "-", "*"): b = stack.pop() # second operand popped first a = stack.pop() if tok == "+": stack.append(a + b) elif tok == "-": stack.append(a - b) else: stack.append(a * b) else: stack.append(int(tok)) if len(stack) != 1: raise ValueError("malformed expression") return stack.pop()The main event. Finish
dequeueso the two-stackQueueis amortized and raisesIndexErroron an empty queue, using onlyappend()andpop()on the two lists, neverpop(0). The checks below test FIFO order across an interleaved run, thatlentracks the count, and that an empty dequeue raises.The checks · run against your code
# FIFO order survives interleaved enqueue and dequeue q = Queue() for x in [1, 2, 3]: q.enqueue(x) assert q.dequeue() == 1 assert q.dequeue() == 2 q.enqueue(4) assert q.dequeue() == 3 assert q.dequeue() == 4 # len counts everything still waiting q = Queue() q.enqueue(10) q.enqueue(20) assert len(q) == 2 q.dequeue() assert len(q) == 1 # dequeue on an empty queue raises IndexError q = Queue() try: q.dequeue() raised = False except IndexError: raised = True assert raisedpython runs in your browser · first run downloads ~240 kbPlate VII Implement the two-stack queue. Fill in dequeue so the checks go green: FIFO order, a correct length, and IndexError on empty. Press Run. Hint one
The outbox is your fast front. Only refill it when it is empty, so most dequeues are a single
pop()off its end.Hint two
To refill: while the inbox is non-empty,
appendonto the outbox whatever youpopoff the inbox. That single reversal turns the oldest item into the outbox’s top.The solution
Refill on demand, then pop. When both lists are empty the final
pop()raisesIndexErroron its own, which is exactly the contract we wanted, so there is nothing extra to write for the empty case.def dequeue(self): if not self._outbox: while self._inbox: self._outbox.append(self._inbox.pop()) return self._outbox.pop()Each item is appended to the inbox once, moved once, and popped once: three constant-time touches over its whole life, so the average cost per dequeue is however the calls interleave.
A second promise, for free. Your
MinStackanswersminimum()in by carrying a parallel stack of running minimums. In one or two sentences, say why storing the running minimum at every level, rather than one reigning champion value, is what keepspopcorrect, and describe exactly what would go wrong on the sequence push 3, push 1, push 1, pop if you had kept only a single champion.Back and Forward, two stacks again. A browser’s history is two stacks: one of pages you can return to, one of pages you skipped past by pressing Back, with the twist that visiting a new page clears the forward trail. Finish
backandforwardso the checks go green: an empty trail makes each button a no-op that returns the current page, Back and Forward are mirror images, and a freshvisitafter going back drops the redo trail for good.The checks · run against your code
# a fresh history sits on home with nowhere to go h = History("home") assert h.current() == "home" assert h.back() == "home" # Back on an empty trail is a no-op assert h.forward() == "home" # so is Forward # visiting moves us on and remembers where we were h.visit("a") h.visit("b") assert h.current() == "b" assert h.back() == "a" # step back to a assert h.back() == "home" # and back again to home assert h.current() == "home" # Forward retraces the steps we took back assert h.forward() == "a" assert h.current() == "a" # visiting after a Back forks a new branch and drops the redo trail h.visit("c") assert h.current() == "c" assert h.forward() == "c" # nothing to redo: b is gone for good assert h.back() == "a" # but Back still workspython runs in your browser · first run downloads ~240 kbPlate VIII Implement Back and Forward with two stacks. Each button moves the current page onto the opposite stack and pops its own; an empty stack makes the button a no-op. Fill in back and forward so the checks go green. Press Run. Hint one
backandforwardare the same shape with the two stacks swapped. Guard first: if the stack you would pop from is empty, there is nowhere to go, so returnself._currentunchanged.Hint two
Otherwise it is three moves: append the current page onto the OTHER stack, pop your own stack into
self._current, and return the new current page.visitalready clears_forwardfor you, so you never touch that trail here.The solution
Each button is a guarded swap between the two stacks with the current page as the pivot, so both run in and the two are exact mirror images of each other.
def back(self): if not self._back: return self._current self._forward.append(self._current) self._current = self._back.pop() return self._current def forward(self): if not self._forward: return self._current self._back.append(self._current) self._current = self._forward.pop() return self._currentThe wrong end, on purpose. A tired server at the Dairy Bar starts handing cones to whoever walked up most recently. Every method still runs and nobody sees an exception. Say precisely which promise has been broken, name what happens to the person standing at the front while arrivals keep coming, and give the shortest test you can write that fails on this server and passes on an honest queue. Then answer the harder half: the wrong-end server is a perfectly correct implementation of some ADT. Which one, and what does that tell you about the relationship between an interface and a guarantee?
Count the shuffling. Under the painted-spots rule the person being served stands on spot 1, so each cone makes the rest of the line step forward once each; under the moving-sign rule nobody in line moves and the sign advances instead. Implement
shuffle_steps(n)andsign_steps(n)for serving a line of n from full to empty, plusworst_wait(ahead), the FIFO promise stated as a number. Then read the printed table: when n doubles, one column doubles and the other nearly quadruples, and you can name both classes from that ratio alone without touching a stopwatch.The checks · run against your code
# One person in line: nobody behind them to shuffle. assert shuffle_steps(1) == 0 # Two people: serving the front makes exactly one person step forward. assert shuffle_steps(2) == 1 # A line of four costs 3 + 2 + 1 + 0 forward steps. assert shuffle_steps(4) == 6 # A Saturday hundred costs 4,950 sidesteps to hand out 100 cones. assert shuffle_steps(100) == 4950 # The sign moves once per cone, however long the line is. assert sign_steps(1) == 1 assert sign_steps(100) == 100 # Double the line and the sign policy exactly doubles: that is linear. assert sign_steps(200) == 2 * sign_steps(100) # Double the line and the shuffling nearly quadruples: that is quadratic. assert shuffle_steps(200) > 3.9 * shuffle_steps(100) # The FIFO bound counts the people already ahead of you, and nobody else. assert worst_wait(0) == 0 assert worst_wait(7) == 7
python runs in your browser · first run downloads ~240 kbPlate IX THE DAIRY BAR BILL · Implement shuffle_steps(n), sign_steps(n), and worst_wait(ahead). Run to grade against eight checks. Serving a hundred cones costs 4,950 forward steps under painted spots and 100 sign moves under the moving sign: the same against you raced in Plate III. Hint one
Serving the front of a line of L people makes people step forward. As the line drains, L runs n, then , and so on down to 1, so the total is . You have met that sum before; it has a closed form.
Hint two
sign_stepsis the easy one: one move per cone, so it is just n. Andworst_waitis easier still. The whole content of the FIFO guarantee is that people arriving after you cannot get in front of you, so the answer is the number who were already there.The solution
Three one-liners, and the middle one is the point of the whole lecture:
def shuffle_steps(n): return n * (n - 1) // 2 def sign_steps(n): return n def worst_wait(ahead): return aheadThe first is and the second , which is the whole gap between
ListQueueandDequeQueuewritten out in sidesteps. The third is the quiet one:worst_waitignores its surroundings entirely, and that indifference to what arrives later is exactly the promise FIFO makes and LIFO cannot.
Two machines, one lesson about which end
The race in Plate III fixed one script and one contract, a queue filled then
drained. But the deeper claim of this lecture is about ends, and it is easier
to feel with the machines in your own hands. So here are two, free to drive: a
stack, whose every operation lives at the top, and a deque, whose whole reason
for existing is that both ends are open. Each machine carries two cost meters,
one for a Python list backing and one for a collections.deque backing, counting
the element steps the same sequence of your clicks charges to each.
Push and pop the stack a few times and the two meters move in lockstep: on the
right end, list.append and list.pop are already , so a deque buys you
nothing and a plain list is the honest choice. Now drive the deque, and reach for
the two tinted operations, appendleft and popleft. Those are
list.insert(0, x) and list.pop(0), and each one makes the list shift every
other cell one slot to keep its block contiguous: watch the shifted cells light
up and the list meter tear away from the deque’s, while the running tally counts
the shifts piling up. The lesson is the whole of “which end”: a stack is happy on
a list, and a deque needs a deque.
Stack · a list is enough
index 0 · bottomtop · push / pop
Deque · both ends in play
index 0 · appendleft / popleftback · append / pop
A stack only ever touches the top, the right end, where a Python list is already O(1): push is list.append, pop is list.pop, and a deque is no faster. A deque touches both ends, and the left end is where a list hurts. On this deque of 6, a popleft is list.pop(0): it removes index 0 and slides the other 5 cells down one slot, O(n). A collections.deque does it in O(1) with nothing shifted. Enable JavaScript to drive both machines and watch the list and deque cost meters agree on the stack and split on the deque.