C语言实现栈的出栈序列验证，并打印所有不可能的出栈序列

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

#define MAX_SIZE 100

int stack[MAX_SIZE]; // 定义栈 int top = -1; // 栈顶指针

// 入栈操作 void push(int data) { if (top == MAX_SIZE - 1) { // 栈满 printf("栈已满，无法入栈。\n"); exit(1); // 异常退出程序 } stack[++top] = data; }

// 出栈操作 int pop() { if (top == -1) { // 栈空 printf("栈已空，无法出栈。\n"); exit(1); // 异常退出程序 } return stack[top--]; }

// 判断序列是否为合法的出栈序列 int is_valid_sequence(int arr[]) { int i, j, k; int temp_top = -1; int temp_stack[MAX_SIZE]; // 临时栈 for (i = 0, j = 0; i < 4; i++) { push(arr[i]); // 入栈 temp_stack[++temp_top] = arr[i]; // 同时将元素入临时栈 while (top != -1 && stack[top] == temp_stack[temp_top]) { // 如果栈顶元素等于临时栈顶元素 pop(); // 出栈 temp_top--; // 临时栈顶指针下移 } } if (top != -1) { // 如果栈不为空，说明序列不合法 return 0; } return 1; }

int main() { int arr[4] = {'A', 'B', 'C', 'D'}; int i, j, k, m; int count = 0; // 计数器，记录不合法序列的个数 int flag = 0; // 标记变量，记录是否有不合法序列 int sequence[24][4]; // 所有可能的出栈序列 int valid_sequence[24][4]; // 合法的出栈序列 int valid_sequence_count = 0; // 合法出栈序列的个数

// 生成所有可能的出栈序列
for (i = 0; i < 4; i++) {
    for (j = 0; j < 4; j++) {
        if (j == i) continue;
        for (k = 0; k < 4; k++) {
            if (k == i || k == j) continue;
            for (m = 0; m < 4; m++) {
                if (m == i || m == j || m == k) continue;
                sequence[count][0] = arr[i];
                sequence[count][1] = arr[j];
                sequence[count][2] = arr[k];
                sequence[count][3] = arr[m];
                count++;
            }
        }
    }
}

// 判断每个出栈序列是否合法
for (i = 0; i < count; i++) {
    if (!is_valid_sequence(sequence[i])) {  // 如果不合法
        flag = 1;  // 标记变量置为1
        printf("不合法的出栈序列：");
        for (j = 0; j < 4; j++) {
            printf("%c ", sequence[i][j]);
        }
        printf("\n");
    } else {  // 如果合法
        for (j = 0; j < 4; j++) {
            valid_sequence[valid_sequence_count][j] = sequence[i][j];
        }
        valid_sequence_count++;
    }
}

if (!flag) {  // 如果没有不合法序列
    printf("没有不合法的出栈序列。\n");
} else {  // 如果有不合法序列
    printf("所有合法的出栈序列：\n");
    for (i = 0; i < valid_sequence_count; i++) {
        for (j = 0; j < 4; j++) {
            printf("%c ", valid_sequence[i][j]);
        }
        printf("\n");
    }
}

return 0;

}