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 由 温婕莺