代码收藏家 Python-迷宫问题-栈和队列的应用
大一pthon学习算法结构——迷宫问题&-NEU-Python汇报作业：
素材来源于：清华计算机博士带你学习Python算法+数据结构_哔哩哔哩_bilibili
栈(Stack)：
栈（stack）是一种特殊的线性表，它的特点是仅在表的一端进行插入和删除操作，这一端被称为栈顶，而另一端则称为栈底。栈的基本操作包括入栈（push）和出栈（pop），遵循后进先出（LIFO，Last In First Out）的原则。
栈的基本概念
栈的操作限制使得只有最后插入的元素才能被访问和移除，这种结构在很多算法和系统功能中非常有用，比如在递归、函数调用、回溯算法等场景中。栈顶通常位于表尾，而栈底则位于表头。当栈顶指针与栈底指针相同时，表示栈为空。
栈的存储结构
栈可以用数组实现，也可以用链表实现。使用数组实现的栈称为顺序栈，它通过一个连续的地址空间来存储元素，并通过一个栈顶指针来管理元素的添加和移除。链表实现的栈则称为链栈，它通过节点的链接来管理数据，每个节点包含数据和指向下一个节点的指针。
栈的基本操作
初始化（InitStack）：创建一个空栈。例如在Python中可以如此
判断栈空（StackEmpty）：检查栈是否为空。
判断栈满（IsFull）：检查栈是否已满。
入栈（Push）：在栈顶添加一个元素。
出栈（Pop）：移除栈顶元素并返回它。
获取栈顶元素（GetTop）：返回栈顶元素而不移除它。
清空栈（ClearStack）：移除栈中所有元素。
销毁栈（DestroyStack）：释放栈占用的内存资源。
栈的长度（StackLength）：返回栈中元素的数量。
遍历栈（StackTraverse）：从栈顶到栈底输出栈中的每个元素。
class stack(size):
def __init__(self):
self.stack = []
def is_empty(self):
return len(self.stack)==0
def is_full(self,size):
self.size = size
return len(self.stack)==size
def push(self,element):
self.stack.append(element):
def pop(self):
self.stack.pop()
def get_top(self):
if len(self.stack)>0:
return self.stack[-1]
else:
return None
def clear_stack(self):
self.stack.clear()
def traverse_stack(self):
for i in range(len(stack)-1:-1:-1):
print(i,end=' ')栈的应用-迷宫问题——深度优先搜索
一条路走到黑
栈的后进先出特性使其在处理具有最后一个进入先处理特性的数据结构时非常有效。例如，在迷宫问题中运用栈的存储结构模式来存储节点可以实现高效操作栈的实现和操作通常涉及对内存的有效管理，以及对栈顶指针的精确控制。在其他应用中，栈的实现需要考虑到可能的溢出和下溢情况，并采取相应的措施来处理这些异常情况，但在本实验中不用考虑
给出一个二位列表表示迷宫，0表示通道，1表示围墙
maze = [
[1,1,1,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,1,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]
思路：
核心思想就是一条路走到黑，先传入原始坐标,然后遍历四个方向，从一个节点开始，任意找下一个能走的点，当找到不能走的点时，退回上一个寻找是否有其他方向的点
遍历方向：
我们可以采用一个二维列表封装四个匿名函数来实现四个方向的值，再用for遍历即可完成查找Eg：
dirs = [
lambda x,y:(x-1,y), #这是一个匿名函数更加简洁，方便
lambda x,y:(x,y+1), #遍历这个列表四次就相当于
lambda x,y:(x+1,y), #检索了四个方向
lambda x,y:(x,y-1) #依次是上右下左
]
路径问题:
默认是上右下左顺时针依次遍历，找到一个能够走的点就直接走，当遇到墙时让最后那一个节点出栈并且标记走过的路和方向，可以用非0，1的数字来表示走过的路径，这样退回的上一节点时可以直接遍历其他的方向的节点
如图先走一条路：
遇到墙或者走过的路了那么回到maze[3][2]进行其他方向的遍历(列表最左上角：maze[0][0])
遍历之后在走依次类推就得到了一下路线:
用栈解决迷宫问题完整代码：
#深度优先搜索顾名思义就是一条路走到黑
maze = [
[1,1,1,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,1,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]
]
#默认左上角（0，0），右下角为（8，8）
#用来检索四个方向:x-1,y;x+1,y;x,y-1;x,y+1
dirs = [
lambda x,y:(x+1,y),
lambda x,y:(x-1,y),
lambda x,y:(x,y+1),
lambda x,y:(x,y-1),
#用lanmbda匿名函数表达式能够使程序更加简洁因为他只有一行
#在编程中使用lambda表达式作为列表的元素进行遍历操作冒号后面表示返回的值
]
def maze_path(x1,y1,x2,y2):
stack = []
stack.append((x1,y1))
while(len(stack)>0):
curNode = stack[-1]#当前节点
if curNode [0] == x2 and curNode[1]== y2:
#走到终点了
print('The path is : ')
for i in stack:
print(i,end = ',')
return True
#四个方向:x-1,y;x+1,y;x,y-1;x,y+1
for dir in dirs:
nextNode = dir(curNode[0],curNode[1])
#如果下一个节点能走
if maze[nextNode[0]][nextNode[1]]== 0:
stack.append(nextNode)
maze[nextNode[0]][nextNode[1]]=2
#用来标记已经走过这里了所以到时候不在走
break
#break 找到了可以走了
else:#四个方向都走不了了回退
maze[nextNode[0]][nextNode[1]]=2
stack.pop()
else:
print('No path!')
return False
maze_path(1,1,8,8)#需要进行运行函数操作输出
双向队列(Dequeue):
双向队列基本概念：
基于本演示用的双向队列的存储数据方式，简要介绍双向队列,双向队列（Deque，全名Double Ended Queue）是一种具有两个指针的线性表，允许从两端都可以进行插入和删除操作即双向队列可以在任意一端进行元素的插入和删除操作，而单向队列只能在一端进行操作。
双向队列四种基本操作：
可以用python中collections库来引用deque()来定义一个双向队列
from collections import deque
#引入collections库
double_end_queue = deque()
#定义一个双向队列double_end_queue 双向队列可以看作是一个特殊的队列，它兼具了栈和队列的特点。
栈是一种后进先出(LIFO)的数据结构，只允许在一端进行插入和删除操作；而队列是一种先进先出(FIFO)的数据结构，只允许在一端插入，在另一端删除。而双向队列则可以同时实现这两种功能，既可用于队列，也可用于栈，所以称为“双向”队列。
双向队列应用-迷宫问题——广度优先搜索:
所有路全都要
思路：
用队列对迷宫路径进行搜索是一种广度优先搜索，可以把搜索比喻成流水一样，每一次流经相同的长度，总有一条支流会率先到达终点，那么我们就可以把这一条支流看作时最优路径除非迷宫走不出去.也即是从一个节点开始，寻找所有能继续走的点，继续不断寻找，直到找到出口,并且使用队列在存储当前正在考虑的节点
如图片演示：
最后有一条支流先到达终点所以这就是最短路径
用队列来存储模式就像下列表一样：
最开始1在队列里，2进队，然后 2出队，3进队，往下，4，5进队，3出队；往下7，8，9进队4，5出队依次类推，由于队列用来存储考虑节点位置，那么原来的节点位置无从所知所以在求最短路径时需要三维的表，前两个用来表示节点，最后一个表示他的来源
存储最短路径：
由于采用双向队列的存储模式，每一次既在出队也有进队，所以我们需要定义一个三维列表，前面两个参数用来存储节点的二维坐标，最后那个参数代表指向他的由来的节点位置
遍历操作：
dirs = [
lambda x,y:(x+1,y),
lambda x,y:(x-1,y),
lambda x,y:(x,y-1),
lambda x,y:(x,y+1)
}
for dir in dirs:
nextNode = dir(curNode[0],curNode[1])
if maze[nextNode[0]][nextNode[1]]==0:
queue.append((nextNode[0],nextNode[1],len(path)-1))
maze[nextNode[0]][nextNode[1]] = 2
#此处与栈的遍历不同之处在于此时没有break跳出循环
#因为需要所有方向都遍历源码：
from collections import deque
maze = [
[1,1,1,1,1,1,1,1,1,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,0,0,0,1,0,1],
[1,0,0,0,0,1,1,0,0,1],
[1,0,1,1,1,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,1],
[1,0,1,0,0,0,1,0,0,1],
[1,0,1,1,1,0,1,1,0,1],
[1,1,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]
]
dirs = [
lambda x,y:(x+1,y),
lambda x,y:(x-1,y),
lambda x,y:(x,y-1),
lambda x,y:(x,y+1),
#用lanmbda匿名函数表达式能够使程序更加简洁因为他只有一行
#在编程中使用lambda表达式作为列表的元素进行遍历操作冒号后面表示返回的值
]
def print_r(path):
curNode = path[-1]#path最后哪个值就是终点
realpath = []
while curNode[2] != -1:
realpath.append(curNode[0:2])#用切片拿到前两个参数就是坐标
curNode = path[curNode[2]]
realpath.append(curNode[0:2])
realpath.reverse()#由于是从后往前取的所以路径是从后往前的因此还要倒一下
for node in realpath:
print(node)
def maze_path_queue(x1,y1,x2,y2):
queue = deque()#创建一个双向列表
queue.append((x1,y1,-1))#传入的是一个三维的列表当心不是值,然后我们把第一个位置为-1，
path = []
while len(queue)>0:
curNode = queue.popleft()#队首出队
path.append(curNode)
#path 是用来最后来索引路线的
if curNode[0]==x2 and curNode[1] == y2:
print_r(path)
return True
for dir in dirs:
nextNode = dir(curNode[0],curNode[1])
if maze[nextNode[0]][nextNode[1]]==0:#如果能走的话我们就让他进队
queue.append((nextNode[0],nextNode[1],len(path)-1))
#是谁的坐标让nextNode进来的肯定是curNode把他带来的而curNode是path里面最后一个元素
#由于我while刚刚才加了curNode所以curNode位置是len(path)-1
maze[nextNode[0]][nextNode[1]] = 2
maze_path_queue(1,1,8,8)
作者：何等样仁
