C++假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。

这是一个经典的栈的应用问题，可以使用递归的思路来解决。

假设当前栈中的元素为1,2,3,...,i，已经有一个出栈序列为seq，现在需要判断是否能将栈中的元素全部出栈，且出栈顺序为seq。

1. 如果栈已经为空，说明出栈序列是合法的，输出seq；
2. 如果栈不为空，分两种情况考虑：将栈顶元素出栈，或者将栈顶元素留在栈中。如果将栈顶元素出栈，则当前的出栈序列为seq + 栈顶元素，栈中的元素变为1,2,3,...,i-1；如果将栈顶元素留在栈中，则当前的出栈序列为seq，栈中的元素变为1,2,3,...,i-1,i。然后递归处理栈中的元素，直到栈为空为止。

具体实现可以参考下面的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10

void dfs(int n, int index, int *stack, int top, int *visited, int *seq) {
    if (top < 0) {
        // 栈已经为空，输出出栈序列
        for (int i = 0; i < n; i++) {
            printf("%d ", seq[i]);
        }
        printf("\n");
        return;
    }

    // 将栈顶元素出栈
    if (top >= 0) {
        seq[index] = stack[top];
        visited[stack[top]] = 1;
        dfs(n, index + 1, stack, top - 1, visited, seq);
        visited[stack[top]] = 0;
    }

    // 将栈顶元素留在栈中
    if (top >= 0) {
        int x = stack[top];
        for (int i = x - 1; i >= 1; i--) {
            if (!visited[i]) {
                stack[top + 1] = i;
                dfs(n, index, stack, top + 1, visited, seq);
            }
        }
    }
}

int main() {
    int n;
    printf("请输入 n：");
    scanf("%d", &n);

    int stack[MAX_SIZE];
    int visited[MAX_SIZE];
    int seq[MAX_SIZE];

    // 初始化栈和 visited 数组
    for (int i = 0; i < n; i++) {
        stack[i] = i + 1;
        visited[i + 1] = 0;
    }

    dfs(n, 0, stack, n - 1, visited, seq);

    return 0;
}

输入n=3时，输出结果为：

3 2 1 
3 1 2 
2 3 1 
2 1 3 
1 3 2 
1 2 3