位置: 编程技术 - 正文
Python算法应用实战之栈详解(python算法怎么用)
编辑：rootadmin推荐整理分享Python算法应用实战之栈详解(python算法怎么用)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词:python算法基础,python的算法,python算法研究,python算法基础,python算法案例,python算法基础,python算法基础,python算法基础,内容如对您有帮助，希望把文章链接给更多的朋友！
栈(stack)
栈又称之为堆栈是一个特殊的有序表，其插入和删除操作都在栈顶进行操作，并且按照先进后出，后进先出的规则进行运作。
如下图所示
例如枪的弹匣，第一颗放进弹匣的子弹反而在发射出去的时候是最后一个，而最后放入弹匣的一颗子弹在打出去的时候是第一颗发射出去的。
栈的接口
如果你创建了一个栈，那么那么应该具有以下接口来进行对栈的操作
接口 描述 push() 入栈 pop() 出栈 isEmpty() 判断是否为空栈 length() 获取栈的长度 getTop() 取栈顶的元素，元素不出栈
知道栈需要上述的接口后，那么在Python中，列表就类似是一个栈，提供接口如下：
操作 描述 s = [] 创建一个栈 s.append(x) 往栈内添加一个元素 s.pop() 在栈内删除一个元素 not s 判断是否为空栈 len(s) 获取栈内元素的数量 s[-1] 获取栈顶的元素
Python中的栈接口使用实例：
一大波实例
在了解栈的基本概念之后，让我们再来看几个实例，以便于理解栈。
括号匹配
题目
假如表达式中允许包含三中括号()、[]、{}，其嵌套顺序是任意的，例如：
正确的格式
错误的格式
编写一个函数，判断一个表达式字符串，括号匹配是否正确
思路
创建一个空栈，用来存储尚未找到的左括号； 便利字符串，遇到左括号则压栈，遇到右括号则出栈一个左括号进行匹配； 在第二步骤过程中，如果空栈情况下遇到右括号，说明缺少左括号，不匹配； 在第二步骤遍历结束时，栈不为空，说明缺少右括号，不匹配；
解决代码
建议在pycharm中打断点，以便于更好的理解
迷宫问题
题目
用一个二维数组表示一个简单的迷宫，用0表示通路，用1表示阻断，老鼠在每个点上可以移动相邻的东南西北四个点，设计一个算法，模拟老鼠走迷宫，找到从入口到出口的一条路径。
如图所示
出去的正确线路如图中的红线所示
思路
用一个栈来记录老鼠从入口到出口的路径 走到某点后，将该点左边压栈，并把该点值置为1，表示走过了； 从临近的四个点中可到达的点中任意选取一个，走到该点； 如果在到达某点后临近的4个点都不走，说明已经走入死胡同，此时退栈，退回一步尝试其他点； 反复执行第二、三、四步骤直到找到出口；解决代码
后缀表达式求值
题目
计算一个表达式时，编译器通常使用后缀表达式，这种表达式不需要括号：
中缀表达式 后缀表达式 2 + 3 * 4 2 3 4 * + ( 1 + 2 ) * ( 6 / 3 ) + 2 1 2 + 6 3 / * 2 + / ( 3 * ( 1 + 2 ) ) 3 1 2 + * /
编写程序实现后缀表达式求值函数。
思路
建立一个栈来存储待计算的操作数； 遍历字符串，遇到操作数则压入栈中，遇到操作符号则出栈操作数(n次)，进行相应的计算，计算结果是新的操作数压回栈中，等待计算 按上述过程，遍历完整个表达式，栈中只剩下最终结果；解决代码
背包问题
题目
有一个背包能装kg的物品，现在有6件物品分别为：
物品名称 重量 物品0 1kg 物品1 8kg 物品2 4kg 物品3 3kg 物品4 5kg 物品5 2kg
编写找出所有能将背包装满的解，如物品1+物品5。
解决代码
总结
标签: python算法怎么用
本文链接地址:https://www.jiuchutong.com/biancheng/380033.html 转载请保留说明！
