栈和队列——python

目录

一、栈

定义一个栈

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

栈的应用——迷宫问题

二、队列

自定义队列

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

测试：