Stacks

1.1The problem: undo

You type “Hello”, then “ world”, then “!!”. Pressing Ctrl+Z should remove “!!” first, then “ world”, then “Hello”. Undo always reverses the most recent change that has not yet been undone. Whatever stores the history must hand back the last thing it was given, then the one before that, and so on.

A pile of plates works the same way. You add a plate to the top and you take a plate from the top. The plate you put down last is the first one you pick up. The plate at the bottom waits until every plate above it is gone.

1.2The Stack ADT

A stack stores arbitrary objects. Insertions and removals both happen at one end, called the top, so they follow a last-in, first-out (LIFO) order.

push and pop are the main operations; the other three are auxiliary: convenient, but you could fake top() with a pop followed by a push.

Here is the lecture's example trace. Read the right-hand column as “bottom … top”.

1.3Where stacks appear

• Undo (Ctrl+Z). Each edit pushes the old state; undo pops it.
• The browser's Back button. Each page you leave is pushed; Back pops the most recent one.
• Function calls. When f calls g and g calls h, the program must finish h first, then return into g, then into f. The runtime keeps a call stack: each call pushes a record of where to return to and its local variables; each return pops one. Infinite recursion fails with “stack overflow” because the call stack runs out of room.

The undo example in code, using the stack class written in Part 2:

text, history = "", ArrayStack()

def type_text(s):
    global text
    history.push(text)                   # save the state BEFORE the change
    text += s

def undo():
    global text
    if not history.is_empty():
        text = history.pop()             # most recent change is undone first

type_text("Hello"); type_text(" world"); type_text("!!")
print(repr(text))
undo(); print(repr(text))
undo(); print(repr(text))

'Hello world!!'
'Hello world'
'Hello'

Note that each step pushes the old text before changing it. Undo is then just “restore whatever was pushed most recently”.

2.1Array-based stack: the Adapter pattern

Python already has a list that can grow at its end. We do not want users to call arbitrary list methods (inserting into the middle would break the LIFO promise), so we write a new class that keeps a list as a hidden field and exposes only the five stack operations. Building a new interface around an existing class like this is called the Adapter design pattern.

The one design decision is: which end of the list is the top? The answer is the end (highest index), because append and pop() work there without moving anything. If the top were index 0, every push and pop would shift all the other elements by one place: O(n) each.

These are the answers to the in-class polls: space O(n); top O(1); is_empty O(1); push and pop O(1) amortized.

class Empty(Exception):
    """Raised when you read from an empty stack."""
    pass

class ArrayStack:
    """LIFO stack that hides a Python list (the Adapter pattern)."""

    def __init__(self):
        self._data = []                  # the hidden list; the top is its END

    def __len__(self):
        return len(self._data)           # O(1): lists store their length

    def is_empty(self):
        return len(self._data) == 0      # O(1)

    def push(self, e):
        self._data.append(e)             # O(1) amortized

    def top(self):
        if self.is_empty():
            raise Empty("stack is empty")
        return self._data[-1]            # O(1): index access

    def pop(self):
        if self.is_empty():
            raise Empty("stack is empty")
        return self._data.pop()          # O(1) amortized: removes from the end

S = ArrayStack()
S.push(5)
S.push(3)
print(len(S), S.pop(), S.is_empty(), S.pop(), S.is_empty())
try:
    S.pop()
except Empty as err:
    print("Empty:", err)

2 3 False 5 True
Empty: stack is empty

Two details worth copying. First, popping an empty stack raises our own Empty exception, with a clear message, instead of letting Python's IndexError leak out with a message about lists that the user never asked for. Second, the leading underscore in _data is the Python convention for “internal; do not touch from outside”.

2.2What a Python list really is

A Python list is a dynamic referential array:

• Array: one block of consecutive memory slots. To find slot i, the computer does one calculation: start address + i × slot size. That is why L[i] is O(1).
• Referential: each slot holds a reference (an address, 8 bytes on a 64-bit machine) to an object stored elsewhere, not the object itself. That is how one list can hold numbers, strings and other lists side by side.
• Dynamic: the block has a fixed capacity, usually more than the number of elements actually stored. When an append finds the block full, Python allocates a bigger block, copies every reference across, and frees the old block.

2.3Why push is still O(1) amortized

Count primitive operations: writing one reference into a slot costs 1. An ordinary append costs 1. An append that triggers a resize from capacity k costs k (copying) + 1 (the new element).

Suppose the array starts with capacity 1 and doubles whenever it is full. Over n appends, resizes happen when the size reaches 1, 2, 4, 8, …, up to the largest power of 2 below n. The total copying is

Add the n ordinary writes and the total is less than 3n. So n appends cost O(n) in total, which is O(1) per append on average. That average is the amortized cost.

The same argument works for any growth factor f > 1 (new capacity = old capacity × f). The resizes happen at sizes f, f², …, f^k with k = log_f n, and the geometric series sums to

because f^k ≤ n and ff − 1 is a constant (2 for doubling, 3 for f = 1.5).

import sys

L = []
print("len  bytes  slots")
last = sys.getsizeof(L)
for k in range(1, 41):
    L.append(None)
    size = sys.getsizeof(L)
    if size != last:                     # the list just moved to a bigger array
        slots = (size - sys.getsizeof([])) // 8   # 8 bytes per reference
        print(f"{k:3}  {size:5}  {slots:5}")
        last = size

len  bytes  slots
  1     88      4
  5    120      8
  9    184     16
 17    248     24
 25    312     32
 33    376     40

2.4Why pop is also “amortized”

Removing the last element is a single step. The lecture still says O(1) amortized for pop because a well-behaved dynamic array also shrinks when it becomes mostly empty, so that a stack that once held a million items and now holds ten does not keep a million slots forever. Shrinking copies, just like growing, and the same averaging argument applies. (The queue page shows the standard rule: halve when the array drops below a quarter full.)

2.5Linked-list stack: no resizing at all

The other standard implementation stores each element in its own small node, and each node holds a reference to the node below it. The stack only remembers the top node (the head). The full story of linked lists is on the Linked Lists page; here is all a stack needs.

Where should the top go: the head or the tail of the list? The head, because both inserting and removing at the head are O(1). Removing at the tail of a singly linked list is O(n), because you would have to walk from the head to find the node before the tail.

class LinkedStack:
    """LIFO stack on a singly linked list; the top is the HEAD."""

    class _Node:
        __slots__ = "_element", "_next"
        def __init__(self, element, nxt):
            self._element, self._next = element, nxt

    def __init__(self):
        self._head = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def push(self, e):
        self._head = self._Node(e, self._head)   # new node points at old head
        self._size += 1

    def top(self):
        if self.is_empty():
            raise IndexError("stack is empty")
        return self._head._element

    def pop(self):
        if self.is_empty():
            raise IndexError("stack is empty")
        answer = self._head._element
        self._head = self._head._next            # unlink the old head
        self._size -= 1
        return answer

S = LinkedStack()
for x in [7, 9, 4]:
    S.push(x)
print(S.pop(), S.top(), len(S))

4 9 2

3.1The task

Given an expression, check that every opening symbol has a closing partner of the same type, and that pairs nest properly (they may contain each other but must not cross). The pairs are parentheses ( ), braces { } and brackets [ ]. Other characters (numbers, variables, operators) are ignored.

3.2Why a stack is the right tool

When you read a closer, which opener must it match? Not the first one, and not any one: it must match the most recent opener that has not been closed yet. In { ( [ ] ) }, the ] closes [ (the latest), then ) closes (, then } closes {. “Most recent unfinished thing” is precisely what the top of a stack holds.

3.3The algorithm

Algorithm ParenMatch(X, n):
    S = empty stack
    for i = 0 to n - 1:
        if X[i] is an opening symbol:
            S.push(X[i])
        else if X[i] is a closing symbol:
            if S.is_empty():
                return false        # nothing to match with
            if S.pop() does not match the type of X[i]:
                return false        # wrong type
    if S.is_empty():
        return true                 # every symbol matched
    else:
        return false                # some opener was never closed

There are exactly three ways to fail, and each line catches one: a closer with an empty stack (too many closers), a closer whose partner is wrong (crossing or mismatched types), and a non-empty stack at the end (too many openers).

def is_matched(expr):
    """Return True if every ( { [ in expr is closed by its partner, in order."""
    lefty, righty = "({[", ")}]"
    S = ArrayStack()
    for c in expr:
        if c in lefty:
            S.push(c)                            # remember the opener
        elif c in righty:
            if S.is_empty():
                return False                     # a closer with nothing to close
            if righty.index(c) != lefty.index(S.pop()):
                return False                     # wrong type of closer
    return S.is_empty()                          # anything left was never closed

for t in ["()(()){([()])}", "((()(()){([()])}))", ")(()){([()])}", "({[])}", "("]:
    print(f"{t:20} {is_matched(t)}")

()(()){([()])}       True
((()(()){([()])}))   True
)(()){([()])}        False
({[])}               False
(                    False

Cost. One pass over n symbols. Each symbol is pushed at most once and popped at most once, and each push or pop is O(1) (amortized), so the whole check is O(n). That answers the poll. Space is O(n) in the worst case (all openers).

4.1Two rules decide the order

To evaluate 14 ≤ 4 − 3 × 2 + 7 correctly, you cannot just go left to right. Two rules decide which operation happens first.

The slide lists precedence as “division, multiplication, addition/subtraction, comparison”. Read that as three levels, not four: × and ÷ share a level, which is exactly why the slide's own example x / y * z is decided by associativity, not precedence.

By hand: 3 × 2 = 6; then left to right, 4 − 6 = −2, −2 + 7 = 5; finally 14 ≤ 5 is False.

4.2The two-stack idea

Read tokens left to right with two stacks: valStk for numbers and opStk for operators waiting to be applied.

• A number is pushed onto valStk.
• An operator first forces out every waiting operator on top of opStk whose precedence is higher than or equal to its own (each one pops two values and pushes the result), and is then pushed itself.
• At the end, a special token $ with the lowest precedence of all forces out everything still waiting.

Why “higher or equal”? “Higher” enforces precedence: a waiting × must happen before a new + arrives. “Equal” enforces left-to-right associativity: in 10 − 4 − 3, when the second − arrives, the first − (equal precedence, further left) must be done first. With “strictly higher” you would compute 10 − (4 − 3) = 9 instead of 3.

Algorithm EvalExp(tokens):
    while there is another token z:
        if isNumber(z):
            valStk.push(z)
        else:
            repeatOps(z)
            opStk.push(z)
    repeatOps($)            # $ = end of input, lowest precedence
    return valStk.top()

Algorithm repeatOps(curOp):
    while valStk.size() > 1 and prec(curOp) <= prec(opStk.top()):
        doOp()

Algorithm doOp():
    x = valStk.pop()        # right operand: it was pushed last
    y = valStk.pop()        # left operand
    op = opStk.pop()
    valStk.push(y op x)

4.3Full trace of 14 ≤ 4 − 3 × 2 + 7

Stacks are written bottom … top.

The answer is valStk.top() = False, which is the poll answer.

PREC = {"<=": 0, "+": 1, "-": 1, "*": 2, "/": 2, "$": -1}   # $ = end of input

def do_op(vals, ops):
    x = vals.pop()                       # right operand (pushed last)
    y = vals.pop()                       # left operand
    op = ops.pop()
    result = {"+": y + x, "-": y - x, "*": y * x, "/": y / x, "<=": y <= x}[op]
    vals.push(result)

def repeat_ops(cur, vals, ops):
    # do every waiting operation that binds at least as tightly as cur
    while len(vals) > 1 and not ops.is_empty() and PREC[cur] <= PREC[ops.top()]:
        do_op(vals, ops)

def eval_exp(tokens):
    vals, ops = ArrayStack(), ArrayStack()
    for z in tokens:
        if isinstance(z, (int, float)):
            vals.push(z)
        else:
            repeat_ops(z, vals, ops)
            ops.push(z)
    repeat_ops("$", vals, ops)           # flush everything at the end
    return vals.top()

print(eval_exp([14, "<=", 4, "-", 3, "*", 2, "+", 7]))
print(eval_exp([10, "-", 4, "-", 3]))
print(eval_exp([8, "/", 4, "*", 2]))

False
3
4.0

The last line shows associativity at work: 8 / 4 × 2 is (8 / 4) × 2 = 4, not 8 / 8 = 1.

5.1What a span is

The span S[i] of X[i] is the largest number of consecutive elements, ending at X[i] and counting backwards (including X[i] itself), that are all ≤ X[i]. In finance: for each day, on how many consecutive days up to and including today was the stock price at most today's price?

Day 3 (price 5) looks back over 4 and 3 (both ≤ 5) and stops at 6, so its span is 3 (days 1, 2, 3). Day 4 (price 2) stops immediately at 5, so its span is 1.

5.2The direct method: O(n²)

Algorithm spansNoStack(X, n):
    S = array of n zeros
    for i = 0 to n - 1:
        j = i
        while j >= 0 and X[j] <= X[i]:   # walk left until something bigger
            S[i] = S[i] + 1
            j = j - 1
    return S

The worst case is a rising sequence, where every day walks all the way back to the start: 1 + 2 + … + n = n(n+1)/2 steps, which is O(n²).

5.3The key observation

The span depends on only one thing: the nearest earlier element strictly greater than X[i]. If that element is at index h, then everything between h and i is ≤ X[i], so

(The second case is the first with h = −1, an imaginary infinitely tall day before the start.)

Now the trick. Suppose day j has price ≤ day i's, with j < i. Can day j ever be “the nearest greater element” for any later day k > i? No: any later day that looks back far enough to reach j must first pass i, and i is at least as tall as j. Day j is hidden behind day i forever and can be thrown away.

What survives is the visible skyline: the days you could see looking left from the current day, each strictly taller than every day after it. Their prices decrease from left to right, and the nearest one is always the one added most recently. Most recent first: a stack.

5.4The stack algorithm: O(n)

Algorithm spansStack(X, n):
    S = array of n ones
    A = empty stack                      # holds INDICES, not prices
    for i = 0 to n - 1:
        while not A.is_empty() and X[A.top()] <= X[i]:
            A.pop()                      # hidden behind day i: discard
        if A.is_empty():
            S[i] = i + 1                 # nothing to the left is bigger
        else:
            S[i] = i - A.top()           # top = nearest greater element
        A.push(i)
    return S

The stack holds indices because the formula needs a position (i − h), and the price is always available as X[h].

5.5Why it is O(n) despite the nested loop

A while inside a for often means O(n²), so look closer. Do not count per iteration of the outer loop; count per index over the whole run. Each index is pushed exactly once (at its own iteration) and popped at most once (after that it is gone). So across the entire algorithm there are at most n pops, and the while body runs at most n times in total. Everything else is O(1) per iteration. Total: O(n).

This style of argument, charging each unit of work to the element that causes it, is the same one that proved append is O(1) amortized. It returns on the queue page for the two-stack queue.

def spans_no_stack(X):
    S, work = [0] * len(X), 0
    for i in range(len(X)):
        j = i
        while j >= 0 and X[j] <= X[i]:   # walk left past smaller-or-equal days
            S[i] += 1
            j -= 1
            work += 1
    return S, work

def spans_stack(X):
    S, work = [1] * len(X), 0
    A = ArrayStack()                     # holds INDICES of still-visible days
    for i in range(len(X)):
        while not A.is_empty() and X[A.top()] <= X[i]:
            A.pop()                      # hidden behind day i forever
            work += 1
        S[i] = i + 1 if A.is_empty() else i - A.top()
        A.push(i)
    return S, work

print(spans_no_stack([6, 3, 4, 5, 2]))
print(spans_stack([6, 3, 4, 5, 2]))
rising = list(range(1000))               # worst case for the naive version
print("naive steps:", spans_no_stack(rising)[1], "  stack pops:", spans_stack(rising)[1])

([1, 1, 2, 3, 1], 8)
([1, 1, 2, 3, 1], 2)
naive steps: 500500   stack pops: 999

The second number in each pair counts loop steps. On a rising array of 1,000 prices the direct method takes 500,500 steps; the stack method pops 999 times.

Ideas to carry forward

1. Geometric growth makes dynamic arrays O(1) amortized; growth by a fixed amount makes them O(n) per append.
2. Amortized ≠ worst case. One push can cost O(n); a long run averages O(1).
3. Count per element, not per loop iteration. “Each item is pushed once and popped at most once” turns a nested loop into O(n).
4. Spot the pattern. “Most recent unfinished”, “nearest earlier bigger”, “undo the last” all mean stack.
5. In doOp, the right operand comes off first.