【洛谷】验证栈序列

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 n(n≤100000)n(n\le100000)n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据。
输入格式：
第一行一个整数 q，询问次数。
接下来 q 个询问，对于每个询问：
第一行一个整数 n 表示序列长度；
第二行 n 个整数表示入栈序列；
第二行 n 个整数表示出栈序列；

输出格式：
对于每个询问输出答案。

输入样例：

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

输出样例：

Yes
No

思路：

（该题在洛谷上的部分题解用到了STL，在这里我用类写了一个顺序栈，以强化基础，也方便不熟悉STL的同学理解。）
本题给出了poped和pushed两个序列，要我们判断以pushed序列为顺序的入栈，能否达成poped序列的出栈。首先完成Sqstack（顺序栈的数据结构，不同于C语言的版本，我将该题所需的基本操作封装在了class里）。给出的两个序列，我们用两个数组来保存。然后依次遍历pushed序列。依次将其入栈。每次入栈之后判断此时的栈顶元素是否与poped序列中正在检查的元素相同，若相同，则访问该元素后将其出栈。pushed序列遍历完成后检查此时栈是否为空。如果栈为空则说明可以达成该poped序列，反之则不能达成。

代码

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

class Sqstack
{
private:
    int data[100005];
    int top;//栈顶指针
public:
    Sqstack()//构造函数
    {
        data[100005] = {0};
        top = -1;//初始栈顶指针设为-1
    }
    void pop(int &e)//出栈，并用e接住该元素
    {
        e = data[top];
        data[top--] = 0;
    }
    void push(int x)//将x入栈
    {
        data[++top] = x;
    }
    bool empty()//判空
    {
        if (top == -1)
            return true;
        else
            return false;
    }
    int gettop()//获取栈顶元素
    {
        return data[top];
    }
};

int main()
{
    int q, n;
    cin >> q;
    while (q)
    {
        q--;
        Sqstack S;
        cin >> n;
        int a[n + 1], b[n + 1], e, j = 0;//j为计数器
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
        }
        for (int i = 0; i < n; ++i)
        {
            cin >> b[i];
        }
        for (int i = 0; i < n; ++i)
        {
            S.push(a[i]);
            while (S.gettop() == b[j])//使用while而不用if是因为很有可能会出现栈顶元素与poped序列待检查元素连续相同的情况，
                                      //此时若用if则只操作一次，会导致错误。
            {
                S.pop(e);
                j++;
                if (S.empty())//若栈为空依然进行出栈操作会出错，故判空
                    break;
            }
        }
        if (S.empty())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        while (!S.empty())
            S.pop(e);   //清空栈
    }
    system("pause");
    return 0;
}

总结

熟悉栈的基本操作，依据题意即可作答。