A1051 Pop Sequence (25分)

/*
题意：
1、给一个最大M的栈，给N个数字（1...N），判断给的栈序列栈序列是否合法
2、输入，M，N，以及K组

解题：
1、模拟栈运算
(1)如果入栈元素刚好等于出栈序列当前的元素，则让栈顶元素出栈，同时把出栈序列当前等待出栈元素的标记位后移一位，
此时，如果仍相等，就持续出栈，持续后移
步骤一：初始化栈，以一个falg做标记
步骤二：从1~N枚举，如果栈内元素大于M，则为false，break
否则，反复判断current所指序列中的元素是否等于栈顶，若是，则出栈
步骤三：上述操作结束后栈空，且flag为true，则输出yes

learn &&wrong:
1、序列用的数字而不是队列更好一点，因为有下标可以记录当前的位置
2、思路：
读入T，
然后清空栈
读入输入序列到数组
循环，然后先压入一个近战，
判断大小超过栈的范围
比较并且不空，就不断弹栈

走完这个循环，然后判定了
3、从1开始，注意
4、注意呀，不断弹出是需要判断栈是否为空，不然 段错误
5、flag的判断也要判断栈是否为空
6、每次开始一定要清空栈
*/

#include <iostream>
#include <stack>
#include <string>
#include <cstdio>
using namespace std;

const int maxn = 1010;
int arr[maxn];  //保存题目给定的出栈序列
int main()
{
    int M,N,K;  //最大的数M，N个数字，以及K组
    cin>>M>>N>>K;

    //string str; //入栈序列
    stack<int> st;   //记录栈!!!,忘记int，这是模板来的

    while(K--){
        while(!st.empty()){ //栈清空
            st.pop();
        }
        for(int i = 1;i <= N;++i){  //读入数据
            scanf("%d", &arr[i]);
        }

        int current = 1;    //指向出栈序列中的待出栈元素
        bool flag = true;
        for(int i = 1;i<= N;++i){
            st.push(i); //先入栈
            if(st.size() > M){
                flag = false;   //输出错误
                break;
            }

            //栈顶元素与序列当前位置相同时
            while(!st.empty()&&st.top() == arr[current]){
                st.pop();
                current++;  //current后移
            }
        }
        if( st.empty() && flag == true){
                printf("YES\n");
            }else printf("NO\n");
    }
    return 0;
}