栈的典型例题（验证栈序列）以及关于模拟题的思考

给出两个序列 pushed 和 poped 两个序列&＃xff0c;其取值从 1 到 n(n\le100000)n(n≤100000)。已知入栈序列是 pushed&＃xff0c;如果出栈序列有可能是 poped&＃xff0c;则输出 Yes&＃xff0c;否则输出 No。

注意&＃xff1a;可能两个字&＃xff0c;即每次操作有可能是直接出栈&＃xff0c;还有可能是入栈再出栈

输入格式&＃xff1a;

第一行一个整数 qq&＃xff0c;询问次数。

接下来 qq 个询问&＃xff0c;对于每个询问&＃xff1a;

第一行一个整数 nn 表示序列长度&＃xff1b;

第二行 nn 个整数表示入栈序列&＃xff1b;

第二行 nn 个整数表示出栈序列&＃xff1b;

输出格式&＃xff1a;

对于每个询问输出答案。

输入样例&＃xff1a;

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

输出样例&＃xff1a;

Yes
No

1、2对题目的理解&＃xff1a;

即不是简单的全部入栈&＃xff0c;然后出栈&＃xff0c;不过&＃xff0c;只要在这个基础上&＃xff0c;验证每次数据入栈之后有没有出栈的操作即可。

2、1给出正确版本

#include
#include
using namespace std;
int main() {int n;cin >> n;while (n--) {int m;cin >> m;int * A&＃61;new int[m&＃43;1];//数组要预先设定大小&＃xff0c;否则可以使用动态数组&＃xff0c;将数据开在堆区int* B &＃61; new int[m &＃43; 1];for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i) {//初始化两个动态数组cin >> A[i];}for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i) {cin >> B[i];}stack sta;int index_A &＃61; 1, index_B &＃61; 1;for ( index_A ; index_A <&＃61; m; &＃43;&＃43;index_A) {//即完成主线任务&＃xff0c;将所有数据打入栈sta.push(A[index_A]);while (sta.top() &＃61;&＃61; B[index_B]) {//在输入的过程中可能会有输出index_B&＃43;&＃43;;sta.pop();if (sta.empty())break;}}if (sta.empty())cout <<"Yes" <


2、2其他版本