乐趣区

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

jiezi

题目粗心：

现有容量为 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;
}
退出移动版