Python算法应用实战之栈详解

栈(stack)

栈又称之为堆栈是一个特殊的有序表，其插入和删除操作都在栈顶进行操作，并且按照先进后出，后进先出的规则进行运作。

如下图所示

例如枪的弹匣，第一颗放进弹匣的子弹反而在发射出去的时候是最后一个，而最后放入弹匣的一颗子弹在打出去的时候是第一颗发射出去的。

栈的接口

如果你创建了一个栈，那么那么应该具有以下接口来进行对栈的操作

知道栈需要上述的接口后，那么在Python中，列表就类似是一个栈，提供接口如下：

Python中的栈接口使用实例：

# 创建一个栈In [1]: s = []# 往栈内添加一个元素In [2]: s.append(1)In [3]: sOut[3]: [1]# 删除栈内的一个元素In [4]: s.pop()Out[4]: 1In [5]: sOut[5]: []# 判断栈是否为空In [6]: not sOut[6]: TrueIn [7]: s.append(1)In [8]: not sOut[8]: False# 获取栈内元素的数量In [9]: len(s)Out[9]: 1In [10]: s.append(2)In [11]: s.append(3)# 取栈顶的元素In [12]: s[-1]Out[12]: 3

一大波实例

在了解栈的基本概念之后，让我们再来看几个实例，以便于理解栈。

括号匹配

题目

假如表达式中允许包含三中括号()、[]、{}，其嵌套顺序是任意的，例如：

正确的格式

{()[()]},[{({})}]

错误的格式

[(]),[()),(()}

编写一个函数，判断一个表达式字符串，括号匹配是否正确

思路

创建一个空栈，用来存储尚未找到的左括号； 便利字符串，遇到左括号则压栈，遇到右括号则出栈一个左括号进行匹配； 在第二步骤过程中，如果空栈情况下遇到右括号，说明缺少左括号，不匹配； 在第二步骤遍历结束时，栈不为空，说明缺少右括号，不匹配；