Gregory Friedman The Greg Wide Web on the name →

Data Structures & Algorithms · demo

The Lab

A guided workbench in the spirit of Codecademy or Brilliant: instructions on the left, a Python editor on the right, and a sequence of small tasks whose checks gate your progress. The same in-browser interpreter that powers every other workbench on this site runs here, downloaded once on your first Run. Nothing is saved; reload and you start clean.

The lesson below builds a stack, the last-in-first-out pile, one method at a time. Your code carries forward from step to step, so you are always adding to the class you already wrote.

Build a Stack, one method at a time

Four steps: push, pop, a guard for the empty case, and a size.

  1. Step 1 of 4 · I

    Push

    A stack is a pile: you add to the top and you take from the top, last in, first out. We keep the pile in a plain Python list, self._items, with the top at the end of the list.

    Give push a body so it puts item on top. One line will do it.

    Starter

    class Stack:
        def __init__(self):
            self._items = []
    
        def push(self, item):
            pass  # your code here
    

    The checks

    • push stores the item
    • push keeps order, newest on top
  2. Step 2 of 4 · II

    Pop

    Now the other half. pop should remove the top item and return it. Because the top is the end of the list, a list's own .pop() does exactly the right thing.

    Add a pop method to the class you just wrote.

    Starter

    class Stack:
        def __init__(self):
            self._items = []
    
        def push(self, item):
            self._items.append(item)
    
        def pop(self):
            pass  # your code here
    

    The checks

    • pop returns the top item
    • pop shrinks the stack
  3. Step 3 of 4 · III

    Empty means empty

    What should popping an empty stack do? A list would raise IndexError with a vague message, or worse, some code returns None and hides the bug. We want a clear signal.

    Guard pop: if the stack is empty, raise IndexError('pop from empty stack') before touching the list.

    Starter

    class Stack:
        def __init__(self):
            self._items = []
    
        def push(self, item):
            self._items.append(item)
    
        def pop(self):
            # add a guard, then return the top item
            return self._items.pop()
    

    The checks

    • an empty pop raises a clear IndexError
    • a non-empty pop still returns the top
  4. Step 4 of 4 · IV

    How tall is the pile?

    Last touch: let the stack report its own size, so len(s) just works. Python calls the __len__ method for that.

    Add __len__ so it returns how many items are on the stack.

    Starter

    class Stack:
        def __init__(self):
            self._items = []
    
        def push(self, item):
            self._items.append(item)
    
        def pop(self):
            if not self._items:
                raise IndexError('pop from empty stack')
            return self._items.pop()
    
        def __len__(self):
            pass  # your code here
    

    The checks

    • a fresh stack has length 0
    • push and pop change the length

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.