15-对塔进行建模

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

1.5.1　对塔进行建模

栈是按照后进先出（LIFO）理念建模的数据结构。最后入栈的数据项会最先出栈。栈的两个最基本操作是压入（push）和弹出（pop）。压入操作是把一个新数据项放入栈中，而弹出操作则是移除并返回最后一次放入的数据项。在Python中用 list 类型作为底层存储，即可轻松对栈进行建模。具体代码如代码清单1-20所示。

代码清单1-20　hanoi.py

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__() 方法，这样想要查看某个塔的状况就比较容易了。对 Stack 类调用 print() 时，输出的就是 __repr__() 的结果。

注意　正如本书引言中所述，本书通篇都会使用类型提示。从 typing 模块导入 Generic ，就能让 Stack 在类型提示时泛型化为某种类型。 T = TypeVar('T') 定义了任意类型 T 。 T 可以是任何类型。后续在求解汉诺塔问题时使用的 Stack ，就用到了类型提示，类型提示为 Stack[int] 类型，表示 T 应该填入 int 类型的数据。换句话说，该栈是一个整数栈。如果对类型提示还存在困惑，不妨阅读一下附录C。

栈是汉诺塔的完美表现。要把圆盘放到塔上，可以进行压入操作。要把圆盘从一个塔移到另一个塔，就可以先从第一个塔弹出再压入第二个塔上。

下面将塔定义为 Stack ，并把圆盘码放在第一个塔上，具体代码如代码清单1-21所示。

代码清单1-21　hanoi.py（续）

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)

Previous 上一篇本节目录 Next 下一篇

15-对塔进行建模

1.5.1 对塔进行建模

1.5.1　对塔进行建模