【算法练习四】判断栈的出栈顺序是否正确

一般这种题都是出现在选择题里面的,而且元素较少,所以即使我们使用野路子(依次把选项代入测试)也不会花费多少时间。但是,我们总不能一直打游击啊,当遇到敌人主力的时候无能为力,那就坑了。
所以这里介绍怎样转游击战为阵地战,从正面硬刚敌人并且取胜的方法。

首先,假设入栈顺序是1,2,3,4
正确的出栈顺序(其中一种)2,3,4,1
错误的出栈顺序(其中一种)3,1,4,2
然后,开始准备进攻。我们设置一个中间栈:tempStack,记录一个出栈顺序下标index
1、按入栈顺序,存入一个元素到tempStack中
2、比较tempStack的栈顶元素与出栈顺序的第index个元素比较
相同,则进行3,否则进行1
3、弹出tempStack的栈顶元素,index++。执行2。
最后,如果循环结束后,tempStack为空,则表示出栈顺序正确。否则,出栈顺序错误。
估计乍看一眼,可能难以理解。其实,这就是模拟了一遍出入栈的过程。觉得难以理解的话,可以在纸上按上述流程把所有元素的入栈出栈画一遍就应该能理解了。我把代码贴在下面了,但是由于我用vector比较熟,所以在代码中也直接使用vector代替stack了。

 

import java.util.*;

public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {

int size = pushA.length;
// 首先把pushA的东西都入栈
Stack<Integer> stack = new Stack<>();
// index 表示目前出栈到哪里了
int index_pop = 0;
// 核心代码
for(int i=0;i<size;i++){
stack.push(pushA[i]);
while(!stack.empty() && stack.peek() == popA[index_pop]){
index_pop++;
stack.pop();
}
}

return stack.empty();
}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注