Python算法应用实战之栈

雨丽酱_6307

雨丽酱_6307

2018-06-02

1850人浏览

原创

栈是什么,你可以理解为一种先入后出的数据结构(first in last out),一种操作受限的线性表。下面这篇文章主要给大家介绍了python中栈的应用实战,文中给出了多个实例,需要的朋友可以参考借鉴,下面来一起看看吧。

栈(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

一大波实例

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

括号匹配

题目

Python 环境工具基础版
Python 环境工具基础版

管理 Python 项目环境,支持虚拟环境创建、依赖安装与环境诊断

下载

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

正确的格式

{()[()]},[{({})}]

错误的格式

[(]),[()),(()}

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

思路

  1. 创建一个空栈,用来存储尚未找到的左括号;

  2. 便利字符串,遇到左括号则压栈,遇到右括号则出栈一个左括号进行匹配;

  3. 在第二步骤过程中,如果空栈情况下遇到右括号,说明缺少左括号,不匹配;

  4. 在第二步骤遍历结束时,栈不为空,说明缺少右括号,不匹配;

解决代码

建议在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 <p></p><p><strong>迷宫问题</strong></p><p>题目</p><p>用一个二维数组表示一个简单的迷宫,用0表示通路,用1表示阻断,老鼠在每个点上可以移动相邻的东南西北四个点,设计一个算法,模拟老鼠走迷宫,找到从入口到出口的一条路径。</p><p>如图所示</p><p style="text-align: center"><img alt="" src="https://img.php.cn/upload/article/000/153/291/18f7ace110e7d800c44cfeac2703b351-1.png?x-oss-process=image/resize,p_40"></p><p>出去的正确线路如图中的红线所示</p><p>思路</p><ol class=" list-paddingleft-2">
<li><p>用一个栈来记录老鼠从入口到出口的路径</p></li>
<li><p>走到某点后,将该点左边压栈,并把该点值置为1,表示走过了;</p></li>
<li><p>从临近的四个点中可到达的点中任意选取一个,走到该点;</p></li>
<li><p>如果在到达某点后临近的4个点都不走,说明已经走入死胡同,此时退栈,退回一步尝试其他点;</p></li>
<li><p>反复执行第二、三、四步骤直到找到出口;</p></li>
</ol><p>解决代码</p><p class="jb51code"></p><pre class="brush:py;">#!/use/bin/env python
# _*_ coding:utf-8 _*_
def initMaze():
 """
 :return: 初始化迷宫
 """
 maze = [[0] * 7 for _ in range(5 + 2)] # 用列表解析创建一个7*7的二维数组,为了确保迷宫四周都是墙
 walls = [ # 记录了墙的位置
 (1, 3),
 (2, 1), (2, 5),
 (3, 3), (3, 4),
 (4, 2), # (4, 3), # 如果把(4, 3)点也设置为墙,那么整个迷宫是走不出去的,所以会返回一个空列表
 (5, 4)
 ]
 for i in range(7): # 把迷宫的四周设置成墙
 maze[i][0] = maze[i][-1] = 1
 maze[0][i] = maze[-1][i] = 1
 for i, j in walls: # 把所有墙的点设置为1
 maze[i][j] = 1
 return maze
"""
[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]
"""
def path(maze, start, end):
 """
 :param maze: 迷宫
 :param start: 起始点
 :param end: 结束点
 :return: 行走的每个点
 """
 i, j = start # 分解起始点的坐标
 ei, ej = end # 分解结束点的左边
 stack = [(i, j)] # 创建一个栈,并让老鼠站到起始点的位置
 maze[i][j] = 1 # 走过的路置为1
 while stack: # 栈不为空的时候继续走,否则退出
 i, j = stack[-1] # 获取当前老鼠所站的位置点
 if (i, j) == (ei, ej): break # 如果老鼠找到了出口
 for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # 左右上下
  if maze[i + di][j + dj] == 0: # 如果当前点可走
  maze[i + di][j + dj] = 1 # 把当前点置为1
  stack.append((i + di, j + dj)) # 把当前的位置添加到栈里面
  break
 else: # 如果所有的点都不可走
  stack.pop() # 退回上一步
 return stack # 如果迷宫不能走则返回空栈
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)]

后缀表达式求值

题目

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


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

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

思路

  1. 建立一个栈来存储待计算的操作数;

  2. 遍历字符串,遇到操作数则压入栈中,遇到操作符号则出栈操作数(n次),进行相应的计算,计算结果是新的操作数压回栈中,等待计算

  3. 按上述过程,遍历完整个表达式,栈中只剩下最终结果;

解决代码

#!/use/bin/env python
# _*_ coding:utf-8 _*_
operators = { # 运算符操作表
 '+': lambda op1, op2: op1 + op2,
 '-': lambda op1, op2: op1 - op2,
 '*': lambda op1, op2: op1 * op2,
 '/': lambda op1, op2: op1 / op2,
}
def evalPostfix(e):
 """
 :param e: 后缀表达式
 :return: 正常情况下栈内的第一个元素就是计算好之后的值
 """
 tokens = e.split() # 把传过来的后缀表达式切分成列表
 stack = []
 for token in tokens: # 迭代列表中的元素
 if token.isdigit(): # 如果当前元素是数字
  stack.append(int(token)) # 就追加到栈里边
 elif token in operators.keys(): # 如果当前元素是操作符
  f = operators[token] # 获取运算符操作表中对应的lambda表达式
  op2 = stack.pop() # 根据先进后出的原则,先让第二个元素出栈
  op1 = stack.pop() # 在让第一个元素出栈
  stack.append(f(op1, op2)) # 把计算的结果在放入到栈内
 return stack.pop() # 返回栈内的第一个元素
result = evalPostfix('2 3 4 * +')
print(result)
# 14

背包问题

题目

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


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

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

解决代码

#!/use/bin/env python
# _*_ coding:utf-8 _*_
def knapsack(t, w):
 """
 :param t: 背包总容量
 :param w: 物品重量列表
 :return:
 """
 n = len(w) # 可选的物品数量
 stack = [] # 创建一个栈
 k = 0 # 当前所选择的物品游标
 while stack or k  0 and k = w[k]: # 剩余空间大于等于当前物品重量
  stack.append(k) # 把物品装备背包
  t -= w[k] # 背包空间减少
  k += 1 # 继续向后找
 if t == 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]
"""

Python免费学习笔记(深入):立即使用
在学习笔记中,你将探索 Python 的核心概念和高级技巧!

相关文章

python速学教程(入门到精通)
python速学教程(入门到精通)

python怎么学习?python怎么入门?python在哪学?python怎么学才快?不用担心,这里为大家提供了python速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

python

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

80

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

2026.11.05

120

12

DBeaver安全防护教程大全
DBeaver安全防护教程大全

DBeaver安全防护专题,围绕数据库连接安全、账号密码保护和访问权限管理展开,整理SSL/TLS加密连接、SSH隧道、数据库凭据保存及证书验证等配置方法,同时介绍敏感信息保护、远程连接风险和高权限账号使用等注意事项,帮助用户提高数据库日常管理的安全性。

2026.11.05

100

12

DBeaver连接创建与配置教程
DBeaver连接创建与配置教程

本专题聚焦DBeaver数据库连接配置与管理,覆盖从新建连接、选择数据库类型到填写连接参数和验证连接的完整流程。针对MySQL、PostgreSQL、SQL Server等常见数据库,整理相应的连接设置方法,并提供驱动缺失、认证失败和连接异常等问题的排查方向。

2026.11.04

120

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程