Python数据结构与算法：栈、队列及迷宫问题的深度与广度搜索详解_队列迷宫问题ipython

在Python编程的旅程中，深入理解数据结构与算法是每个开发者不可回避的重要议题。本文将结合实际的代码示例，深入剖析栈、队列这两种经典的数据结构，并通过一个实际的迷宫问题，演示它们在深度与广度搜索中的威力。

栈的实际运用

首先，我们了解了栈的基本实现。以下是一个栈的代码示例：

# 栈的代码示例
class Stack:
    def __init__(self):
        self.stack = []
 
    def push(self, element):
        self.stack.append(element)
 
    def pop(self):
        return self.stack.pop()
 
    def gettop(self):
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None
 
    def is_empty(self):
        return len(self.stack) == 0
 
# 括号匹配的函数
def braec_math(str):
    match = {'}': '{', ']': '[', ')': '('}
    stack = Stack()
    for i in str:
        if i in {'{', '[', '('}:
            stack.push(i)
        else:
            if stack.is_empty():
                return False
            elif stack.gettop() == match[i]:
                stack.pop()
            else:
                return False
    if stack.is_empty():
        return True
    else:
        return False
'
运行
运行

上述代码不仅实现了栈的基本操作，还通过 braec_math 函数展示了栈在解决括号匹配问题中的实际应用。这种栈的特性在处理语法结构问题上非常实用。

队列的实际应用

接着，我们深入研究了队列的基本实现。以下是一个队列的代码示例：

# 队列的代码示例
class Queue:
    def __init__(self, size=100):
        self.queue = [0 for _ in range(size)]
        self.size = size
        self.front = 0
        self.rear = 0
 
    def push(self, element):
        if not self.is_empty():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = element
        else:
            raise IndexError("queue is full")
 
    def pop(self):
        if not self.is_empty():
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise IndexError("queue is empty")
 
    def is_empty(self):
        return self.rear == self.front
 
    def is_full(self):
        return (self.rear + 1) % self.size == self.front
'
运行
运行

上述代码实现了一个基本的队列，并通过迷宫问题的广度搜索函数展示了队列在解决寻路问题中的实际应用。队列的先进先出的特性使其非常适合广度搜索，寻找最短路径。

迷宫问题的深度与广度搜索

最后，我们通过实际的迷宫问题，深入探讨了深度与广度搜索的实现：

# 栈和队列的应用————迷宫问题
# 栈——深度优先搜索-回溯法
# 迷宫地图
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, y + 1),  # 右
    lambda x, y: (x + 1, y),  # 下
    lambda x, y: (x, y - 1),  # 左
]
 
def maze_path(x1, y1, x2, y2):
    stack = []  # 用于存储路径的栈
    stack.append((x1, y1))  # 将起始节点入栈
    while len(stack) > 0:
        curnode = stack[-1]  # 获取当前节点
        # 如果当前节点为终点，打印路径并返回True
        if curnode[0] == x2 and curnode[1] == y2:
            for p in stack:
                print(p, end=" ")
            return True
        # 在四个方向上尝试移动
        for dir in dirs:
            nextnode = dir(curnode[0], curnode[1])  # 获取下一个节点
            # 如果下一个节点可以移动（值为0），则将其入栈并标记为已走过
            if 0 <= nextnode[0] < len(maze) and 0 <= nextnode[1] < len(maze[0]) and maze[nextnode[0]][nextnode[1]] == 0:
                stack.append(nextnode)
                maze[nextnode[0]][nextnode[1]] = 2  # 表示已走过
                break
        else:
            # 如果四个方向都不能移动，将当前节点标记为已走过，并回退（pop）到上一个节点
            maze[curnode[0]][curnode[1]] = 2
            stack.pop()
    # 如果无法找到路径，打印提示信息并返回False
    else:
        print("没有路")
        return False
 
# 调用函数并打印路径
print(maze_path(1, 1, 8, 8))
 
# 队列——广度优选搜索
from collections import deque
 
def print_path(path):
    curnode = path[-1]  # 取路径的最后一个节点
    realpath = []  # 一个列表，用于存储实际路径的节点坐标
    while curnode[2] != -1:  # 当路径索引不为-1时，表示路径还未结束
        realpath.append(curnode[0:2])  # 将当前节点坐标添加到realpath列表中
        curnode = path[curnode[2]]  # 根据路径索引找到下一个节点
    realpath.append(curnode[0:2])  # 将起点添加到realpath列表中
    realpath.reverse()  # 将realpath列表反转，使其按照路径的顺序排列
    for node in realpath:  # 按顺序打印每个节点坐标
        print(node,end="")
 
def max_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)  # 将当前节点加入路径
        if curnode[0] == x2 and curnode[1] == y2:  # 如果当前节点是终点
            print_path(path)  # 打印路径
            return path  # 返回找到的路径
        for dir in dirs:  # 对于每个方向
            nextnode = dir(curnode[0], curnode[1])  # 计算下一个节点的坐标
            if 0 <= nextnode[0] < len(maze) and 0 <= nextnode[1] < len(maze[0]) and maze[nextnode[0]][nextnode[1]] == 0:
                # 如果下一个节点在迷宫范围内且是可通行的
                maze[nextnode[0]][nextnode[1]] = 2  # 标记节点已访问
                queue.append((nextnode[0], nextnode[1], len(path) - 1))  # 将下一个节点和路径索引加入队列
    print("没有路")  # 如果循环结束仍未找到路径，打印没有路
    return False  # 返回False表示没有找到路径
 
 
max_path_queue(1, 1, 8, 8)
'
运行
运行

在这两段代码中，我们展示了深度优先搜索和广度优先搜索在解决迷宫问题中的实际运用。深度优先搜索通过栈实现，广度优先搜索通过队列实现。这两种搜索方法分别适用于不同的场景，深度搜索适用于探索所有可能路径，而广度搜索则适用于找到最短路径。

通过本文，我们深入理解了栈和队列的基本原理，并结合迷宫问题的实例展示了它们在解决实际问题中的应用。这对于理解数据结构的实际应用场景以及算法的选择提供了有益的指导。希望本文对你的学习和实践有所帮助。