目录

一、栈

定义一个栈

栈的应用——括号匹配问题

栈的应用——迷宫问题

二、队列

自定义队列

python队列的内置模块

队列应用——打印文件后五行

队列应用——迷宫问题

---

python的数据结构与算法之栈与队列

自学视频：bilibili路飞学城清华大学博士讲解Python数据结构与算法

一、栈

定义一个栈

class Stack:def __init__(self):self.stack = []def push(self, element):self.stack.append(element)def pop(self):return self.stack.pop()def get_top(self):if len(self.stack) > 0:return self.stack[-1]   # 取栈顶元素即列表最后一个元素else:return Nonedef is_empty(self):return len(self.stack) == 0def stack_all(self):return self.stack

栈的规则：先进后出First in Last out

栈的应用——括号匹配问题

def brace_match(s):match = {'}': "{", "]": "[", ")": "("}stack = Stack()for ch in s:if ch in {"(", "{", "["}:stack.push(ch)else:if stack.is_empty():return Falseelif stack.get_top() == match[ch]:stack.pop()else:return Falseif stack.is_empty():return Trueelse:return False

测试：

栈的应用——迷宫问题

# 定义迷宫，1表示墙，不能走，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],
]
# 表示4个方向: 上(x-1,y)，右(x,y+1)，下(x+1,y)，左(x,y-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),
]
stack = []

# 深度优先搜索思想，一条道走到黑，最后的路径不一定是最短的
def maze_path(x1, y1, x2, y2):""":param x1: 起点纵坐标:param y1: 起点横坐标:param x2: 终点纵坐标:param y2: 终点横坐标:return:"""stack.append((x1, y1))  # 先将起点坐标入栈# 当栈空的时候表示没有通路，无法到达终点，所以只有当栈非空时执行循环while len(stack) > 0:# 栈顶元素就是当前走到的位置curNode = stack[-1]if curNode[0] == x2 and curNode[1] == y2:# 走到终点了for p in stack:print(p)return True# 遍历四个方向看是否能走for dir in dirs:nextNode = dir(curNode[0], curNode[1])# 如果下一个结点能走：if maze[nextNode[0]][nextNode[1]] == 0:stack.append(nextNode)    # 将nextNode入栈maze[nextNode[0]][nextNode[1]] = 2   # 将该点标记为走过break# 如果一个方向都不能走，就回退else:stack.pop()     # 栈顶出栈else:print("没有路")return False

测试：

maze_path(1, 1, 8, 8)

二、队列

自定义队列

class Queue:def __init__(self, size=100):self.size = sizeself.queue = [0 for _ in range(self.size)]self.rear = 0  # 队尾指针self.front = 0  # 队首指针def push(self, element):if not self.is_filled():self.rear = (self.rear+1) % self.sizeself.queue[self.rear] = elementelse:raise IndexError("Queue is filled.")def pop(self):if not self.is_empty():self.front = (self.front + 1) % self.sizereturn self.queue[self.front]else:raise IndexError("Queue in empty.")# 判断队空def is_empty(self):return self.rear == self.front# 判断队满def is_filled(self):return (self.rear + 1) % self.size == self.front# 测试
q = Queue(5)
for i in range(4):q.push(i)
print(q.is_filled())

python队列的内置模块

from collections import deque# 单向队列
q = deque()
q2 = deque([1, 2, 3], 5)   # 第一个参数为初始进队元素，第二个元素设置队列最大长度
# 队满之后再进队时，队首元素会自动出队
# 对尾进队
q.append(1)
# 队首出队
print(q.popleft())# 双向队列
q.appendleft(1)  # 队首进队
q.pop()  # 队尾出队

队列应用——打印文件后五行

创建一个文本文件，随便输入几行

from collections import deque
# 使用队列打印文件后五行
with open('test.txt', 'r') as f:q = deque(f, 5)# print(q)for line in q:print(line, end="")

结果：

队列应用——迷宫问题

变量定义：
 

from collections import deque# 定义迷宫，1表示墙，不能走，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],
]
# 表示4个方向: 上(x-1,y)，右(x,y+1)，下(x+1,y)，左(x,y-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 print_path(parent):curNode = parent[-1]  # 此时终点就是parent的最后一个元组min_path = []   # 存放最短路径坐标# 当遍历到起点位置时，即curNode[2]==-1，就终止循环while curNode[2] != -1:min_path.append((curNode[0], curNode[1]))# 下一个结点curNode = parent[curNode[2]]min_path.append(curNode[0:2])   # 最后还要将起点放入min_pathmin_path.reverse()   # 将列表反转，变成从起点到终点表示# 打印输出最短路径：for p in min_path:print(p)

# 广度优先搜索思想，找到的路径就是最短路径
def maze_path_queue(x1, y1, x2, y2):queue = deque()# -1代表当前结点的前一个结点（父结点）queue.append((x1, y1, -1))parent = []   # 用来存放出队的父结点while len(queue) > 0:# 先将当前节点出队并暂时用curNode保存curNode = queue.popleft()parent.append(curNode)if curNode[0] == x2 and curNode[1] == y2:# 到达终点，调用自定义的print_path函数回溯找到这条最优路径print_path(parent)return Truefor dir in dirs:nextNode = dir(curNode[0], curNode[1])# 如果下一个结点为0，表示有路，就把他入队if maze[nextNode[0]][nextNode[1]] == 0:# queue中要存三个元素，下一个结点的坐标以及其父节点在parent列表中的下标# 此时nextNode的父节点就是parent列表的最后一个元素，所以其下标就是len(parent)-1queue.append((nextNode[0], nextNode[1], len(parent)-1))maze[nextNode[0]][nextNode[1]] = 2   # 标记为已经走过# 这里不用break，因为要将所有能走的方向都走完，与深度优先搜索不同else:print("没有路")return False

测试：