大佬帮忙看一下为什么只有20分,栈也清空了,不知道出现了什么问题

P4387 【深基15.习9】验证栈序列

Horse_in_Russia @ 2022-03-31 17:18:14

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int qe;          //询问次数

int main() {
    cin >> qe;
    while (qe--) {
        int length = 0, tmp;   //标记输入的数字长度length
        queue<int> q;   //保存输入的数字
        stack<int> s;
        cin >> length;
        int length2 = length;
        while (length--) {
            cin >> tmp;
            q.push(tmp);
        }

        while (length2--) {

            cin >> tmp;
            bool flag = 0;      //flag标志着有没有元素进去
            while (flag==0){
                flag == 0;

                //如果栈不为空且栈顶元素等于这个元素

                if (s.empty() != 1 && s.top() == tmp) {
                    s.pop();
                    flag = 1;
                }
                //如果队列不为空且队首元素等于这个元素            
                else if (q.empty() != 1 && q.front() == tmp) {
                    q.pop();
                    flag = 1;
                }
                //如果不存在就结束了,此时队列为空,且栈顶元素不等于其tmp
                else if (q.empty() == 1 && s.top() != tmp) {
                    cout << "No" << endl;
                    goto label;
                }
                //如果队列和栈都空了,说明结束了
                else if (q.empty() == 1 && s.empty() == 1) {
                    flag=1;
                }
                //如果都不是,将队列元素压入堆栈,并且比较下一个元素
                else {
                    s.push(q.front());
                    q.pop();
                }
            }

        }
        cout << "Yes" << endl;
    label:;

    //!!!!!!!!记得清空堆栈和队列
        while (s.empty() != 1) {
            s.pop();
    }
        while (q.empty() != 1) {
            q.pop();
        }

    }

    return 0;

}

by tr2020 @ 2022-06-29 16:32:27

抱歉,不会STL,不嫌弃就看我的代码吧:

#include <cstdio>

#define N 100000

int n;
int in[N], out[N], stack[N];

bool is_out()
{
    int len = 0;
    int i = 0, j = 0;
    while (i < n)
    {
        if (stack[len - 1] == out[j])
            len--, j++;
        else
        {
            while (in[i] != out[j])
                stack[len++] = in[i++];
            i++, j++;
        }
    }
    while (len)
    {
        if (stack[len - 1] != out[j])
            return 0;
        len--, j++;
    }  
    return 1;
}

int main()
{
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++)
    {
        scanf("%d", &n);
        for (int j = 0; j < n; j++)
            scanf("%d", &in[j]);
        for (int j = 0; j < n; j++)
            scanf("%d", &out[j]);
        if (is_out())
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}

|