1) 假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。算法如何实现

这个问题可以使用经典的递归算法来实现。首先，如果栈中只有一个数，那么它的所有出栈序列只有一个，就是这个数本身。否则，我们可以把栈分为两部分：第一个数和剩下的数。

假设我们已经得到了剩下的数的所有出栈序列，现在我们要考虑如何插入第一个数。显然，第一个数可以插入到任何一个出栈序列的前面或中间，每一种插入方式都会得到一个新的出栈序列。因此，我们可以将第一个数插入到每一个剩余序列的每一个位置中，得到新的出栈序列。

接下来，我们可以用递归的方式，将后面的元素依次取出，然后对于每个取出的元素，重复上述过程，得到一个新的出栈序列。最终，我们就可以得到所有可能的出栈序列。

具体实现的过程中，我们可以使用一个栈来保存当前剩余的元素，另外一个栈来保存已经取出的元素，然后递归调用求解函数。在递归函数中，我们首先检查当前剩余元素的个数，如果只有一个，那么我们可以直接将它加入到已取出元素的栈中，然后将得到的出栈序列加入到结果列表中。否则，我们可以从剩余元素中取出一个元素，将其加入到已取出元素的栈中，对于剩余的元素，递归调用求解函数，得到这些元素的所有可能的出栈序列。然后，我们可以将当前取出的元素弹出已取出元素的栈中，再继续考虑下一个元素。

最终，我们可以得到所有可能的出栈序列，每个序列都是一个整数列表。有一个例子实现如下：

def get_all_pop_sequences(stack):
    if len(stack) == 1:
        return [stack]
    else:
        res = []
        for i in range(len(stack)):
            num = stack.pop(i)
            sub_seqs = get_all_pop_sequences(stack)
            for sub_seq in sub_seqs:
                res.append([num] + sub_seq)
            stack.insert(i, num)
        return res

stack = list(range(1, 6))
sequences = get_all_pop_sequences(stack)
for seq in sequences:
    print(seq)

输出结果如下：

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

这个算法的时间复杂度为 $O(n!)$，因为我们需要枚举所有可能的出栈序列。但是，实际上我们可以对这个算法进行一些优化，例如，可以使用记忆化搜索将已经求解过的子问题的结果保存下来，避免重复计算。