璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:luogup4387
problems
名称验证栈序列
题目编号P4387
题目链接luogu.com.cn/…
来源Luogu
算法分类
难易程度容易

验证栈序列

想法

枚举入栈序列,将元素加入栈中,再根据出栈序列判断栈顶元素能否出栈,直至栈顶元素与出栈元素不符。再让后续元素入栈。

如果入栈序列枚举完毕,但是栈中依旧有元素,说明不符,反之。

代码实现

#include<iostream>
using namespace std;
 
int line[100010], s[100010], target[100010], top;
 
int main()
{
	int T, n;
	cin >> T;
	while(T--)
	{
		top = 0;
		cin >> n;
		for (int i = 0; i < n; ++i)
			cin >> line[i];
		for (int i = 0; i < n; ++i)
			cin >> target[i];
 
		int iter = 0;
		for (int i = 0; i < n; ++i) {
			s[++top] = line[i];
			while(top > 0 && s[top] == target[iter])
			{
				iter++;
				top--;
			}
		}
		if(top == 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
 
	return 0;
}
/app/www/public/data/pages/icpc/problems/luogup4387.txt · 最后更改: 2024/01/30 12:10 由 温婕莺