判断序列的合法性，有人操作一下吗？

各位社友们百忙之中，抽抽空看看，谢谢。有没有铁子们提供一下思路

img

这是一道我做过的课后题，你可以参考一下我的方法自己实现着

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

#define MAX_SIZE 100 // 假设最大栈大小为100

typedef struct {
    int data[MAX_SIZE]; // 栈数组
    int top; // 栈顶指针，初始化为-1
} Stack;

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

// 入栈
void push(Stack *s, int x) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack overflow!\n");
        return;
    }
    s->data[++s->top] = x;
}

// 出栈
int pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack underflow!\n");
        return -1;
    }
    return s->data[s->top--];
}

// 判断能否用栈将 1~N 的递增序列转换为指定序列
void check(int n, int a[]) {
    Stack s;
    initStack(&s);
    int i = 1, j = 0;
    while (i <= n && j < n) {
        if (a[j] == i) { // 如果当前元素是期望的元素，则出栈
            i++;
            j++;
        } else if (s.top != -1 && s.data[s.top] == a[j]) { // 如果栈顶元素是期望的元素，则出栈
            j++;
            pop(&s);
        } else if (i <= n) { // 将当前元素入栈
            push(&s, i);
            i++;
        } else {
            break;
        }
    }
    if (j == n) { // 如果序列全部匹配，则输出操作序列
        printf("push(1)");
        for (int k = 2; k <= n; k++) {
            printf(", push(%d)", k);
            while (s.top != -1 && s.data[s.top] == k) {
                printf(", pop(%d)", pop(&s));
            }
        }
        while (s.top != -1) {
            printf(", pop(%d)", pop(&s));
        }
        printf("\n");
    } else {
        printf("impossible\n"); // 否则输出impossible
    }
}

int main() {
    int a[5] = {2, 1, 5, 4, 3};
    check(5, a); // 输出push(1), push(2), pop(2), pop(1), push(3), push(4), push(5), pop(5), pop(4), pop(3)
    int b[5] = {5, 1, 2, 3, 4};
    check(5, b); // 输出impossible
    return 0;
}



bool is_possible(int n, int* seq, int seqSize)
{
    int curr = 0;
    int* stack = (int*)malloc(sizeof(int) * n); // 动态分配存储空间
    int top = -1;

    for (int i = 0; i < seqSize; i++) {
        while (top >= 0 && stack[top] == seq[i]) { // 栈不为空且栈顶元素等于要出栈的元素
            top--; // 弹出栈顶元素
            i++; // 向右移动，考虑下一个元素
        }
        if (curr <= n && curr <= seq[i]) { // 当前元素小于等于栈顶元素
            while (curr < seq[i]) { 
                stack[++top] = curr++; // 压栈
            }
            curr++; // 下次压栈从下一个元素开始
        }
        else { // 无法得到要出栈的元素序列
            free(stack);
            return false; 
        }
    }
    free(stack);
    return true;
}
不知道你这个问题是否已经解决, 如果还没有解决的话:

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^