栈(stack)又称之为堆栈是一个特殊的有序表，其插入和删除操作都在栈顶进行操作，并且按照先进后出，后进先出的规则进行运作。

如下图所示

例如枪的弹匣，第一颗放进弹匣的子弹反而在发射出去的时候是最后一个，而最后放入弹匣的一颗子弹在打出去的时候是第一颗发射出去的。

栈的接口

如果你创建了一个栈，那么那么应该具有以下接口来进行对栈的操作

知道栈需要上述的接口后，那么在Python中，列表就类似是一个栈，提供接口如下：

Python中的栈接口使用实例：

一大波实例

在了解栈的基本概念之后，让我们再来看几个实例，以便于理解栈。

括号匹配

题目

假如表达式中允许包含三中括号 ()、 []、 {}，其嵌套顺序是任意的，例如：

正确的格式

错误的格式

编写一个函数，判断一个表达式字符串，括号匹配是否正确

思路

1. 创建一个空栈，用来存储尚未找到的左括号；
2. 便利字符串，遇到左括号则压栈，遇到右括号则出栈一个左括号进行匹配；
3. 在第二步骤过程中，如果空栈情况下遇到右括号，说明缺少左括号，不匹配；
4. 在第二步骤遍历结束时，栈不为空，说明缺少右括号，不匹配；

解决代码

建议在 pycharm中打断点，以便于更好的理解

迷宫问题

题目

用一个二维数组表示一个简单的迷宫，用0表示通路，用1表示阻断，老鼠在每个点上可以移动相邻的东南西北四个点，设计一个算法，模拟老鼠走迷宫，找到从入口到出口的一条路径。

如图所示

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

思路

1. 用一个栈来记录老鼠从入口到出口的路径
2. 走到某点后，将该点左边压栈，并把该点值置为1，表示走过了；
3. 从临近的四个点中可到达的点中任意选取一个，走到该点；
4. 如果在到达某点后临近的4个点都不走，说明已经走入死胡同，此时退栈，退回一步尝试其他点；
5. 反复执行第二、三、四步骤直到找到出口；

解决代码

后缀表达式求值

题目

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

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

思路

1. 建立一个栈来存储待计算的操作数；
2. 遍历字符串，遇到操作数则压入栈中，遇到操作符号则出栈操作数(n次)，进行相应的计算，计算结果是新的操作数压回栈中，等待计算
3. 按上述过程，遍历完整个表达式，栈中只剩下最终结果；

解决代码

背包问题

题目

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

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

解决代码

最后，想学习Python的小伙伴们！

请关注+私信回复：“学习”就可以拿到一份我为大家准备的Python学习资料！

pytyhon学习资料

python学习资料