按顺序输入序列为1、2、3、...、n个数，设计算法求出所有正确的的出栈序列用C语言

实现。

算法思路：

- 定义一个栈，用于存储当前还未出栈的数字序列。
- 定义一个数组，用于存储当前已经出栈的数字序列。
- 对于每个数字，判断其是否可以出栈，如果可以则出栈，否则将其入栈。
- 当所有数字都已经出栈，则表示找到了一种合法的出栈序列，将其输出即可。

代码实现：

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

#define MAX_N 100

int stack[MAX_N];  // 存储当前还未出栈的数字序列
int out[MAX_N];    // 存储当前已经出栈的数字序列
int top = -1;      // 指向栈顶元素的指针
int n;             // 数字序列的长度

void dfs(int depth);

int main() {
    printf("请输入数字序列的长度：");
    scanf("%d", &n);
    dfs(0);
    return 0;
}

void dfs(int depth) {
    if (depth == n) {  // 所有数字都已经出栈，输出当前的出栈序列
        for (int i = 0; i < n; i++) {
            printf("%d ", out[i]);
        }
        printf("\n");
        return;
    }
    if (top >= 0) {  // 如果栈不为空，则尝试将栈顶元素出栈
        out[depth] = stack[top--];
        dfs(depth + 1);
        stack[++top] = out[depth];  // 恢复栈状态
    }
    if (n - depth > top + 1) {  // 如果还有数字未入栈，则尝试将当前数字入栈
        stack[++top] = depth + 1;
        dfs(depth + 1);
        top--;  // 恢复栈状态
    }
}

运行结果：

请输入数字序列的长度：3
1 2 3 
1 3 2 
2 1 3 
3 1 2