3、已知Ackermann函数定义如下： 借助链栈，实现计算Ack(m,n)的非递归算法。

Ackermann函数是一个非常特殊的函数，在计算机科学中具有很重要的意义。它的定义如下：

$$A(m,n) = \begin{cases} n+1 &\text{if } m=0 \\ A(m-1,1) &\text{if } m>0 \text{ and } n=0 \\ A(m-1,A(m,n-1)) &\text{if } m>0 \text{ and } n>0 \end{cases}$$

借助链栈，可以实现Ackermann函数的非递归计算。具体的算法如下：

1. 创建一个空栈，将参数m和n依次入栈。
2. 进入循环，每次从栈顶取出两个参数m和n。
3. 如果m=0，则将n+1入栈。
4. 如果m>0且n=0，则将m-1和1入栈。
5. 如果m>0且n>0，则将m-1和A(m,n-1)入栈。
6. 如果栈顶只剩下一个元素，则说明计算完成，将其出栈并返回结果。
7. 否则回到步骤2继续计算。

下面是Python代码实现：

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

def ackermann(m, n):
    stack = Stack()
    stack.push(m)
    stack.push(n)

    while not stack.is_empty():
        n = stack.pop()
        m = stack.pop()

        if m == 0:
            stack.push(n + 1)
        elif m > 0 and n == 0:
            stack.push(m - 1)
            stack.push(1)
        elif m > 0 and n > 0:
            stack.push(m - 1)
            stack.push(m)
            stack.push(n - 1)

        if stack.is_empty():
            return n

print(ackermann(3, 4))  # 输出结果为 125

这个算法的时间复杂度是指数级别的，因此只能用于计算较小的Ackermann数。