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

迷南。 2022-05-09 12:20 161阅读 0赞

Problem Description

给一个初始的入栈序列，其次序即为元素的入栈次序，栈顶元素可以随时出栈，每个元素只能入栈依次。输入一个入栈序列，后面依次输入多个序列，请判断这些序列是否为所给入栈序列合法的出栈序列。  
例如序列1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个出栈序列，但4，3，5，1，2就不可能是该序列的出栈序列。假设压入栈的所有数字均不相等。  
Input

第一行输入整数n(1<=n<=10000)，表示序列的长度。  
第二行输入n个整数，表示栈的压入顺序。  
第三行输入整数t（1<=t<=10）。  
后面依次输入t行，每行n个整数，表示要判断的每一个出栈序列。  
Output

对应每个测试案例输出一行，如果由初始入栈序列可以得到该出栈序列，则输出yes，否则输出no。

Sample Input

5  
1 2 3 4 5  
2  
4 5 3 2 1  
4 3 5 1 2  
Sample Output

yes  
no

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    int main()
    {
        int A[10010],B[10010];
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>A[i];
        }
        int k;
        cin>>k;
        while(k--)
        {
            for(int i=0;i<n;i++)
            {
                cin>>B[i];
            }
            stack<int>S;
            int i=0,j=0;
            while(j<n)
            {
                if(A[i]==B[j])
                {
                    j++;
                    i++;
                }
                else if(!S.empty()&&S.top()==B[j])
                {
                    j++;
                    S.pop();
                }
                else
                {
                    S.push(A[i]);
                    i++;
                }
            }
            if(S.empty())
            {
                cout<<"yes"<<endl;
            }
            else
            {
                cout<<"no"<<endl;
            }
        }
       return 0;
    }

简单来说就是重新来判一遍，如果两个数对应相等，则相当于进栈再出栈，两个坐标向后移动一位就行，如果栈顶元素等于B【j】那么栈顶出栈，j向后移。其他则进栈，i向后移。最后判空，如果是空值，则，YES，否则ON。

#include <iostream>
    #include <stack>
    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    using namespace std;
    
    int main()
    {
        int A[10001];
        int B[10001];
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&A[i]);
        }
        int t;
        scanf("%d",&t);
        while(t--)
        {
            for(int i=0;i<n;i++)
            {
                scanf("%d",&B[i]);
            }
            stack<int>mystack;
            int top1=0;
            int top2=0;
            while(top2<n)
            {
                if(A[top1]==B[top2])
                {
                    top1++;
                    top2++;
                }
                else if(!mystack.empty()&&mystack.top()==B[top2])
                {
                    mystack.pop();
                    top2++;
                }
                else
                {
                    mystack.push(A[top1]);
                    top1++;
                }
            }
            if(mystack.empty())
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
        return 0;
    }

下面是栈对象的使用：

#include<iostream>
    #include<stack>
    #include<string>
    using namespace std;
    
    int main()
    {
    
    
        //top用法
        stack<int> mystack;
        mystack.push(10);
        mystack.push(20);
        mystack.top() -= 5;
        cout << "mystack.top() is now " << mystack.top() << '\n';
    
        //size用法
        stack<int> myints;
        cout << "0. size: " << myints.size() << '\n';
        for (int i = 0; i < 5; i++) myints.push(i);
        cout << "1. size: " << myints.size() << '\n';
        myints.pop();
        cout << "2. size: " << myints.size() << '\n';
    
    
        //push和pop用法
        stack<int> mystack1;
        //将i元素压入栈
        for (int i = 0; i < 5; ++i) mystack1.push(i);
        cout << "Popping out elements...";
        while (!mystack1.empty())
        {
            cout << ' ' << mystack1.top();//取栈顶元素
            mystack1.pop();//栈顶元素出栈
        }
        cout << '\n';
    
        //emplace用法
        stack<string> myqueue1;
        myqueue1.emplace("First sentence");
        myqueue1.emplace("Second sentence");
        cout << "myqueue contains:\n";
        while (!myqueue1.empty())
        {
            cout << myqueue1.top() << '\n';
            myqueue1.pop();
        }
    
        //swap用于交换两个队列内的元素
        stack<int> foo, bar;
        foo.push(10); foo.push(20); foo.push(30);
        bar.push(111); bar.push(222);
        foo.swap(bar);
        cout << "size of foo: " << foo.size() << '\n';
        cout << "size of bar: " << bar.size() << '\n';
    
        system("pause");
        return 0;
    }

对应的输出情况：

mystack.top() is now 15
    0. size: 0
    1. size: 5
    2. size: 4
    Popping out elements... 4 3 2 1 0
    myqueue contains:
    Second sentence
    First sentence
    size of foo: 2
    size of bar: 3
    Press any key to continue . . .