图 6.10 现实中的堆栈例子

如果忽略各种具体堆栈中无关紧要的成分，如所堆放的东西（碗、书、子弹）、容器（纸箱、碗橱、弹夹）和放入/取出的具体实现（人工、机械），那么我们可以抽象地定义堆栈。 所谓堆栈，是以如下两个操作进行处理的数据结构：

此前介绍的数据类型大多是具体的，即它们的实现方式是给定的，例如 int 类型是以 4 个字节来表示，字符串类型是特定编码的字节串等等。而现在我们所讨论的堆栈则是抽象数 据类型，因为我们只规定了堆栈的操作方式，并没有规定操作的具体实现方式。

在具体应用中，可以采用多种不同的方式来实现堆栈这个抽象数据类型。例如，可以采 用列表来实现堆栈。令列表 stack 是存放数据的堆栈，按照堆栈的要求，对 stack 只能执行 push 和 pop 操作，不能像列表那样可以随机存取任何一个元素。假设以列表头为栈底，以 列表尾为栈顶，那么向堆栈中放入元素就只能在尾部添加，Python 列表对象提供的 append 方法正好提供堆栈所需的功能，因此可以用 append 来实现 push()，形如：

另外，Python 列表对象的 pop()方法的功能是取出列表的最后一个元素，恰好符合堆栈的 pop()方法的要求，因此可以这样实现堆栈 pop 操作：

为了防止从空堆栈中取数据的错误，我们定义一个检测堆栈是否为空的函数：

利用上述以列表实现堆栈的技术，程序 6.5 首先通过用户输入数据创建一个堆栈，然后 再逐个取出堆栈成员。输出恰好是输入的逆序，这是由堆栈的 LIFO 性质决定的。可见，利 用堆栈来逆序显示列表数据是非常容易的。

【程序 6.5】stack.py

堆栈在计算机科学中非常有用，一个常见的用例是实现表达式的计算。 读者都熟悉算术表达式的中缀形式，但在用计算机处理表达式时常将表达式写成后缀形式，例如“1 + 2”可写成“1 2 +”、“3 + 4 5”可写成“3 4 5 +”。后缀形式的表达式可以 利用堆栈来非常方便地求值，算法如下：

1. 扫描后缀形式的表达式，每次读一个符号（运算数或者运算符）；

2. 如果读到的是运算数，则 push 到堆栈中；如果读到的是运算符，则从堆栈 pop 两个运算 数，并执行该运算，然后将运算结果 push 入堆栈；

3. 重复 1、2，直至到达表达式尾。这时堆栈中应该只剩一个运算数，就是表达式的结果值。

图 6.11 显示的是“3 4 5 * +”的计算过程。

以上求值部分非常容易实现，但要想对用户输入的中缀形式的算术表达式进行求值，还 需要先对输入进行语法分析，拆分出运算符和运算数，然后改成后缀形式。这部分编程有点 复杂，所以在此我们就不实现这个程序了。有兴趣的读者可以尝试解决这个问题。