C++假设栈的输入序列为1、2、3、...、n，设计算法实现对给定的一个序列，判定其是否是此栈合法的输出序列。比如输入1、2、3、4、5序列，13452为合法出栈序列；15234是不合法输出序列。

算法思路：

- 创建一个辅助栈stack，用来模拟操作序列的入栈和出栈。
- 遍历给定的输出序列，依次对每个元素进行判断。
- 如果栈为空或者栈顶元素不等于当前输出序列的元素，则将1~当前元素依次入栈。
- 如果栈顶元素等于当前输出序列的元素，则将栈顶元素出栈，输出序列指针后移。
- 如果遍历完输出序列后，辅助栈为空，则说明输出序列合法，否则不合法。

算法实现：

bool is_legal_order(int n, int order[])
{
    stack<int> s;
    int i = 0, j = 1;
    while (i < n)
    {
        if (s.empty() || s.top() != order[i])
        {
            while (j <= n && j != order[i])
            {
                s.push(j);
                j++;
            }
            if (j > n) return false;
            s.push(j);
            j++;
        }
        else
        {
            s.pop();
            i++;
        }
    }
    return s.empty();
}

算法分析：

- 时间复杂度：O(n)，需要遍历一次输出序列。
- 空间复杂度：O(n)，辅助栈最多存储n个元素。