Python算法应用实战之栈详解(python算法怎么用)

推荐整理分享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表示阻断，老鼠在每个点上可以移动相邻的东南西北四个点，设计一个算法，模拟老鼠走迷宫，找到从入口到出口的一条路径。

如图所示

出去的正确线路如图中的红线所示

思路

解决代码

后缀表达式求值

题目

计算一个表达式时，编译器通常使用后缀表达式，这种表达式不需要括号：

中缀表达式 后缀表达式 2 + 3 * 4 2 3 4 * + ( 1 + 2 ) * ( 6 / 3 ) + 2 1 2 + 6 3 / * 2 + / ( 3 * ( 1 + 2 ) ) 3 1 2 + * /

编写程序实现后缀表达式求值函数。

思路

解决代码

背包问题

题目

有一个背包能装kg的物品，现在有6件物品分别为：

物品名称 重量 物品0 1kg 物品1 8kg 物品2 4kg 物品3 3kg 物品4 5kg 物品5 2kg

编写找出所有能将背包装满的解，如物品1+物品5。

解决代码

总结