目录
一、栈
定义一个栈
栈的应用——括号匹配问题
栈的应用——迷宫问题
二、队列
自定义队列
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 None
def is_empty(self):
return len(self.stack) == 0
def 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 False
elif stack.get_top() == match[ch]:
stack.pop()
else:
return False
if stack.is_empty():
return True
else:
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 = size
self.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.size
self.queue[self.rear] = element
else:
raise IndexError("Queue is filled.")
def pop(self):
if not self.is_empty():
self.front = (self.front + 1) % self.size
return 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_path
min_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 True
for dir in dirs:
nextNode = dir(curNode[0], curNode[1])
# 如果下一个结点为0，表示有路，就把他入队
if maze[nextNode[0]][nextNode[1]] == 0:
# queue中要存三个元素，下一个结点的坐标以及其父节点在parent列表中的下标
# 此时nextNode的父节点就是parent列表的最后一个元素，所以其下标就是len(parent)-1
queue.append((nextNode[0], nextNode[1], len(parent)-1))
maze[nextNode[0]][nextNode[1]] = 2 # 标记为已经走过
# 这里不用break，因为要将所有能走的方向都走完，与深度优先搜索不同
else:
print("没有路")
return False
测试：
文章来源：https://www.toymoban.com/news/detail-405115.html
文章来源地址https://www.toymoban.com/news/detail-405115.html
到了这里，关于栈和队列——python的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
