做网站导航一般字号是多少,怎样做不用备案的网站,网站程序开发,站长之家ppt数据结构实验之栈与队列七#xff1a;出栈序列判定
Description 给一个初始的入栈序列#xff0c;其次序即为元素的入栈次序#xff0c;栈顶元素可以随时出栈#xff0c;每个元素只能入栈依次。输入一个入栈序列#xff0c;后面依次输入多个序列#xff0c;请判断这些序…数据结构实验之栈与队列七出栈序列判定
Description 给一个初始的入栈序列其次序即为元素的入栈次序栈顶元素可以随时出栈每个元素只能入栈依次。输入一个入栈序列后面依次输入多个序列请判断这些序列是否为所给入栈序列合法的出栈序列。
例如序列12345是某栈的压入顺序序列45321是该压栈序列对应的一个出栈序列但43512就不可能是该序列的出栈序列。假设压入栈的所有数字均不相等。
Input 第一行输入整数n(1n10000)表示序列的长度。
第二行输入n个整数表示栈的压入顺序。
第三行输入整数t1t10。
后面依次输入t行每行n个整数表示要判断的每一个出栈序列。
Output 对应每个测试案例输出一行如果由初始入栈序列可以得到该出栈序列则输出yes否则输出no。
Samples Sample #1 Input 5 1 2 3 4 5 2 4 5 3 2 1 4 3 5 1 2 Output yes no
分析
设置两个标志i,j分别从两个序列开始走如果两者的值一致这种情况对应的是入栈一个出栈一个如果不相等那么有可能是先入栈了几个元素然后才开始出出栈的所以先保存再栈里一直到栈顶元素等于要判断的序列的j位置元素为止这时候模拟出栈继续上述的循环即可。
#include bits/stdc.h
using namespace std;
int main(){int n,t,j,i,p;int a[10010];int b[10010];scanf(%d,n);for(int i0;in;i)//入栈序列 scanf(%d,a[i]);scanf(%d,t);while(t--){stackint s;for(int i0;in;i)//可能的出栈序列 cinb[i];int i0,j0;while(jn){if(a[i]b[j]){i;j;}else if(!s.empty()s.top()b[j]){//s.pop();j;}else if(in){s.push(a[i]);i;}elsebreak;}if(s.empty())printf(yes\n);elseprintf(no\n);}return 0;
}
