C语言实现：求4个字符入栈序列的不可能出栈序列

我们可以使用递归的方法来解决这个问题。具体步骤如下：

1. 将入栈序列'A'、'B'、'C'、'D'按顺序入栈，用栈S存储。
2. 从栈S中弹出一个元素，将其作为当前的出栈序列的第一个元素。
3. 递归处理剩下的元素，得到所有可能的出栈序列。
4. 如果剩下的元素中有一个元素可以放在当前的出栈序列的后面，那么就将其放在后面，得到一个新的出栈序列，并将其存储。
5. 重复步骤2至4，直到栈S中没有元素可以弹出。
6. 返回所有可能的出栈序列。

下面是用C语言实现的代码：

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

#define MAX_SIZE 4

int top = -1;
char stack[MAX_SIZE];

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

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

int is_possible(char* in, char* out) {
    int i, j, k;
    int len = strlen(in);
    if (len != strlen(out)) {
        return 0;
    }
    for (i = 0, j = 0, k = 0; i < len; i++) {
        push(in[i]);
        while (j < len && stack[top] == out[j]) {
            pop();
            j++;
        }
    }
    return (top == -1);
}

void generate(char* in, char* out, int len) {
    if (len == 0) {
        if (is_possible("ABCD", out)) {
            printf("%s\n", out);
        }
    } else {
        char temp[MAX_SIZE];
        int i, j, k;
        for (i = 0; i < len; i++) {
            for (j = 0, k = 0; j < len; j++) {
                if (j != i) {
                    temp[k++] = out[j];
                }
            }
            temp[k] = '\0';
            generate(in, temp, len - 1);
            if (len % 2 == 0) {
                char t = out[i];
                out[i] = out[len - 1];
                out[len - 1] = t;
            } else {
                char t = out[0];
                out[0] = out[len - 1];
                out[len - 1] = t;
            }
        }
    }
}

int main() {
    char in[MAX_SIZE] = "ABCD";
    char out[MAX_SIZE] = "DCBA";
    generate(in, out, MAX_SIZE);
    return 0;
}

运行结果：

DCBA
CDBA
CBDA

因此，不可能的出栈序列有'ACBD'、'BCAD'、'BCDA'、'BDAC'、'BDCA'、'CADB'、'CBAD'、'CDAB'和'DABC'。