关于算法-数据结构:PAT甲级1051-Pop-Sequence

题目粗心：

现有容量为M的栈,入栈序列是1到N,现有K个长度为N的出栈序列,请问是否依照固定的入栈序列是否能够通过出栈取得输出的出栈序列

算法思路：

第一个就是得看清楚题目,题目说的是入栈序列为1到N,意思是入栈的程序得依照1到N进行输出,在输出的时候能够有出栈操作。而后咱们抉择
STL库中的stack<int> s作为咱们的操作数栈,应用pop_num保留以后待比拟的出栈序列的元素(须要输出),而后在每一次的查问过程中，用isPossible记录以后查问的出栈序列是否非法，初始为true，应用push_num记录待入栈的元素(和栈顶元素没有什么关系)，接来下就是具体的比拟操作，咱们首先将栈清空，这里也能够抉择将栈的定义写在循环体外部，对于每一次输出的pop_num，如果push_num<=pop_num，阐明待出栈元素还没有入栈，得先顺次入栈所有小于等于pop_num的元素，如果栈的容量无奈退出须要入栈的元素，那么就让isPossible置为false,并且终止程序持续运行，否则就模仿入栈过程，并且出栈栈顶元素，如果push_num>pop_num，阐明待出栈元素曾经入栈，那么就只须要出栈栈顶元素，而后比拟和pop_num是否相等，如果不相等就让isPossible置为false,并且终止程序持续运行。最初在所有数字输出结束后判断isPossible，为true输入YES,否则输入NO.

留神点：

1、这里因为是应用的pop_num承受每一个待比拟的数字，所以在isPossible置为false后不能退出循环，得应用continue,并且在承受pop_num后，只有isPossible为false，就持续循环，不让程序往下执行。
2、每次比拟的时候栈得清空并且push_num每次都得置为1.

提交后果：

AC代码1：

#include<cstdio>
#include<stack>

using namespace std;

stack<int> s;

int main(){
    int M,N,K;//栈的容量，入栈序列长度，比拟的序列个数
    scanf("%d %d %d",&M,&N,&K);
    int pop_num;// 以后待比拟的出栈序列的元素 
    for(int i=0;i<K;++i){
        bool isPossible = true;
        int push_num = 1;//待入栈的元素
        if(i!=0){
            // 每次都得清空栈的元素 
            while(!s.empty()){
                s.pop();
            }
        }
        for(int j=0;j<N;++j){
            scanf("%d",&pop_num);
            if(!isPossible){
                continue;
            }
            if(push_num<=pop_num){
                if(pop_num-push_num+1>M-s.size()){
                    // 须要进栈的元素个数超过栈的残余容量 
                    isPossible = false;
                    continue;
                }
                // 栈能够容入须要入栈的元素 
                while(push_num<=pop_num){
                    // 入栈 
                    s.push(push_num);
                    ++push_num;
                }
                // 出栈 
                s.pop();
                // 这里不必判断出栈的元素和出栈序列中须要比拟的元素是否相等 
            }else {
                //出栈
                int top_num = s.top();
                s.pop();
                if(top_num!=pop_num){
                    isPossible = false;
                    continue;
                }
            }
        }
        if(isPossible){
            printf("YES\n");
        }else{
            printf("NO\n");;
        }
    } 
    return 0; 
}

下面的写法必须得接管结束所有的pop_num，否则程序会进行，这里给出另外一种办法，应用数组先接管所有待比拟的出栈序列，而后在进行查问。

AC代码2：

#include<cstdio>
#include<stack>
#include<cstring>

using namespace std;

int main(){
    int M,N,K;//栈的容量,入栈序列长度,须要判断的序列个数
    scanf("%d %d %d",&M,&N,&K);
    int num;
    for(int i=0;i<K;++i){
        bool flag = true;//判断以后序列是否能够输入
        stack<int> s;
        int num = 1;//以后须要入栈的元素
        int a[N];
        for(int j=0;j<N;++j){
            scanf("%d",&a[j]);
        } 
        for(int j=0;j<N;++j){
            int temp = a[j];//以后须要出栈的元素
            while(num<=temp){//将num到temp的元素全副进栈 
                s.push(num);
                if(s.size()>M){
                    flag = false;
                    break;
                }
                ++num;
            } 
            if(!flag) break;//栈溢出 
            int k = s.top();
            if(k!=temp){
                flag = false;//num>temp并且栈顶元素和出栈元素不同 
                break;
            }else{
                s.pop();//雷同,则出栈 
            }
        }
        if(!flag){
            printf("NO\n");
        }else{
            printf("YES\n");
        }    
    } 
    return 0;
}