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;
}