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 利用堆栈对后缀表达式求值

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