3.1 对一个栈的输入序列a1,a2,a3,… ,an,，称由此栈依次出栈后所得到的元素序列为栈的合法输出序列。例如，假设栈S的一个输入序列为1,2,3,4,5，则可得到多个输出序列，例如，1,2,3,4,5就是一个合法的输出序列，同理，5,4,3,2,1 和3,2,1,4,5 也分别是其合法的输出序列。分别求解下列问题： （1）判断序列1,3,4,5,2是否是合法的输出序列。 （2）对输入序列1,2,3,4,5，求出其所有的合法的输出序列(给出结果，不用写代码)。

（1）可以使用模拟栈的方式来判断一个输出序列是否合法。具体地，从1开始依次将数字入栈，每次入栈后判断栈顶元素是否等于当前输出序列中的第一个元素，如果相等则将栈顶元素出栈，并将输出序列中的第一个元素移除，直到栈为空或者栈顶元素不等于当前输出序列中的第一个元素。如果最终栈为空且输出序列也为空，则说明该输出序列是合法的。对于序列1,3,4,5,2，按照上述方法模拟栈的操作，可以得到其不是一个合法的输出序列。

（2）对于输入序列1,2,3,4,5，其所有的合法的输出序列有：

1,2,3,4,5

1,2,3,5,4

1,2,5,4,3

1,2,5,3,4

1,5,4,3,2

1,5,4,2,3

1,5,3,4,2

1,5,3,2,4

5,4,3,2,1

其中，每个输出序列中数字的顺序可以任意调整。