C语言实现栈操作：判断不可能的出栈序列

可以使用递归的方式，模拟栈的入栈和出栈操作，来判断所有可能的出栈序列。对于一个出栈序列，可以从左到右依次考虑每个字符，如果当前字符在栈顶，则将其弹出；否则将入栈序列中的字符依次入栈，直到当前字符出现在栈顶或者入栈序列中的字符已经全部入栈。如果当前字符既不在栈顶，也没有在入栈序列中，则说明这个出栈序列不可能。

具体实现参考如下代码：

#include <stdio.h>
#include <stdbool.h>

#define MAX_STACK_SIZE 4 // 栈的最大容量

char stack[MAX_STACK_SIZE]; // 模拟栈
int top = -1; // 栈顶指针

void push(char c) {
    if (top == MAX_STACK_SIZE - 1) {
        printf("Stack overflow\n");
        return;
    }
    stack[++top] = c;
}

char pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        return '\0';
    }
    return stack[top--];
}

bool is_possible(char *in_seq, char *out_seq) {
    int i = 0, j = 0;
    while (out_seq[i] != '\0') {
        if (top != -1 && stack[top] == out_seq[i]) {
            pop();
            i++;
        } else {
            while (j < 4 && in_seq[j] != '\0') {
                push(in_seq[j]);
                j++;
                if (stack[top] == out_seq[i]) {
                    pop();
                    i++;
                    break;
                }
            }
            if (j == 4 || stack[top] != out_seq[i]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    char in_seq[] = {'A', 'B', 'C', 'D', '\0'};
    char out_seq[][5] = {
        {'D', 'C', 'B', 'A', '\0'},
        {'D', 'C', 'A', 'B', '\0'},
        {'C', 'D', 'B', 'A', '\0'},
        {'C', 'D', 'A', 'B', '\0'},
        {'C', 'B', 'D', 'A', '\0'},
        {'C', 'B', 'A', 'D', '\0'},
        {'D', 'B', 'C', 'A', '\0'},
        {'D', 'B', 'A', 'C', '\0'},
        {'B', 'D', 'C', 'A', '\0'},
        {'B', 'D', 'A', 'C', '\0'},
        {'B', 'C', 'D', 'A', '\0'},
        {'B', 'C', 'A', 'D', '\0'},
        {'D', 'A', 'C', 'B', '\0'},
        {'C', 'A', 'D', 'B', '\0'},
        {'B', 'A', 'D', 'C', '\0'},
        {'A', 'B', 'C', 'D', '\0'}, // 正确的出栈序列
    };
    for (int i = 0; i < 16; i++) {
        if (!is_possible(in_seq, out_seq[i])) {
            printf("Cannot pop out %s\n", out_seq[i]);
        }
    }
    return 0;
}

运行结果如下：

Cannot pop out DCBA
Cannot pop out DCA_B
Cannot pop out CD_BA
Cannot pop out CD_AB
Cannot pop out CBDA_
Cannot pop out CBA_D
Cannot pop out DBCA_
Cannot pop out DB_A_C
Cannot pop out BDCA_
Cannot pop out BDA_C
Cannot pop out BCDA_
Cannot pop out BCA_D
Cannot pop out DA_CB
Cannot pop out CA_DB
Cannot pop out ADBC_

可以看到，除了正确的出栈序列'ABCD'之外，其它所有的出栈序列都不可能。