Practical 15: the Stack ADT

the same exercise over two different implementations

  a new ArrayStack: empty? True
    push 10 -> ArrayStack(bottom [10] top) size 1
    push 20 -> ArrayStack(bottom [10, 20] top) size 2
    push 30 -> ArrayStack(bottom [10, 20, 30] top) size 3
    peek  -> 30 and the size is still 3
    pop   -> 30 -> ArrayStack(bottom [10, 20] top)
    pop   -> 20 -> ArrayStack(bottom [10] top)
    pop   -> 10 -> empty? True
    one pop too many: IndexError: pop from an empty stack

  a new LinkedStack: empty? True
    push 10 -> LinkedStack(top 10 bottom) size 1
    push 20 -> LinkedStack(top 20 10 bottom) size 2
    push 30 -> LinkedStack(top 30 20 10 bottom) size 3
    peek  -> 30 and the size is still 3
    pop   -> 30 -> LinkedStack(top 20 10 bottom)
    pop   -> 20 -> LinkedStack(top 10 bottom)
    pop   -> 10 -> empty? True
    one pop too many: IndexError: pop from an empty stack

One exercise function, two stacks

That is the thing to notice, and it is worth a mark in the viva. exercise calls push, pop, peek, is_empty and len, and it does not know or care which class it was given. Both classes implement the same ADT, so both satisfy the same code.

The output differs in exactly one respect: the __repr__, because that prints the representation and the representation is the thing that differs. Every answer to every operation is identical.

The choice of which end is the top

This is the design decision in each class, and getting it wrong makes a correct stack slow.

Both are the cheap end of their own structure, and they are opposite ends. A student who puts the top of an array stack at index 0 has written a stack that is correct and O(n) per operation, and [Practical 12: Singly Linked Lists] measured what that costs: about 99 times slower for 20000 operations.

Array against linked list, for a stack

"O(1) amortised" is worth explaining, because an examiner may ask. A Python list occasionally has to move to a bigger block, which costs O(n) for that one append. It happens rarely enough that the average over many appends is constant, and that average is what "amortised" means. The linked list has no such moment: every push costs the same.

Overflow is the one thing this pair does not show, because Python lists grow. In C a stack is usually a fixed array with a top index, and then push must check top == MAX - 1 and report stack overflow, while pop checks top == -1 and reports stack underflow. Those two words are examination vocabulary, and the linked version cannot overflow at all, which is its main advantage.

MU's first application: matching delimiters

Every opening bracket must be closed, by the right kind of bracket, in the right order. A stack is the natural answer, and the reason is worth stating: the bracket that must be closed next is always the one opened most recently, which is the definition of LIFO.

PAIRS = {")": "(", "]": "[", "}": "{"}
OPENERS = set(PAIRS.values())


def check_delimiters(text):
    """Returns (True, '') or (False, why). One stack, one pass."""
    stack = []
    for at, ch in enumerate(text):
        if ch in OPENERS:
            stack.append((ch, at))
        elif ch in PAIRS:
            if not stack:
                return False, f"{ch!r} at position {at} closes nothing"
            opener, where = stack.pop()
            if opener != PAIRS[ch]:
                return False, (f"{ch!r} at position {at} does not match "
                               f"{opener!r} at position {where}")
    if stack:
        opener, where = stack[-1]
        return False, f"{opener!r} at position {where} is never closed"
    return True, ""


tests = [
    "a = (b + [c * d]) - {e}",
    "print(items[0])",
    "",
    "(a + [b)]",
    "a = (b + c",
    "a = b + c)",
    "([{}])",
    "{[(])}",
]

print(f"  {'text':<26}{'balanced':<10}why")
for t in tests:
    ok, why = check_delimiters(t)
    print(f"  {t!r:<26}{str(ok):<10}{why}")

  text                      balanced  why
  'a = (b + [c * d]) - {e}' True
  'print(items[0])'         True
  ''                        True
  '(a + [b)]'               False     ')' at position 7 does not match '[' at position 5
  'a = (b + c'              False     '(' at position 4 is never closed
  'a = b + c)'              False     ')' at position 9 closes nothing
  '([{}])'                  True
  '{[(])}'                  False     ']' at position 3 does not match '(' at position 2

The algorithm in four lines

1. An opener is pushed, with its position.
2. A closer pops. If the stack was empty, this closer closes nothing.
3. If the popped opener is not the matching kind, the two do not match.
4. At the end, anything left on the stack was never closed.

All four failure modes appear in the run, and a complete answer reports all four:

The position is pushed with the bracket, which is why the messages can name where. A matcher that pushes only the character can say that something is wrong and not where, and an editor that cannot point at the mistake is not much use.

The empty string is balanced, and it is in the tests on purpose. A program that reports an error for it has an off-by-one somewhere, and the empty case is the cheapest test in any exercise in this module.

A dictionary from closer to opener is better than three ifs. PAIRS[ch] is one lookup and adding another kind of bracket is one line. Three chained conditions are three chances to get a character wrong, and every real language has more than three kinds of bracket to match.

MU's second application: an undo mechanism

[Practical 14: Doubly Linked Lists] built undo and redo with a cursor on a list. If redo is not needed, a single stack is enough and far simpler.

class Editor:
    """Undo with a stack. Each entry is what to do to go back."""

    def __init__(self):
        self.text = ""
        self.undo_stack = []

    def type(self, s):
        self.text += s
        self.undo_stack.append(("remove_last", len(s)))

    def delete_last(self, n):
        if n > len(self.text):
            raise ValueError(f"there are only {len(self.text)} characters")
        removed = self.text[-n:]
        self.text = self.text[:-n]
        self.undo_stack.append(("put_back", removed))

    def replace_all(self, old, new):
        before = self.text
        self.text = self.text.replace(old, new)
        self.undo_stack.append(("restore", before))

    def undo(self):
        if not self.undo_stack:
            raise IndexError("there is nothing to undo")
        what, arg = self.undo_stack.pop()
        if what == "remove_last":
            self.text = self.text[:-arg]
        elif what == "put_back":
            self.text = self.text + arg
        else:
            self.text = arg
        return what


e = Editor()
e.type("Computer Science ")
e.type("Practical 3")
e.replace_all("Practical", "Prac.")
e.delete_last(6)

print("  the text now      :", repr(e.text))
print("  actions on the stack:", len(e.undo_stack))
while e.undo_stack:
    what = e.undo()
    print(f"  undo {what:<12} -> {e.text!r}")
try:
    e.undo()
except IndexError as ex:
    print("  one undo too many : IndexError:", ex)

  the text now      : 'Computer Science P'
  actions on the stack: 4
  undo put_back     -> 'Computer Science Prac. 3'
  undo restore      -> 'Computer Science Practical 3'
  undo remove_last  -> 'Computer Science '
  undo remove_last  -> ''
  one undo too many : IndexError: there is nothing to undo

The idea: push the reverse, not the action

Each entry on the stack says how to go back, not what was done:

The third row is the interesting one and the reason the run includes it. "Replace all Practical with Prac." cannot be undone by replacing Prac. with Practical, because the text may have contained Prac. already, and then the undo would change something the user never touched. When an action cannot be reversed from its arguments, store the state before it. That is the general rule, and it is why real editors keep snapshots as well as actions.

The stack comes off in the right order for nothing. The run undoes four actions and each one is the most recent remaining, because that is what a stack is. No sorting, no timestamps, no book-keeping: LIFO is exactly the semantics of undo.

Redo needs a second stack, and it is one line in each method: undo pushes what it undid on to a redo stack, redo pops from it and pushes back on to the undo stack, and any new action clears the redo stack. That last line is the same rule as the cursor version in [Practical 14: Doubly Linked Lists]: doing something new discards what was in front.

Procedure

1. Write both stack classes and the exercise function. Run it and confirm every answer is the

same for both.

1. Change ArrayStack so that the top is index 0, using insert(0, x) and pop(0). Confirm it

is still correct, then time 100000 pushes on both versions.

1. Add a size limit to ArrayStack and make push raise on overflow. That is the C version,

and the word is worth having.

1. Write the delimiter matcher. Add angle brackets to PAIRS and confirm it takes one line.
2. Run the matcher over one of your own Python files, read as a string, and note what it says

about the brackets inside string literals. That is a real limitation and worth a sentence in the journal.

1. Write the editor. Add a redo stack and the line that clears it on a new action.
2. Write is_palindrome(word) using a stack: push every character, then pop them and compare. It

is a standard examination question and it is four lines.

Result

The Stack abstract data type was implemented twice, over a Python list with the top at the end and over a singly linked list with the top at the head, and one exercise function was shown to drive both without change, every answer identical. Both give push, pop and peek in constant time by choosing the cheap end of their own structure. A delimiter matcher was built on a stack and reported all four kinds of fault, naming the position in each case. An undo mechanism was built on a single stack, storing the reverse of each action, and the case of an action that cannot be reversed from its arguments was handled by storing the state before it.

Where marks are lost

• Putting the top of an array stack at index 0. Correct and O(n) per operation.
• pop returning None on an empty stack instead of raising.
• No peek, or a peek that removes the item.
• Letting a caller index into the stack. A stack has five operations and indexing is not one

of them.

• Three ifs instead of a dictionary in the matcher, and then missing a bracket kind.
• Reporting only that the delimiters are unbalanced, not which one and where.
• Not checking the stack at the end of the matcher, so a = (b + c passes.
• Not handling the empty input.
• Undoing by re-deriving the action where the action is not reversible from its arguments, as

with replace-all.

• Not knowing the words overflow and underflow, which is what the C version is examined on.

For the journal

Write the aim, MU's own wording, the five operations of the ADT with what each does to an empty stack, and the picture of a pile of plates. Then both implementations and the one run that drives both, and one sentence saying that the outputs are identical except for the representation, because that sentence is the answer to what an ADT is. Then the matcher with all eight test lines, because the four failure modes are what make the answer complete, and the undo with its four actions undone in order. The conclusion: a stack is LIFO with five operations, it can be built over an array or a chain by choosing the cheap end of each, and the problems it solves are the ones where the thing to deal with next is always the thing seen most recently.

Quick revision

• A stack is LIFO: last in, first out. Five operations: push, pop, peek, is_empty, len. Nothing

else.

• pop and peek on an empty stack raise. Returning None cannot be told from a stored None.
• Over an array the top is the end; over a linked list the top is the head. Both are the

cheap end of that structure, and they are opposite ends.

• ArrayStack.push is O(1) amortised, because the list occasionally moves to a bigger block.

LinkedStack.push is O(1) always.

• In C a fixed-array stack can overflow; popping an empty one is underflow. A linked stack

cannot overflow.

• One function can drive both implementations without change. That is what an abstract data type

means.

• Delimiter matching: push openers with their position, pop on a closer, check the kind matches,

and check the stack is empty at the end. Four failure modes, and a complete answer reports all four.

• Use a dictionary from closer to opener, not a chain of ifs.
• Undo: push the reverse of each action. Where an action cannot be reversed from its

arguments, push the state before it.

• Redo needs a second stack, and a new action clears it.
• A stack is also the call stack, depth-first search, and expression evaluation.

Questions you should be able to answer

1. What does LIFO mean and what are the five operations of a stack? Last in, first out: the only reachable item is the one added most recently. Push, pop, peek, is_empty and a size.

2. Where is the top in an array implementation and in a linked implementation, and why? At the end of the array and at the head of the chain. Those are the cheap ends: appending and popping the end of a Python list are O(1), and prepending and removing the head of a chain are O(1).

3. What happens if you put the top of an array stack at index 0? Every push and pop then shifts every other item, so each operation is O(n) instead of O(1). The stack is still correct and it is unusably slow for large sizes.

4. Why must pop on an empty stack raise rather than return None? Because None may be a value somebody pushed, so the caller could not tell an empty stack from one whose top is None.

5. What is stack overflow, and can a linked stack suffer it? Overflow is pushing on to a stack that has reached its fixed capacity, which happens in a C array implementation. A linked stack allocates a node per push, so it cannot overflow until the machine runs out of memory.

6. Why is a stack the right structure for matching brackets? Because the bracket that has to be closed next is always the one opened most recently, which is exactly LIFO.

7. Name the four things a delimiter matcher must detect. A closer of the wrong kind, a closer when nothing is open, an opener that is never closed, and, in passing, that the empty input is balanced rather than an error.

8. Why does an undo stack store the state before a replace-all rather than the replacement? Because reversing the replacement would also change text that already contained the new string before the action, which the user never touched. When an action cannot be reversed from its arguments, the state before it is stored.

9. What does "O(1) amortised" mean? That a single operation may occasionally cost more, here when the list moves to a bigger block, but rarely enough that the average cost over many operations is constant.