基础实验3-2.4 出栈序列的合法性 (25分)--栈

 

 解题思路：

先将1入栈

     判断栈顶元素和出栈序列是否一致

     栈顶元素==出栈序列，则出栈

     栈顶元素>出栈序列，顺序有误

     栈顶元素<出栈序列，按序将不大于出栈序列的数字依次入栈，如果栈满还是小于出栈序列，则入栈顺序有误

#include <stdio.h>
#include <malloc.h>
#define ERROR -1
typedef enum {false,true
             } bool;
typedef struct {
    int *Data;
    int Top;
    int MaxSize;
}*Stack;
Stack CreateStack(int size) {
    Stack S=(Stack)malloc(sizeof(Stack));
    S->Data=(int *)malloc(sizeof(int)*size);
    S->MaxSize=size;
    S->Top=-1;
    return S;
}
bool IsEmpty(Stack S) {
    if(S->Top==-1)
        return true;
    return false;
}
bool IsFull(Stack S) {
    if(S->Top==S->MaxSize-1)
        return true;
    return false;
}
bool Push(Stack S,int x) {
    if(IsFull(S))
        return false;
    S->Data[++S->Top]=x;
    return true;
}
int Pop(Stack S) {
    if(IsEmpty(S))
        return ERROR;
    return S->Data[S->Top--];
}
int GetTop(Stack S) {
    if(IsEmpty(S))
        return ERROR;
    return S->Data[S->Top];
}
int main() {
    int size,n,m;
    scanf("%d %d %d",&size,&n,&m);
    int i,x,j;
    int k=1,flag=0;
    Stack S=CreateStack(size);
    for(j=0; j<m; j++) {
        k=1;
        Push(S,k);
        k++;
        flag=0;
        for(i=0; i<n; i++) {
            scanf("%d",&x);
            if(GetTop(S)==x) {
                Pop(S);
            } else if(GetTop(S)<x) {
                while(k<=x) {
                    if(Push(S,k))
                        k++;
                    else {
                        flag=1;
                        break;
                    }
                }
                if(!flag)
                    Pop(S);
            } else {
                flag=1;
            }
        }
        while(!IsEmpty(S)) {
            Pop(S);
        }
        if(flag)
            printf("NO
");
        else
            printf("YES
");
    }
    return 0;
}