栈:即先进先出

class Stack:
    def __init__(self,size=10):
        self.size = size
        self.queue = [0 for i in range(size)]

    def push(self,item):
        if self.is_filled():
            self.queue.append(item)
        else:
            raise IndexError("存储失败")
    def pop(self):
        if self.is_empty():

            self.queue.pop()
        else:
            raise IndexError("删除失败")
    def is_filled(self):
        return len(self.queue) > self.size
    def is_empty(self):
        return len(self.queue) == 0

队列:即一边出一边进

class Queue:
    def __init__(self,size=10):
        self.size = size
        self.rear = 0    #队尾指针
        self.front = 0 #队首指针
        self.queue = [0 for i in range(size)]

    def push(self,eleme 
        if not self.is_filled():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = element
        else:
            raise IndexError("The 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("The Queue is empty")

    def is_empty(self):
        return self.front == self.rear

    def is_filled(self):
        return (self.rear + 1) % self.size == self.front

q = Queue(5)
for i in range(4):
    q.push(i)
for i in range(5):
    print(q.pop())

迷宫问题:

栈_迷宫:利用栈的原理解决迷宫问题,原理是像一个方向进行通过,如果此路不通将退回上一部然后再寻找另外解,直至可以找到终点or返回到最初值即没有答案

maze = [                            #迷宫图,0即可以走的路,1即墙
    [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]

]
dics = [                            #利用lambda表达式实现迷宫的走路,优先级是上右下左
    lambda x,y:(x,y+1),
    lambda x,y:(x+1,y),
    lambda x,y:(x,y-1),
    lambda x,y:(x-1,y),
]
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:
            for i in stack:
                print(i)
            return True

        for dic in dics:
            nextNode = dic(curNode[0],curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = 2        #走过的路标记为2
                break
        else:
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()
    else:
        print("此迷宫没有路")
        return False

maze_path(1,1,1,8)

队列迷宫:此解题方法不同于栈,此方法在到达一个地点时,会同时想周围方向进行探索,此方法不仅会找到解题方法,并且是最优解

from collections import deque        #python内置队列库
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]

]
dics = [
    lambda x,y:(x,y+1),
    lambda x,y:(x+1,y),
    lambda x,y:(x,y-1),
    lambda x,y:(x-1,y),
]
def print_r(path):
    realpath = []
    curNode = path[-1]
    while curNode[2] != -1:
        realpath.append((curNode[0],curNode[1]))
        curNode = path[curNode[2]]        #利用之前的标记下标来寻找上一步
    realpath.append(curNode[0:2])
    realpath.reverse()
    for i in realpath:
        print(i)


def maze_path_queue(x1,y1,x2,y2):
    queue = deque()
    queue.append((x1,y1,-1))        #-1是起点标记
    path = []                        #用来存储此方法探索过的路
    while len(queue) > 0:
        curNode = queue.pop()
        path.append(curNode)
        if curNode[0] == x2 and curNode[1] == y2:
            print_r(path)
            return True
        for dic in dics:
            nextNode = dic(curNode[0],curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                maze[nextNode[0]][nextNode[1]] = 2
                queue.append((nextNode[0],nextNode[1],len(path)-1))    #存储队列,但是最后一个参数是用来标记路径列表path的下标
    else:
        print("没有路")
        return False

maze_path_queue(1,1,1,8)

链表:上一个数据的头/尾标记了下一个数据

class Node:                        #模拟实现列表
    def __init__(self,item):
        self.item = item
        self.next = None


def linklist_head(li):  #头插法


    head = Node(li[0])
    for i in li[1:]:
        node = Node(i)
        node.next = head
        head = node
    return head

def linlist_tail(li):   #尾插法
    head = Node(li[0])
    tail = head
    for i in li[1:]:
        node = Node(i)
        tail.next = node
        tail = node
    return head

def linklist_print(li):
    while li:
        print(li.item)
        li = li.next


li = linlist_tail([1,2,3,4,5])
linklist_print(li)





li = [1,2,3,4,5]