Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture IV of XIV

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.

python runs in your browser · first run downloads ~240 kb
Plate I A stack you can drive. Run it as given to see the empty pop raise, then edit pop() to raise on purpose with a message of your own. Press Run.

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?

python runs in your browser · first run downloads ~240 kb
Plate II The list under the stack, drawn. push() and pop() both work the RIGHT end of the list, so the top of the stack is the last cell. Run it to see three pushes and one pop, then Trace it line by line.

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 LL costs LL element moves. One dequeue, LL 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 LL people costs L−1L-1 separate forward steps by other people. Serve a Saturday line of a hundred from full to empty and the shuffling comes to 99+98+⋯+099 + 98 + \cdots + 0, 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, nn steps over the whole line, no matter how long the line is. “Move the marker, not the people” is the entire difference between O(n2)O(n^2) and O(n)O(n) 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 nn upward and watch the gap widen, not by a constant, but by a factor that grows with the length of the line.

Element-step totals for running the same 12 enqueues then 12 dequeues through two backings of one Queue: a Python list using pop(0) versus a collections.deque.
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.

Plate III One Queue interface, two backings, raced by cost, read as the Dairy Bar line. Joining the back is cheap for both; then every list pop(0) makes the whole rest of the line shuffle forward a spot while the deque just moves the sign. Press Play, Step through one person at a time, and drag nn to watch the O(n2)O(n^2) painted-spot policy pull away from the O(n)O(n) one.

Put a number on what you are seeing. Draining a queue that grew to nn items costs the list n+(n−1)+⋯+1n + (n-1) + \cdots + 1 shifts, which is n(n+1)/2n(n+1)/2, squarely O(n2)O(n^2). The deque pays one step per dequeue, O(n)O(n) over the whole drain. At n=12n = 12 that is ninety steps against twenty-four; at n=24n = 24, 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 O(1)O(1) 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 O(n)O(n), 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 O(1)O(1)” 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.

python runs in your browser · first run downloads ~240 kb
Plate IV The two-stack queue with its lid off. Enqueues pile into the inbox; the first dequeue pours the inbox into the outbox, reversing it, so the oldest item lands on top. Run it, then Trace it to watch the pour cell by cell.

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
python runs in your browser · first run downloads ~240 kb
Plate V Balanced brackets with a stack. Push every opener; a closer must match the top or the string is broken; the stack must be empty at the end. Fill in the loop so the checks go green, including the count-even but order-wrong case ([)]. Press Run.
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 stack

Every character is looked at once and touches the stack at most twice (one push, one pop), so is_balanced is O(n)O(n) 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 O(1)O(1) 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 O(1)O(1) append and pop at the right end and O(1)O(1) 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 O(1)O(1) 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 O(1)O(1) 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 O(n)O(n) 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 O(1)O(1), 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 O(1)O(1). 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
python runs in your browser · first run downloads ~240 kb
Plate VI Implement a MinStack whose minimum() is O(1). Keep a parallel stack of running minimums that rises and falls with the main one. Fill in push, pop, and minimum so the checks go green, including the repeated-minimum case. Press Run.
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 O(1)O(1). The price is a second list the same length as the first: the familiar trade of space for time.

Exercises

  1. 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 len drops as you dequeue. Convince yourself the same suite would pass against ListQueue, DequeQueue, and the two-stack queue below. That is the ADT idea made concrete.

  2. A stack reverses. Using only your Stack, write reverse(seq) that returns a new list with the elements of seq in reverse order. Explain in one sentence why the LIFO guarantee is the only property you used.

  3. Give Stack a companion peek that raises a clear IndexError on an empty stack, and argue why peek and pop should agree about the empty case rather than each inventing its own answer. This is the contract talking.

  4. Bounded on purpose. Explain in two or three sentences why the RingQueue raises on a full enqueue while 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 _head and _size would be after you enqueue four items into a capacity of three and dequeue one, or explain why you cannot get that far.

  5. Evaluate an expression with a stack. Write evaluate_rpn(tokens) where tokens is 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()
  6. The main event. Finish dequeue so the two-stack Queue is amortized O(1)O(1) and raises IndexError on an empty queue, using only append() and pop() on the two lists, never pop(0). The checks below test FIFO order across an interleaved run, that len tracks 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 raised
    python runs in your browser · first run downloads ~240 kb
    Plate 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, append onto the outbox whatever you pop off 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() raises IndexError on 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 O(1)O(1) however the calls interleave.

  7. A second promise, for free. Your MinStack answers minimum() in O(1)O(1) 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 keeps pop correct, 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.

  8. 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 back and forward so 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 fresh visit after 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 works
    python runs in your browser · first run downloads ~240 kb
    Plate 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

    back and forward are 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 return self._current unchanged.

    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. visit already clears _forward for 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 O(1)O(1) 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._current
  9. The 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?

  10. 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) and sign_steps(n) for serving a line of n from full to empty, plus worst_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 kb
    Plate 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 O(n2)O(n^2) against O(n)O(n) you raced in Plate III.
    Hint one

    Serving the front of a line of L people makes L−1L-1 people step forward. As the line drains, L runs n, then n−1n-1, and so on down to 1, so the total is (n−1)+(n−2)+⋯+0(n-1) + (n-2) + \cdots + 0. You have met that sum before; it has a closed form.

    Hint two

    sign_steps is the easy one: one move per cone, so it is just n. And worst_wait is 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 ahead

    The first is Θ(n2)\Theta(n^2) and the second Θ(n)\Theta(n), which is the whole gap between ListQueue and DequeQueue written out in sidesteps. The third is the quiet one: worst_wait ignores 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 O(1)O(1), 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

1
2
3
4

index 0 · bottomtop · push / pop

Deque · both ends in play

1
2
3
4
5
6

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.

Plate X Two operable ADT machines with cost meters. Click an operation and watch the contents update and a list backing and a deque backing tick side by side. On the stack both meters climb together; on the deque, every left-end appendleft or popleft is a list.insert(0,x) or list.pop(0) that shifts the whole row, so the list meter races the deque's. Push, pop, appendleft, popleft, and read which end costs what.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.