【洛谷 P4387】【深基15.习9】验证栈序列 题解（模拟+栈+队列）

本文主要是介绍【洛谷 P4387】【深基15.习9】验证栈序列 题解（模拟+栈+队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 $n(n\le 100000)$。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据。

输入格式

第一行一个整数 $q$，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

样例 #1

样例输入 #1

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

样例输出 #1

Yes
No

---

思路

首先定义一个栈s1和两个队列pu、po。其中，s1用于模拟栈操作，pu用于存储输入的原始序列，po用于存储目标序列。

在主函数main中，首先输入一个数q，表示接下来有q组数据需要处理。对于每一组数据，首先输入一个数n，表示序列的长度。然后清空栈和两个队列，以便处理新的一组数据。

接下来，输入n个数，这些数构成了原始序列，按照输入的顺序依次添加到队列pu中。再输入n个数，这些数构成了目标序列，按照输入的顺序依次添加到队列po中。

然后，开始模拟栈操作。对于原始序列中的每一个元素，都执行入栈操作，然后检查栈顶元素是否等于目标序列的第一个元素，如果相等，就同时执行出栈操作和删除目标序列的第一个元素。这个过程一直持续到原始序列中的所有元素都被处理完。

最后，如果栈为空，表示原始序列可以通过一系列的入栈和出栈操作得到目标序列，输出"Yes"；否则，表示不能得到目标序列，输出"No"。

---

AC代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#define AUTHOR "HEX9CF"
using namespace std;stack<int> s1;
queue<int> pu, po;int main() {int q;cin >> q;while (q--) {int n;cin >> n;while (s1.size()) {s1.pop();}while (pu.size()) {pu.pop();}while (po.size()) {po.pop();}for (int i = 1; i <= n; i++) {int t;cin >> t;pu.push(t);}for (int i = 1; i <= n; i++) {int t;cin >> t;po.push(t);}for (int i = 1; i <= n; i++) {s1.push(pu.front());pu.pop();while (s1.size() && s1.top() == po.front()) {po.pop();s1.pop();}}if (s1.empty()) {cout << "Yes" << endl;} else {cout << "No" << endl;}}return 0;
}

这篇关于【洛谷 P4387】【深基15.习9】验证栈序列 题解（模拟+栈+队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---