P4387 验证栈序列

题目原文及输入/输出格式

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 n(n<100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。

AC解法

本题原理不清，解法思路来自洛谷题解。

int p, n, A[100010], B[100010];
stack<int> S; 

int main(){
	cin>>p;
	for(int k=1;k<=p;k++){
		cin>>n;
		int sum=1;
		for(int i=1;i<=n;i++) cin>>A[i];
		for(int i=1;i<=n;i++) cin>>B[i]; //输入
		
		for(int i=1;i<=n;i++){  
			S.push(A[i]);  //按顺序入栈
			while(S.top()==B[sum]){  //如果栈顶和出栈序列头相同就弹出，可能连续弹出
				S.pop();
				sum++;
				if(S.empty()) break;  //防栈空
			}
		}
		
		if(S.empty()) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		while(!S.empty()) S.pop();  //清理栈
	}
	return 0;
}