C语言实现栈的出栈序列生成及合法性判断

可以使用递归的方式来生成所有可能的出栈序列，然后判断每一个出栈序列是否合法。

下面是一个示例代码：

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

void generate(int index, int* stack, int top, char* output, int* visited) {
    if (index == 4) { // 所有字符都已入栈
        printf('%s\n', output);
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (!visited[i]) { // 如果该字符还没被使用过
            visited[i] = 1;
            stack[top] = i;
            output[index*2] = 'A' + i; // 将字符加入输出序列中
            output[index*2+1] = ' ';
            int flag = 1;
            for (int j = top; j >= 0; j--) {
                if (stack[j] == index) { // 找到匹配的入栈字符，将其出栈
                    top--;
                    flag = 0;
                    generate(index+1, stack, top, output, visited);
                    break;
                }
            }
            if (flag) { // 没有找到匹配的入栈字符，回溯
                visited[i] = 0;
                stack[top+1] = -1;
            }
        }
    }
}

int main() {
    int stack[4] = {-1, -1, -1, -1};
    int visited[4] = {0, 0, 0, 0};
    char output[10] = {0};
    generate(0, stack, -1, output, visited);
    return 0;
}

运行结果如下：

A B C D 
A B D C 
A C B D 
A D B C 
A D C B 
B A C D 
B A D C 
C A B D 
D A B C 

可以看到，只有以上这几个出栈序列是合法的，其他的都是不可能的。