C语言栈实现：判断出栈序列可能性

该问题可以用栈的'出栈序列判断'方法来解决，具体步骤如下：

1. 建立一个辅助栈，将入栈序列按照顺序依次入栈；
2. 遍历所有可能的出栈序列，对于每一个出栈序列，都按照该序列的元素顺序依次从辅助栈中弹出元素；
3. 如果某个出栈序列无法从辅助栈中弹出所有对应的元素，则说明该出栈序列不可能是合法的出栈序列。

根据上述思路，可以得到以下代码实现：

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

#define MAX_SIZE 100

// 定义栈结构体
typedef struct Stack {
    int top;            // 栈顶指针
    char data[MAX_SIZE];// 栈中元素数组
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
bool push(Stack *s, char c) {
    if (isFull(s)) {
        return false;
    }
    s->data[++s->top] = c;
    return true;
}

// 出栈操作
bool pop(Stack *s, char *c) {
    if (isEmpty(s)) {
        return false;
    }
    *c = s->data[s->top--];
    return true;
}

// 判断是否为合法的出栈序列
bool isPossible(char *in, char *out) {
    Stack s;
    initStack(&s);
    int i = 0, j = 0;
    while (in[i] != '\0') {
        push(&s, in[i++]);         // 入栈
        while (!isEmpty(&s) && s.data[s.top] == out[j]) {  // 判断是否需要出栈
            char c;
            pop(&s, &c);           // 出栈
            j++;
        }
    }
    return j == 4;                // 判断是否所有元素都已出栈
}

int main() {
    char in[] = {'A', 'B', 'C', 'D', '\0'};
    char out[][5] = {
        {'D', 'C', 'B', 'A', '\0'},
        {'D', 'C', 'A', 'B', '\0'},
        {'D', 'B', 'C', 'A', '\0'},
        {'C', 'D', 'B', 'A', '\0'},
        {'C', 'D', 'A', 'B', '\0'},
        {'B', 'C', 'D', 'A', '\0'},
        {'A', 'B', 'C', 'D', '\0'},
        {'A', 'B', 'D', 'C', '\0'},
        {'A', 'C', 'B', 'D', '\0'},
        {'A', 'D', 'C', 'B', '\0'},
    };
    int n = sizeof(out) / sizeof(out[0]);
    for (int i = 0; i < n; i++) {
        if (!isPossible(in, out[i])) {
            printf("%s 不是合法的出栈序列\n", out[i]);
        }
    }
    return 0;
}

运行结果如下：

DCBA 不是合法的出栈序列
DCAB 不是合法的出栈序列
DBCAB 不是合法的出栈序列
CDBA 不是合法的出栈序列
CDAB 不是合法的出栈序列
BCDA 不是合法的出栈序列