ADT vs Data Structure: Interface and Implementation

An ADT (abstract data type) describes what a type does: operations, errors and invariants. A data structure is how it is done: an array, a linked list, a hash table. In this lesson we write the same stack and map interface in two ways. Expressing an interface in Python comes in the next lesson: Implementing ADTs in Python.

An ADT: operations and a contract

The contract of a Stack ADT: push(x) adds an item, pop() returns and removes the most recently added one (LIFO), pop() on an empty stack raises IndexError, and len always equals pushes minus pops. These sentences mention no array and no pointers: that is the ADT. Below it is written on a list; the function drain knows only len and pop.

class ListStack:
    def __init__(self):
        self._items = []

    def push(self, x):
        self._items.append(x)

    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def __len__(self):
        return len(self._items)