(3)设计算法以判断对输入序列1，2，3,··n，序列a1，a2， a3, ...an是否是该栈的合法的输出序列(假设输出序列在数组A中)；

可以使用栈来判断输入序列和输出序列是否匹配。具体算法如下：

1. 定义一个栈，用于存储输入序列中的元素。
2. 遍历输出序列中的每个元素，记为x。
3. 如果栈顶元素等于x，则弹出栈顶元素。
4. 如果栈顶元素不等于x，则将输入序列中的元素依次入栈，直到栈顶元素等于x或者输入序列为空。
5. 如果输入序列已经为空，但是栈顶元素不等于x，则输出序列不是该栈的合法输出序列。
6. 如果输出序列中的所有元素都遍历完了，且栈为空，则输出序列是该栈的合法输出序列。

代码实现如下：

bool isLegalOutput(int A[], int n, int a[]) {
stack<int> s;
int i = , j = ;
while (j < n) {
if (!s.empty() && s.top() == a[j]) {
s.pop();
j++;
} else if (i < n) {
s.push(A[i]);
i++;
} else {
return false;
}
}
return s.empty();
}