3334 数据结构实验之栈七：出栈序列判定

迷南。 2022-07-15 00:53 139阅读 0赞

[数据结构实验之栈七：出栈序列判定][Link 1]

#include <iostream>  
    #include <stdlib.h>  
    using namespace std;  
    
    
    int main()  
    {  
        int a[100000], b[100000], Stack[100000], n, t;  
        cin >> n;  
        for(int i = 0; i < n; i++)  
            cin >> a[i];  
        cin >> t;  
        for(int j = 0; j < t; j++)  
        {  
            int flag = 1;  
            int top = 0;  
            int i = 0, l = 0;  
            for(int i = 0; i < n; i++)  
                cin >> b[i];  
            while(i < n)  
            {  
                if(top == 0 || Stack[top - 1] < b[i])           //如果栈为空的时候   或者  栈中的元素小于此时的准备出栈的元素  
                {  
                    if(top < n)                                 //如果此时栈不为满 就把 元素a[]赋值到栈中， 也就是说  
                                                                //当此时的元素比栈顶的元素大，但是此时栈为到达预定设置的范围，就继续入栈  
                        Stack[top++] = a[l++];  
                    else                                        //如果此时的元素比栈顶的元素还大，并且此时栈已经达到预期设定的最大值，例如此时元素为1，但是栈顶元素为2  
                                                                //就不符合要求，需要判否，跳出  
                    {  
                        flag = 0;  
                        break;  
                    }  
                }  
                if(Stack[top - 1] == b[i])                      //如果此时的元素为栈顶元素， 就让栈顶下降， 并让此时出栈的元素增加  
                {  
                    top--;  
                    i++;  
                }  
                else if(Stack[top - 1] > b[i])                  //如果此时的元素小于栈顶元素， 也不能出栈  
                {  
                    flag = 0;  
                    break;  
                }  
            }  
            if(flag == 0)  
                cout << "no" << endl;  
            else  
                cout << "yes" << endl;  
        }  
        return 0;  
    }

[Link 1]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1825/pid/3334