(1)问题描述
- 题目描述:
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 输入:
每个测试案例包括3行:
第一行为1个整数n(1<=n<=100000),表示序列的长度。
第二行包含n个整数,表示栈的压入顺序。
第三行包含n个整数,表示栈的弹出顺序。
- 输出:
对应每个测试案例,如果第二个序列是第一个序列的弹出序列输出Yes,否则输出No
(2)程序实现
栈的特点是后进先出,假设入栈的顺序是 1 2 3 4 5,出栈的顺序是:4 5 3 2 1,这样操作的顺序是:push 1, push 2,push 3,push 4,pop 4, push 5 , pop 5,pop 3, pop 2, pop 1。假设出栈的顺序是4 5 3 1 2,这种顺序是错误的,因为1比2先压入栈,所以2的出栈顺序应该是1之前,显然出栈顺序是错误的。
判断思路:遍历出栈顺序中的元素,有两种情况 A:如果元素是栈顶的元素,则pop出来;B:如果不是栈顶元素,则根据入栈顺序将没入栈的元素push进栈,直到将该元素push栈中,然后将该元素pop出来,如果push完所有元素都没有找到该元素,那么这个出栈顺序是错误的。
#include <iostream>#include <stack> using namespace std; int main(){ int n; while(cin>>n) { stack<int> s; int* stack_in = new int[n]; int* stack_out = new int[n]; for(int i=0; i<n; ++i) cin>>stack_in[i]; for(int i=0; i<n; ++i) cin>>stack_out[i]; int i = 0; bool isValid = false;//判断标志 for(int j=0; j<n; ++j) { //判断栈顶是否是该元素 if(s.size() != 0 && s.top() == stack_out[j]) s.pop(); else { bool find = false; for(; i<n;++i) { s.push(stack_in[i]); if(stack_in[i] == stack_out[j]) { ++i; find = true; break; } } if(!find) { isValid = true; break; } else s.pop(); } } if(isValid) cout<<"No"<<endl; else cout<<"Yes"<<endl; delete[] stack_in; delete[] stack_out; } }