На этом шаге мы рассмотрим, каким образом можно смоделировать башни.
Стек - это структура данных, смоделированная по принципу " " (last-in-first-out, LIFO). То, что попадает в стек последним, становится первым, что оттуда извлекается. Две основные операции стека - это push (поместить) и pop (извлечь). Операция push помещает новый элемент в стек, a pop удаляет из стека и возвращает последний вставленный элемент. Можно легко смоделировать стек в Python, используя список в качестве резервного хранилища.
from typing import TypeVar, Generic, List T = TypeVar('T') class Stack(Generic[T]): def __init__(self) -> None: self._container: list[T] = [] 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)
В представленном классе Stack реализован метод __repr__(), позволяющий легко исследовать содержимое башни. __repr__() - это то, что будет выводиться при применении к стеку функции print().
В приводимых примерах используются аннотации типов. Импорт Generic из модуля ввода позволяет Stack быть параметрическим классом для определенного типа в аннотациях типов.
Произвольный тип Т определен в Т = TypeVar (Т). Т может быть любым типом. Когда впоследствии аннотация типа будет задействоваться для Stack при решении
задачи о ханойских башнях, в подсказке будет стоять Stack[int], то есть вместо Т будет применен тип int. Другими словами, здесь стек - это стек целых чисел.
Стеки идеально подходят для задачи о ханойских башнях. Для того чтобы переместить диск на башню, мы можем использовать операцию push. Для того чтобы переместить диск с одной башни на другую, мы можем вытолкнуть его с первой (pop) и поместить на вторую (push).
Определим башни как объекты Stack и заполним первую из них дисками.
num_discs: int = 3 tower_a: Stack[int] = Stack() tower_b: Stack[int] = Stack() tower_c: Stack[int] = Stack() for i in range(1, num_discs + 1): tower_a.push(i)
На следующем шаге мы приведем решение этой задачи.
