题目:输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。
比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列:push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
其实这个题目就直接模拟push和pop的过程即可
有一个栈push_stack={1,2,3,4,5} , 一个栈pop_stack={4,5,3,2,1}
一个空栈 temp
int current = 0;
List temp = new ArrayList();
int top=0;
boolean flag = true;
for(int i =0;i<pop_stack.length;i++){
if(temp.size()>0)
top = temp.get(temp.size());
if(current==push_stack.length-1 && top!=pop_stack[current]){
// 如果所有的数字都被push进栈仍然没有找到这个数字,表明该序列不可能是一个pop序列。
flag = false;
}
if(top==pop_stack[i]){
temp.remove(temp.size());
}else{//如果栈顶元素不是想要的,说明还没有push进来,现在push
for(int j=current+1;j<push_stack.length;j++){
temp.add(push_stack[j]);
if(push_stack[j]==top){
current=j;
break;
}
}
}
}
分享到:
相关推荐
程序员面试题精选100题
程序员面试题精选100题
程序员面试题精选程序员面试题精选程序员面试题程序员面试题精选精选
程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试...
程序员面试题精选100题-何海涛 程序员 面试题 算法 数据结构
程序员面试题精选100题(2008)程序员面试题精选100题(2008)
程序员面试题精选100题
一份可以让大家在求职时更能自信的题解,经典的100题,让大家可以感受到算法的经典,当然,自己要更加努力,要懂得举一反三才能更上一层楼!
程序员面试题精选100题
程序员面试题精选100题,以前下过的不全,自己在网上搜了搜,整理了一下。
程序员面试题精选100例.doc