正文
九度oj 题目1366：栈的压入、弹出序列
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
- 题目描述：
-
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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。
- 样例输入：
-
5
1 2 3 4 5
4 5 3 2 1
5
1 2 3 4 5
4 3 5 1 2
- 样例输出：
-
Yes
No 这个题一开始提交的代码是这样#include <cstdio>
#include <cstdlib>
#include <stack> using namespace std; int num1[];
int num2[];
int n; stack <int> tmp; int main(int argc, char const *argv[])
{
while(scanf("%d",&n) != EOF) {
for(int i = ; i < n; i++) {
scanf("%d",&num1[i]);
}
for(int i = ; i < n; i++) {
scanf("%d",&num2[i]);
}
while(!tmp.empty()) {
tmp.pop();
}
int p1 = , p2 = ; while(p1 < n && p2 < n) {
if(num1[p1] != num2[p2]) {
tmp.push(num1[p1]);
p1++;
}
else {
p1++;
p2++;
}
}
while(!tmp.empty()) {
int cp = tmp.top();tmp.pop();
if(p2 < n && cp == num2[p2]) {
p2++;
}
else {
break;
}
}
if(tmp.empty()) {
puts("Yes");
}
else {
puts("No");
}
}
return ;
}这段代码在逻辑上有问题，判断是否出栈的条件写错
修改如下
#include <cstdio>
#include <cstdlib>
#include <stack> using namespace std; int num1[];
int num2[];
int n; stack <int> tmp; int main(int argc, char const *argv[])
{
while(scanf("%d",&n) != EOF) {
for(int i = ; i < n; i++) {
scanf("%d",&num1[i]);
}
for(int i = ; i < n; i++) {
scanf("%d",&num2[i]);
}
while(!tmp.empty()) {
tmp.pop();
}
int p = ; for(int i = ; i < n; i++) {
tmp.push(num1[i]);
int cp = tmp.top();
while(p < n && cp == num2[p]) {
tmp.pop();
p++;
if(tmp.empty()) {
break;
}
cp = tmp.top(); }
}
if(tmp.empty()) {
puts("Yes");
}
else {
puts("No");
}
}
return ;
}注意32行，p++必须在break之前
