基于Python 算法实战系列“栈”的干货解析
栈(stack)又称之为堆栈是一个特殊的有序表，其插入和删除操作都在栈顶进行操作，并且按照先进后出，后进先出的规则进行运作。
如下图所示
例如枪的弹匣，第一颗放进弹匣的子弹反而在发射出去的时候是最后一个，而最后放入弹匣的一颗子弹在打出去的时候是第一颗发射出去的。
栈的接口
如果你创建了一个栈，那么那么应该具有以下接口来进行对栈的操作
知道栈需要上述的接口后，那么在python中，列表就类似是一个栈，提供接口如下：
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]: nots
out[6]: true
in[7]: s.append(1)
in[8]: nots
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 = {')',']','}'}# 右括号
defmatch(expr):
:param expr:传过来的字符串
:return:返回是否是正确的
stack = []# 创建一个栈
forbrackets inexpr:# 迭代传过来的所有字符串
ifbrackets inleft:# 如果当前字符在左括号内
stack.append(brackets)# 把当前左括号入栈
elifbrackets inright:# 如果是右括号
ifnotstack ornot1 <= ord(brackets) - ord(stack[-1]) <= 2:
# 如果当前栈为空，()]
# 如果右括号减去左括号的值不是小于等于2大于等于1
returnfalse# 返回false
stack.pop()# 删除左括号
returnnotstack# 如果栈内没有值则返回true，否则返回false
result = match('[(){()}]')
print(result)
迷宫问题
题目
用一个二维数组表示一个简单的迷宫，用0表示通路，用1表示阻断，老鼠在每个点上可以移动相邻的东南西北四个点，设计一个算法，模拟老鼠走迷宫，找到从入口到出口的一条路径。
如图所示
出去的正确线路如图中的红线所示
思路
用一个栈来记录老鼠从入口到出口的路径
走到某点后，将该点左边压栈，并把该点值置为1，表示走过了；
从临近的四个点中可到达的点中任意选取一个，走到该点；
如果在到达某点后临近的4个点都不走，说明已经走入死胡同，此时退栈，退回一步尝试其他点；
反复执行第二、三、四步骤直到找到出口；
解决代码
#!/use/bin/env python
# _*_ coding:utf-8 _*_
definitmaze():
:return: 初始化迷宫
maze = [[0] * 7for_inrange(5 + 2)]# 用列表解析创建一个7*7的二维数组，为了确保迷宫四周都是墙
walls = [# 记录了墙的位置
(1,3),
(2,1),(2,5),
(3,3),(3,4),
(4,2),# (4, 3),# 如果把(4, 3)点也设置为墙，那么整个迷宫是走不出去的，所以会返回一个空列表
(5,4)
]
foriinrange(7):# 把迷宫的四周设置成墙
maze[i][0] = maze[i][-1] = 1
maze[0][i] = maze[-1][i] = 1
fori,jinwalls:# 把所有墙的点设置为1
maze[i][j] = 1
returnmaze
[1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 1, 1]
[1, 0, 0, 1, 1, 0, 1]
[1, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1]
defpath(maze,start,end):
:param maze: 迷宫
:param start: 起始点
:param end: 结束点
:return: 行走的每个点
i,j = start# 分解起始点的坐标
ei,ej = end# 分解结束点的左边
stack = [(i,j)]# 创建一个栈，并让老鼠站到起始点的位置
maze[i][j] = 1# 走过的路置为1
whilestack:# 栈不为空的时候继续走，否则退出
i,j = stack[-1]# 获取当前老鼠所站的位置点
if(i,j) == (ei,ej): break# 如果老鼠找到了出口
fordi,dj in[(0, -1),(0,1),(-1,0),(1,0)]:# 左右上下
ifmaze[i + di][j + dj] == 0:# 如果当前点可走
maze[i + di][j + dj] = 1# 把当前点置为1
stack.append((i + di,j + dj))# 把当前的位置添加到栈里面
break
else:# 如果所有的点都不可走
stack.pop()# 退回上一步
returnstack# 如果迷宫不能走则返回空栈
maze = initmaze()# 初始化迷宫
result = path(maze=maze,start=(1,1),end=(5,5))# 老鼠开始走迷宫
print(result)
# [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (4, 3), (4, 4), (4, 5), (5, 5)]
后缀表达式求值
题目
计算一个表达式时，编译器通常使用后缀表达式，这种表达式不需要括号：
编写程序实现后缀表达式求值函数。
思路
建立一个栈来存储待计算的操作数；
遍历字符串，遇到操作数则压入栈中，遇到操作符号则出栈操作数(n次)，进行相应的计算，计算结果是新的操作数压回栈中，等待计算
按上述过程，遍历完整个表达式，栈中只剩下最终结果；
解决代码
#!/use/bin/env python
# _*_ coding:utf-8 _*_
operators = {# 运算符操作表
'+': lambdaop1,op2: op1 + op2,
'-': lambdaop1,op2: op1 - op2,
'*': lambdaop1,op2: op1 * op2,
'/': lambdaop1,op2: op1 / op2,
}
defevalpostfix(e):
:param e: 后缀表达式
:return: 正常情况下栈内的第一个元素就是计算好之后的值
tokens = e.split()# 把传过来的后缀表达式切分成列表
stack = []
fortokenintokens:# 迭代列表中的元素
iftoken.isdigit():# 如果当前元素是数字
stack.append(int(token))# 就追加到栈里边
eliftokeninoperators.keys():# 如果当前元素是操作符
f = operators[token]# 获取运算符操作表中对应的lambda表达式
op2 = stack.pop()# 根据先进后出的原则，先让第二个元素出栈
op1 = stack.pop()# 在让第一个元素出栈
stack.append(f(op1,op2))# 把计算的结果在放入到栈内
returnstack.pop()# 返回栈内的第一个元素
result = evalpostfix('2 3 4 * +')
print(result)
# 14
背包问题
题目
有一个背包能装10kg的物品，现在有6件物品分别为：
编写找出所有能将背包装满的解，如物品1+物品5。
解决代码
#!/use/bin/env python
# _*_ coding:utf-8 _*_
defknapsack(t,w):
:param t: 背包总容量
:param w: 物品重量列表
:return:
n = len(w)# 可选的物品数量
stack = []# 创建一个栈
k = 0# 当前所选择的物品游标
whilestack ork < n:# 栈不为空或者k 0andk = w[k]:# 剩余空间大于等于当前物品重量
stack.append(k)# 把物品装备背包
t -= w[k]# 背包空间减少
k += 1# 继续向后找
ift == 0:# 找到了解
print(stack)
# 回退过程
k = stack.pop()# 把最后一个物品拿出来
t += w[k]# 背包总容量加上w[k]
k += 1# 装入下一个物品
knapsack(10,[1,8,4,3,5,2])
[0, 2, 3, 5]
[0, 2, 4]
[1, 5]
[3, 4, 5]
世界移动通信大会三亮点 智能产品将引领未来互联生活
基于FPGA的电子按键密码锁设计
映众GeForceRTX2080冰龙超级版上手 分量十足少幅超越公版的性能
基于嵌入式Linux系统的机车状态实时检测系统设计详解
带你看“小米”历代手机！
基于Python 算法实战系列“栈”的干货解析
详细说明功率放大器有哪些类型
再看系统级芯片SoC与传统CPU
如何写一个架构设计
Feel Three：可以满足VR体验更加身临其境的需求
基于区块链技术的V-ID验证服务介绍
利用NGINX帮助您为突发的流量高峰做好准备的方法
论高速公路隧道机电智慧管控系统的应用与研究
Google首款真无线耳机Pixel Buds 2获得无线充电认证
研华无风扇工控机推荐 工控机特点介绍
电子元器件失效原因都有哪些？
基于LabVIEW的虚拟振动测试分析系统
手机宽带等业务涨价，是5G的锅？
谷歌员工抗议为中国开发审查版搜索引擎,美国新增“NIST小型企业网络安全法”
智能能源设计说明：太阳能系统
如下图所示
例如枪的弹匣，第一颗放进弹匣的子弹反而在发射出去的时候是最后一个，而最后放入弹匣的一颗子弹在打出去的时候是第一颗发射出去的。
栈的接口
如果你创建了一个栈，那么那么应该具有以下接口来进行对栈的操作
知道栈需要上述的接口后，那么在python中，列表就类似是一个栈，提供接口如下：
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]: nots
out[6]: true
in[7]: s.append(1)
in[8]: nots
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 = {')',']','}'}# 右括号
defmatch(expr):
:param expr:传过来的字符串
:return:返回是否是正确的
stack = []# 创建一个栈
forbrackets inexpr:# 迭代传过来的所有字符串
ifbrackets inleft:# 如果当前字符在左括号内
stack.append(brackets)# 把当前左括号入栈
elifbrackets inright:# 如果是右括号
ifnotstack ornot1 <= ord(brackets) - ord(stack[-1]) <= 2:
# 如果当前栈为空，()]
# 如果右括号减去左括号的值不是小于等于2大于等于1
returnfalse# 返回false
stack.pop()# 删除左括号
returnnotstack# 如果栈内没有值则返回true，否则返回false
result = match('[(){()}]')
print(result)
迷宫问题
题目
用一个二维数组表示一个简单的迷宫，用0表示通路，用1表示阻断，老鼠在每个点上可以移动相邻的东南西北四个点，设计一个算法，模拟老鼠走迷宫，找到从入口到出口的一条路径。
如图所示
出去的正确线路如图中的红线所示
思路
用一个栈来记录老鼠从入口到出口的路径
走到某点后，将该点左边压栈，并把该点值置为1，表示走过了；
从临近的四个点中可到达的点中任意选取一个，走到该点；
如果在到达某点后临近的4个点都不走，说明已经走入死胡同，此时退栈，退回一步尝试其他点；
反复执行第二、三、四步骤直到找到出口；
解决代码
#!/use/bin/env python
# _*_ coding:utf-8 _*_
definitmaze():
:return: 初始化迷宫
maze = [[0] * 7for_inrange(5 + 2)]# 用列表解析创建一个7*7的二维数组，为了确保迷宫四周都是墙
walls = [# 记录了墙的位置
(1,3),
(2,1),(2,5),
(3,3),(3,4),
(4,2),# (4, 3),# 如果把(4, 3)点也设置为墙，那么整个迷宫是走不出去的，所以会返回一个空列表
(5,4)
]
foriinrange(7):# 把迷宫的四周设置成墙
maze[i][0] = maze[i][-1] = 1
maze[0][i] = maze[-1][i] = 1
fori,jinwalls:# 把所有墙的点设置为1
maze[i][j] = 1
returnmaze
[1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 0, 1, 1]
[1, 0, 0, 1, 1, 0, 1]
[1, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1]
defpath(maze,start,end):
:param maze: 迷宫
:param start: 起始点
:param end: 结束点
:return: 行走的每个点
i,j = start# 分解起始点的坐标
ei,ej = end# 分解结束点的左边
stack = [(i,j)]# 创建一个栈，并让老鼠站到起始点的位置
maze[i][j] = 1# 走过的路置为1
whilestack:# 栈不为空的时候继续走，否则退出
i,j = stack[-1]# 获取当前老鼠所站的位置点
if(i,j) == (ei,ej): break# 如果老鼠找到了出口
fordi,dj in[(0, -1),(0,1),(-1,0),(1,0)]:# 左右上下
ifmaze[i + di][j + dj] == 0:# 如果当前点可走
maze[i + di][j + dj] = 1# 把当前点置为1
stack.append((i + di,j + dj))# 把当前的位置添加到栈里面
break
else:# 如果所有的点都不可走
stack.pop()# 退回上一步
returnstack# 如果迷宫不能走则返回空栈
maze = initmaze()# 初始化迷宫
result = path(maze=maze,start=(1,1),end=(5,5))# 老鼠开始走迷宫
print(result)
# [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (4, 3), (4, 4), (4, 5), (5, 5)]
后缀表达式求值
题目
计算一个表达式时，编译器通常使用后缀表达式，这种表达式不需要括号：
编写程序实现后缀表达式求值函数。
思路
建立一个栈来存储待计算的操作数；
遍历字符串，遇到操作数则压入栈中，遇到操作符号则出栈操作数(n次)，进行相应的计算，计算结果是新的操作数压回栈中，等待计算
按上述过程，遍历完整个表达式，栈中只剩下最终结果；
解决代码
#!/use/bin/env python
# _*_ coding:utf-8 _*_
operators = {# 运算符操作表
'+': lambdaop1,op2: op1 + op2,
'-': lambdaop1,op2: op1 - op2,
'*': lambdaop1,op2: op1 * op2,
'/': lambdaop1,op2: op1 / op2,
}
defevalpostfix(e):
:param e: 后缀表达式
:return: 正常情况下栈内的第一个元素就是计算好之后的值
tokens = e.split()# 把传过来的后缀表达式切分成列表
stack = []
fortokenintokens:# 迭代列表中的元素
iftoken.isdigit():# 如果当前元素是数字
stack.append(int(token))# 就追加到栈里边
eliftokeninoperators.keys():# 如果当前元素是操作符
f = operators[token]# 获取运算符操作表中对应的lambda表达式
op2 = stack.pop()# 根据先进后出的原则，先让第二个元素出栈
op1 = stack.pop()# 在让第一个元素出栈
stack.append(f(op1,op2))# 把计算的结果在放入到栈内
returnstack.pop()# 返回栈内的第一个元素
result = evalpostfix('2 3 4 * +')
print(result)
# 14
背包问题
题目
有一个背包能装10kg的物品，现在有6件物品分别为：
编写找出所有能将背包装满的解，如物品1+物品5。
解决代码
#!/use/bin/env python
# _*_ coding:utf-8 _*_
defknapsack(t,w):
:param t: 背包总容量
:param w: 物品重量列表
:return:
n = len(w)# 可选的物品数量
stack = []# 创建一个栈
k = 0# 当前所选择的物品游标
whilestack ork < n:# 栈不为空或者k 0andk = w[k]:# 剩余空间大于等于当前物品重量
stack.append(k)# 把物品装备背包
t -= w[k]# 背包空间减少
k += 1# 继续向后找
ift == 0:# 找到了解
print(stack)
# 回退过程
k = stack.pop()# 把最后一个物品拿出来
t += w[k]# 背包总容量加上w[k]
k += 1# 装入下一个物品
knapsack(10,[1,8,4,3,5,2])
[0, 2, 3, 5]
[0, 2, 4]
[1, 5]
[3, 4, 5]
世界移动通信大会三亮点 智能产品将引领未来互联生活
基于FPGA的电子按键密码锁设计
映众GeForceRTX2080冰龙超级版上手 分量十足少幅超越公版的性能
基于嵌入式Linux系统的机车状态实时检测系统设计详解
带你看“小米”历代手机！
基于Python 算法实战系列“栈”的干货解析
详细说明功率放大器有哪些类型
再看系统级芯片SoC与传统CPU
如何写一个架构设计
Feel Three：可以满足VR体验更加身临其境的需求
基于区块链技术的V-ID验证服务介绍
利用NGINX帮助您为突发的流量高峰做好准备的方法
论高速公路隧道机电智慧管控系统的应用与研究
Google首款真无线耳机Pixel Buds 2获得无线充电认证
研华无风扇工控机推荐 工控机特点介绍
电子元器件失效原因都有哪些？
基于LabVIEW的虚拟振动测试分析系统
手机宽带等业务涨价，是5G的锅？
谷歌员工抗议为中国开发审查版搜索引擎,美国新增“NIST小型企业网络安全法”
智能能源设计说明：太阳能系统