ADT (абстрактный тип данных) описывает, что делает тип: операции, ошибки и инварианты. Структура данных — это то, как это сделано: массив, связный список, хеш-таблица. В этом уроке мы напишем один и тот же интерфейс стека и словаря двумя способами. Оформление интерфейса средствами Python — в следующем уроке: ADT в Python: ABC, Protocol и тесты контракта.

Клиентский код работает через интерфейс Stack ADT, его реализуют две структуры
Клиентский код работает через интерфейс Stack ADT, его реализуют две структуры

ADT: операции и контракт

Контракт Stack ADT: push(x) добавляет элемент, pop() возвращает и удаляет последний добавленный (LIFO), на пустом стеке pop() бросает IndexError, а len всегда равен разности числа push и pop. В этих фразах нет ни массива, ни указателей — это и есть ADT. Ниже он написан на list; функция drain знает только len и pop.

python
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)