C++借助栈编程：（1）对输入序列1，2，3，4，5，求出所有合法的输出序列（2）设计算法判断对输入序列1，2，3，4….n，序列a1,a2,a3,…an是否是合法的输出序列

好的，我来为你解答这个问题。

对于第一个问题，我们可以采用回溯法来求解。具体思路如下：

1. 将输入序列入栈。
2. 初始化一个空栈，用于存储当前已经出栈的元素。
3. 从栈中弹出一个元素，将其加入到已出栈的元素中。
4. 如果当前已出栈的元素个数等于 n，则表示找到了一个合法的输出序列，将其存储起来。
5. 否则，将栈中剩余的元素依次尝试出栈，并进行递归搜索，直到找到所有的合法输出序列为止。

具体的 C++ 代码如下：

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

void backtrack(stack<int>& s, vector<int>& out, vector<vector<int>>& res) {
    if (out.size() == s.size()) {
        res.push_back(out);
        return;
    }
    if (!s.empty()) {
        int x = s.top();
        s.pop();
        out.push_back(x);
        backtrack(s, out, res);
        out.pop_back();
        s.push(x);
    }
    if (!out.empty()) {
        int x = out.back();
        out.pop_back();
        s.push(x);
        backtrack(s, out, res);
        out.push_back(x);
        s.pop();
    }
}

vector<vector<int>> get_valid_permutations(int n) {
    stack<int> s;
    vector<int> out;
    vector<vector<int>> res;
    for (int i = n; i >= 1; i--) {
        s.push(i);
    }
    backtrack(s, out, res);
    return res;
}

对于第二个问题，我们可以采用贪心算法来判断一个输出序列是否合法。具体思路如下：

1. 初始化一个空栈和一个指针 i，用于指示当前需要出栈的元素。
2. 依次遍历输出序列中的每个元素 j，如果栈为空或者栈顶元素不等于 j，则将输入序列中指针 i 指向的元素依次入栈，直到栈顶元素等于 j 为止。
3. 如果栈顶元素等于 j，则将其弹出栈，并将指针 i 向后移动一个位置。
4. 如果在遍历输出序列的过程中，发现栈已经为空，则说明当前输出序列不合法。

具体的 C++ 代码如下：

bool is_valid_permutation(int n, const vector<int>& a) {
    stack<int> s;
    int i = 0;
    for (int j : a) {
        if (s.empty() || s.top() != j) {
            while (i <= n && i != j) {
                s.push(i++);
            }
            if (i > n) {
                return false;
            }
            i++;
        } else {
            s.pop();
        }
    }
    return s.empty();
}

希望能够帮助到你，如果还有问题可以随时问我。