算法｜栈的压入、弹出序列（C）

前言

大二，刚刚开始学数据结构与算法，写得不好....

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：压入栈的所有数字均不相等，并且这两个序列的长度是相等的）。
例如：
输入：1 2 3 4 5
4 3 5 1 2
输出：NO
输入：1 2 3 4 5
4 5 3 2 1
输出：YES

//
// Created by Kkoo on 2021/4/11.
//

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

typedef struct Stack {
    int data;
    int in[5];
    int out[5];
    struct Stack *next;
} Stack;


void InitStack(Stack *s, int n) {
    int i;
    Stack *p;
    for (i = 5; i >0; i--) {
        p = (Stack *) malloc(sizeof(Stack));
        p->data = i;
        p->next = s->next;
        s->next = p;
    }
}

void DisplayStack(Stack *s) {
    Stack *p = s;
    while (p->next != NULL) {
        p = p->next;
        printf("%d ", p->data);
    }
    printf("\n");
}

int check(Stack *s) {
    int i,j;
    int o = 0, top = 0;
    for (i = 1; i <= 5; i++) {
        for (j = o + 1; j <= s->out[i]; j++) {
            o = j;
            s->in[top++] = j;
            if (top > 5) {
                return 0;
            }
        }
        if (s->in[--top] != s->out[i]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int i;
    Stack *s = (Stack *) malloc(sizeof(Stack));
    InitStack(s, 5);
    DisplayStack(s);
    for (i = 1; i <= 5; i++) {
        scanf("%d", &s->out[i]);
    }
    if (check(s) == 1)
        printf("YES\n");
    else
        printf("NO\n");
    DisplayStack(s);
    for (i = 1; i <= 5; i++) {
        scanf("%d", &s->out[i]);
    }
    if (check(s) == 1)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

总结

就离谱 数据结构确实难。

作者：Kkoo

链接：https://www.pwwwp.com/

著作权归作者所有。商业转载请联系作者进行授权，非商业转载请注明出处。