作者：安生
原文：https://blog.ansheng.me/article/python-algorithm-combat-series-stack/
栈(stack)又称之为堆栈是一个特殊的有序表，其插入和删除操作都在栈顶进行操作，并且按照先进后出，后进先出的规则进行运作。
如下图所示
例如枪的弹匣，第一颗放进弹匣的子弹反而在发射出去的时候是最后一个，而最后放入弹匣的一颗子弹在打出去的时候是第一颗发射出去的。
栈的接口
如果你创建了一个栈，那么那么应该具有以下接口来进行对栈的操作
| 接口 |
描述 |
| push() |
入栈 |
| pop() |
出栈 |
| isEmpty() |
判断是否为空栈 |
| length() |
获取栈的长度 |
| getTop() |
取栈顶的元素，元素不出栈 |
知道栈需要上述的接口后，那么在Python中，列表就类似是一个栈，提供接口如下：
| 操作 |
描述 |
| s = [] |
创建一个栈 |
| s.append(x) |
往栈内添加一个元素 |
| s.pop() |
在栈内删除一个元素 |
| not s |
判断是否为空栈 |
| len(s) |
获取栈内元素的数量 |
| s[-1] |
获取栈顶的元素 |
Python中的栈接口使用实例：
# 创建一个栈
In [1]: s = []
# 往栈内添加一个元素
In [2]: s.append(1)
In [3]: s
Out[3]: [1]
# 删除栈内的一个元素
In [4]: s.pop()
Out[4]: 1
In [5]: s
Out[5]: []
# 判断栈是否为空
In [6]: not s
Out[6]: True
In [7]: s.append(1)
In [8]: not s
Out[8]: False
# 获取栈内元素的数量
In [9]: len(s)
Out[9]: 1
In [10]: s.append(2)
In [11]: s.append(3)
# 取栈顶的元素
In [12]: s[-1]
Out[12]: 3
一大波实例
在了解栈的基本概念之后，让我们再来看几个实例，以便于理解栈。
括号匹配
题目
假如表达式中允许包含三中括号()、[]、{}，其嵌套顺序是任意的，例如：
正确的格式
{()[()]},[{({})}]
错误的格式
[(]),[()),(()}
编写一个函数，判断一个表达式字符串，括号匹配是否正确
思路
创建一个空栈，用来存储尚未找到的左括号； 便利字符串，遇到左括号则压栈，遇到右括号则出栈一个左括号进行匹配； 在第二步骤过程中，如果空栈情况下遇到右括号，说明缺少左括号，不匹配； 在第二步骤遍历结束时，栈不为空，说明缺少右括号，不匹配；
解决代码
建议在pycharm中打断点，以便于更好的理解
#!/use/bin/env python
# _*_ coding:utf-8 _*_
LEFT = {'(', '[', '{'} # 左括号
RIGHT = {')', ']', '}'} # 右括号
def match(expr):
"""
:param expr: 传过来的字符串
:return: 返回是否是正确的
"""
stack = [] # 创建一个栈
for brackets in expr: # 迭代传过来的所有字符串
if brackets in LEFT: # 如果当前字符在左括号内
stack.append(brackets) # 把当前左括号入栈
elif brackets in RIGHT: # 如果是右括号
if not stack or not 1
| 
注册
登录
