目 录
1. 栈的应用场景
1.1 实际应用场景
总的来说，栈的运用还是非常广泛的，在实际的编程场景中，支持文本编辑器、字处理程序、电子表格程序、绘图程序或类似的应用程序中的撤销功能，支持维护 Web 浏览器所访问过的连接的历史记录。
1.2 例题分类
常见的例题有下面四种，会依次进行讲解，本章只讲迷宫求解。
- 括号匹配：请看数据结构 03-栈的应用：括号匹配的代码实现_江南野栀子的博客-CSDN博客
- 数制转换：请看数据结构 04-栈的应用：数制转换的代码实现_江南野栀子的博客-CSDN博客
- 迷宫求解：
- 表达式求值：请看数据结构 06-栈的应用：表达式求值的代码实现_江南野栀子的博客-CSDN博客
2. 应用场景：迷宫求解
2.1 迷宫求解例题
例题参看： 1926. 迷宫中离入口最近的出口 - 力扣（LeetCode） (leetcode-cn.com)
例题内容：
给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
2.2 迷宫求解代码实现
下面是比较官方的一个代码实现，使用了 collections 中的 deque 结构。
def nearestExit(maze, entrance) :
m, n = len(maze), len(maze[0])
# 上下左右四个相邻坐标对应的行列变化量
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# 入口加入队列并修改为墙
q = deque([(entrance[0], entrance[1], 0)])
maze[entrance[0]][entrance[1]] = '+'
while q:
cx, cy, d = q.popleft()
# 遍历四个方向相邻坐标
for k in range(4):
nx = cx + dx[k]
ny = cy + dy[k]
if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == '.':
# 新坐标合法且不为墙
if nx == 0 or nx == m - 1 or ny == 0 or ny == n - 1:
# 新坐标为出口，返回距离作为答案
return d + 1
# 新坐标为空格子且不为出口，修改为墙并加入队列
maze[nx][ny] = '+'
q.append((nx, ny, d + 1))
# 不存在到出口的路径，返回 -1
return -1
文章评论