实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路： （1， 1， 1），（1， 2， 2）， （2， 2， 2），（3， 2， 3），（3， 1， 2）

首先，我们需要定义一个以链表做存储的栈类型。

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.top = None

    def is_empty(self):
        return self.top is None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def peek(self):
        if self.is_empty():
            return None
        return self.top.data

接下来，我们可以编写一个求解迷宫的非递归程序。假设迷宫用一个二维数组表示，其中0表示墙，1表示通路，起点为(1,1)，终点为(3,1)。

maze = [[0, 0, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 0, 0]]

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右下左上

def print_path(path):
    for i, j, d in path:
        print("({}, {}, {})".format(i, j, d), end=",")

def find_path(maze):
    n = len(maze)
    m = len(maze[0])
    visited = [[False] * m for _ in range(n)]
    stack = LinkedListStack()
    stack.push((1, 1, -1))  # -1表示起点
    visited[1][1] = True

    while not stack.is_empty():
        i, j, d = stack.pop()

        if i == 3 and j == 1:  # 到达终点
            path = []
            while d != -1:
                path.append((i, j, d))
                i, j, d = visited[i][j]
            path.append((1, 1, -1))
            path.reverse()
            print_path(path)
            return True

        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < m and maze[ni][nj] == 1 and not visited[ni][nj]:
                visited[ni][nj] = (i, j, di * 2 + dj)
                stack.push((ni, nj, di * 2 + dj))

    print("No path found.")
    return False

find_path(maze)  # 输出：(1, 1, 1),(1, 2, 2),(2, 2, 2),(3, 2, 3),(3, 1, 2),

在程序中，我们使用一个二维数组visited来记录每个点的父节点以及到达该点的方向。当到达终点时，我们根据visited数组回溯出路径，并输出路径上每个点的坐标和走到下一坐标的方向。