02-线性结构4 Pop Sequence

Given a stack which can keep $M$ numbers at most. Push $N$ numbers in the order of $1, 2, 3, ..., N$ and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if $M$ is 5 and $N$ is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): $M$ (the maximum capacity of the stack), $N$ (the length of push sequence), and $K$ (the number of pop sequences to be checked). Then $K$ lines follow, each contains a pop sequence of $N$ numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

My Code

#include<stdio.h>
#include<stdbool.h>
#define ERROR -1
typedef int ElementType;
typedef struct SNode *PtrToSNode;
struct SNode{
    ElementType Data;
    PtrToSNode Next;
}; 
typedef PtrToSNode Stack;
Stack CreateStack(){
    Stack S;
    S = malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}
bool IsEmpty(Stack S){
    return (S->Next==NULL);
}
void Push(Stack S,ElementType x){
    Stack tmp;
    tmp = malloc(sizeof(struct SNode));
    tmp->Data = x;
    tmp->Next = S->Next;
    S->Next = tmp;
}
ElementType Pop(Stack S){
    Stack tmp;
    ElementType EleTmp;
    if(IsEmpty(S)){
        return ERROR;
    }
    tmp = S->Next;
    EleTmp = tmp->Data;
    S->Next = tmp->Next;
    free(tmp);
    return EleTmp;
}
int main()
{
    int m,n,k,i,j,count1,count2,tag=0;
    scanf("%d %d %d",&m,&n,&k);
    int link[k][n];
    for(i=0;i<k;i++){
        for(j=0;j<n;j++) scanf("%d",&link[i][j]);
    }
    Stack S=CreateStack();
    for(i=0;i<k;i++){
        count2=0;count1=0;
        for(j=1;j<=n+1;j++){
            tag = 0;
            if(j<=link[i][count2] && ++count1<=m) Push(S,j);
            while(j>link[i][count2]){
                if(Pop(S)!=link[i][count2]) break;
                count2++;count1--;
                tag = 1;
            }
            if(tag==1) j--;
        }
        if(count2==n) printf("YES");
        else printf("NO");
        if(i!=k-1) printf("\n");
        S->Next=NULL;
    }
    return 0;
}

程序其实很短，如果不考虑堆栈的实现的话，另外刚开始做的时候没有考虑到入栈元素个数超过限制非法，用了链式栈，应该用数组栈的，为了补救，在主程序中设置了计数参数count1。另外的，这样比较简单的程序，我却因为很多小错误一直报错，我奔溃了，我像个睿智。