6.5.2 堆栈
最后更新于：2022-04-02 00:29:46
### 6.5.2 堆栈
堆栈（stack）也是一种数据集合体，其中的数据构成一种具有“后进先出（LIFO）”性 质的数据结构，即最后加入堆栈的数据总是首先取出。现实中堆栈的例子俯拾皆是，例如碗橱里的一摞碗、纸箱里的一摞书、弹夹中的子弹等等（图 6.10），他们共同的特点是先放进 去的东西垫底，最后放进去的东西在顶上，而取东西的顺序正好相反。
图 6.10 现实中的堆栈例子
如果忽略各种具体堆栈中无关紧要的成分，如所堆放的东西（碗、书、子弹）、容器（纸箱、碗橱、弹夹）和放入/取出的具体实现（人工、机械），那么我们可以抽象地定义堆栈。 所谓堆栈，是以如下两个操作进行处理的数据结构：
+ push(x)：在堆栈顶部推入一个新数据 x，x 即成为新的栈顶元素；
+ pop()：从堆栈中取出栈顶元素，显然被取出的元素只能是最后加入堆栈的元素。 为了完善这两个操作，还需提供一些辅助操作，如：
+ isFull()：检查堆栈是否已满。如果堆栈具有固定大小，那么满了之后是无法执行 push()的；
+ isEmpty()：检查堆栈是否为空。如果堆栈是空的，那么 pop()操作将出错。
此前介绍的数据类型大多是具体的，即它们的实现方式是给定的，例如 int 类型是以 4 个字节来表示，字符串类型是特定编码的字节串等等。而现在我们所讨论的堆栈则是抽象数 据类型，因为我们只规定了堆栈的操作方式，并没有规定操作的具体实现方式。
在具体应用中，可以采用多种不同的方式来实现堆栈这个抽象数据类型。例如，可以采 用列表来实现堆栈。令列表 stack 是存放数据的堆栈，按照堆栈的要求，对 stack 只能执行 push 和 pop 操作，不能像列表那样可以随机存取任何一个元素。假设以列表头为栈底，以 列表尾为栈顶，那么向堆栈中放入元素就只能在尾部添加，Python 列表对象提供的 append 方法正好提供堆栈所需的功能，因此可以用 append 来实现 push()，形如：
```
def push(stack,x):
stack.append(x)
```
另外，Python 列表对象的 pop()方法的功能是取出列表的最后一个元素，恰好符合堆栈的 pop()方法的要求，因此可以这样实现堆栈 pop 操作：
```
def pop(stack):
return stack.pop()
```
为了防止从空堆栈中取数据的错误，我们定义一个检测堆栈是否为空的函数：
```
def isEmpty(stack):
return (stack == [])
```
利用上述以列表实现堆栈的技术，程序 6.5 首先通过用户输入数据创建一个堆栈，然后 再逐个取出堆栈成员。输出恰好是输入的逆序，这是由堆栈的 LIFO 性质决定的。可见，利 用堆栈来逆序显示列表数据是非常容易的。
【程序 6.5】stack.py
```
def push(stack,x):
stack.append(x)
def pop(stack):
return stack.pop()
def isEmpty(stack):
return (stack == [])
def main():
stack = []
print "Pushing..."
x = raw_input("Enter a string: ")
while x != "":
push(stack,x)
x = raw_input("Enter a string: ")
print "Popping..."
while not isEmpty(stack):
print pop(stack),
main()
```
下面是程序 6.5 的一次执行情况：
```
Pushing...
Enter a string: 1st
Enter a string: 2nd
Enter a string: 3rd
Enter a string: 4th
Enter a string: Popping...
4th 3rd 2nd 1st
```
堆栈在计算机科学中非常有用，一个常见的用例是实现表达式的计算。 读者都熟悉算术表达式的中缀形式，但在用计算机处理表达式时常将表达式写成后缀形式，例如“1 + 2”可写成“1 2 +”、“3 + 4 * 5”可写成“3 4 5 * +”。后缀形式的表达式可以 利用堆栈来非常方便地求值，算法如下：
1\. 扫描后缀形式的表达式，每次读一个符号（运算数或者运算符）；
2\. 如果读到的是运算数，则 push 到堆栈中；如果读到的是运算符，则从堆栈 pop 两个运算 数，并执行该运算，然后将运算结果 push 入堆栈；
3\. 重复 1、2，直至到达表达式尾。这时堆栈中应该只剩一个运算数，就是表达式的结果值。
图 6.11 显示的是“3 4 5 * +”的计算过程。
图 6.11 利用堆栈对后缀表达式求值
以上求值部分非常容易实现，但要想对用户输入的中缀形式的算术表达式进行求值，还 需要先对输入进行语法分析，拆分出运算符和运算数，然后改成后缀形式。这部分编程有点 复杂，所以在此我们就不实现这个程序了。有兴趣的读者可以尝试解决这个问题。
';