学点算法之栈的学习与应用

在学习前，脑海中对这个词只有一个印象：

栈是什么

栈（有时称为“后进先出栈”）是一个项的有序集合，其中添加移除新项总发生在同一端。

这段话初学者是懵逼的，别急，往下看。

对栈的一般操作：

Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。

push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。

pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。

peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。

isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。

size() 返回栈中的 item 数量。不需要参数，并返回一个整数。

例如，s 是已经创建的空栈，下图展示了栈操作序列的结果。栈中，顶部项列在最右边。

自己在心里过一遍就很好理解了

Python实现栈

其实看到上面那张图，就想起了Python中的一些用法，append、pop等，下面是使用 Python 来实现栈，也非常简单：

pythonds/basic/stack.py

栈的应用：简单括号匹配（一）

有一些正确匹配的括号字符串：

对比那些不匹配的括号：

具有挑战的是如何编写一个算法，能够从左到右读取一串符号，并决定符号是否平衡。

为了解决这个问题，我们需要做一个重要的观察。从左到右处理符号时，最近开始符号必须与下一个关闭符号相匹配。此外，处理的第一个开始符号必须等待直到其匹配最后一个符号。结束符号以相反的顺序匹配开始符号。他们从内到外匹配。这是一个可以用栈解决问题的线索。

output

一旦你认为栈是保存括号的恰当的数据结构，算法是很直接的。

从空栈开始，从左到右处理括号字符串。如果一个符号是一个开始符号，将其作为一个信号，对应的结束符号稍后会出现。另一方面，如果符号是结束符号，弹出栈，只要弹出栈的开始符号可以匹配每个结束符号，则括号保持匹配状态。如果任何时候栈上没有出现符合开始符号的结束符号，则字符串不匹配。最后，当所有符号都被处理后，栈应该是空的。

如果有和我一样不能很好理解的，使用pycharm的debug模式，可以一步步来，看看程序就近在做什么。

括号配对问题（二）

来看看第二种匹配问题。Python程序里存在很多括号：如圆括号、方括号和花括号，每种括号都有开括号和闭括号。

output

生成器（回忆一下）：

用 yield 语句产生结果

可以用在需要迭代器的地方

函数结束导致迭代结束

参考

http://interactivepython.org/runestone/static/pythonds/BasicDS/TheStackAbstractDataType.html

http://www.math.pku.edu.cn/teachers/qiuzy/ds_python/courseware/index.htm