线性结构4 Pop Sequence

题面，来自PTA

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.

题目大意

题目会给出一个深度为M的堆栈，要求判断K个长度为N的序列是否可能是这个堆栈输入序列{1，2，3，……n}随机弹出的结果，比如说，M=5，N=7时，{1，2，3，4，5，6，7}就是可能的结果（注：输入1，弹出1，输入2，弹出2……输入7，弹出7）。但是{3，2，1，7，5，6，4}就不可能是弹出的结果。

算法思路

实现一个堆栈（数组或是链表均可），然后对要判断的序列的每一个数据，判断它是否等于堆栈栈顶值就行了，如果数据相同就弹出堆栈中的值并判断下一个数据，如果不同就推入堆栈输入序列{1，2，3，4，5，……}的下一个值，直到堆栈满为止。
此时若栈顶值还是和序列中的对应值不等的话，说明不可能为该堆栈的输出序列，在屏幕上打印NO即可。如果序列所有值都判断完了，就说明可能为该堆栈的输出序列，在屏幕上打印YES即可。

代码部分

#include <iostream>
#define MaxSize 1005
using namespace std;

typedef struct stackNode{
    int Data[MaxSize];
    int top;//top指示栈顶位置
} *pStack;


/**
判断栈空或满

 @param p 要判断的栈的地址
 @param length 栈长度
 @return 栈满返回1；栈不空不满返回0；栈空返回-1
 */
int isStackFullorEmpty(pStack p,int length){
    if ((p->top)>=(length-1)) return 1;
    else if(p->top<0) return -1;
    else return 0;
}

/**
 推入堆栈

 @param p 堆栈地址
 @param Data 要推入的数字
 @param length 栈长度
 @return  堆栈不满时返回True；堆栈满时返回False
 */
bool pushIntoStack(pStack p,int Data,int length){
    if(isStackFullorEmpty(p,length)<=0){
        p->top++;
        p->Data[p->top]=Data;
        return true;
    }else return false;
}

/**
 从堆栈弹出

 @param p 堆栈地址
 @return 成功弹出时返回栈顶值；堆栈空（不能弹出时）返回-1
 */
int popOutFromStack(pStack p){
    int temp;
    if (isStackFullorEmpty(p,1)>=0) {
        temp=p->Data[p->top];
        p->top--;
        return temp;
    }return -1;
}

/**
 判断指定序列是否可能为（0，1，2，……，n）的堆栈的输出结果
 核心算法

 @param s 要判断的序列数组首地址
 @param stackDepth 堆栈深度
 @param sequenceLength 序列数组的长度
 @return 可能：返回true；不可能：返回false
 */
bool isPossiblePopSequences(int *s,int stackDepth, int sequenceLength){
     /*      生成新的堆栈      */
    pStack pnode = (pStack)malloc(sizeof(struct stackNode));
    pnode->top=-1;
    int m=1;//m自加生成（1，2，3……，n）的堆栈输入序列
    
    for (int i=0; i<sequenceLength; i++) {
    /*      思路：直到堆栈满为止， 判断堆栈顶的数据是否等于判断序列的当前值。
                 如不等，则不断推入m++；如等于，则弹出并判断下一个值。       */
        while((pnode->top)+1 < stackDepth){
            if (pnode->top==-1 || pnode->Data[pnode->top]!=s[i])
            {
                pushIntoStack(pnode, m, stackDepth);
                m++;
            }else break;
        }
   /*       循环结束时说明发生了以下情形之一：堆栈满，或栈顶值与欲判断值相等。
            相等时弹出，堆栈满且不相等则返回false       */
        if(pnode->Data[pnode->top]==s[i]) popOutFromStack(pnode);
//        printf("此时,栈里有%d个元素栈顶为%d\n",pnode->top+1,pnode->Data[pnode->top]);//测试用语句
        if(pnode->top>=stackDepth-1) return false;
    }
    return true;
}

int main(void) {

    /*      读取首行输入值，从左到右分别为堆栈深度、队列长度和队列数目       */
    int stackDepth,sequenceLength,countOfSequences;
    cin>>stackDepth>>sequenceLength>>countOfSequences;
    
    int s[countOfSequences][sequenceLength];
    for(int j=0;j<countOfSequences;j++)
    {
        for (int i=0; i<sequenceLength; i++)
        {
            cin>>s[j][i];
        }

    }
    for(int i=0;i<countOfSequences;i++)
        {
        if(isPossiblePopSequences(s[i], stackDepth, sequenceLength)) cout<<"YES\n";
            else cout<<"NO\n";
        }
}

测试结果