На этом шаге мы рассмотрим реализацию стека.

    Алгоритм поиска в глубину опирается на структуру данных, известную как стек. Стек - это структура данных, которая работает по принципу "последним пришел - первым вышел" (last-in-first-out, LIFO). Стек можно представить как стопку документов. Последний документ, помещенный сверху стопки, будет первым, который оттуда извлекут. Обычно стек реализуется на основе более примитивной структуры данных, такой как список. Мы будем реализовывать стек на основе типа list Python.

    Обычно стек имеет как минимум две операции:

• push() - помещает элемент в вершину стека;
• рор() - удаляет элемент из вершины стека и возвращает его.

    Мы реализуем обе эти операции, а также создадим свойство empty, чтобы проверить, остались ли в стеке еще элементы. Разместим код стека в файле generic_search.ру, с которым уже работали (20 шаг). Все, что нужно было импортировать, мы уже импортировали.

class Stack(Generic[T]):
    def __init__(self) -> None:
        self._container: List[T] = []

    @property
    def empty(self) -> bool:
        return not self._container  # не равно True для пустого контейнера

    def push(self, item: T) -> None:
        self._container.append(item)

    def pop(self) -> T:
        return self._container.pop()

    def __repr__(self) -> str:
        return repr(self._container)

    Обратите внимание на то, что реализовать стек с использованием типа list в Python означает просто всегда добавлять и удалять элементы только с его правого конца. Метод рор() для list будет реализован неудачно, если в списке не осталось элементов, поэтому рор() потерпит неудачу в стеке, если он пуст.

    На следующем шаге мы рассмотрим алгоритм поиска в глубину.

Предыдущий шаг Содержание Следующий шаг