给定栈的输入顺序push和输出顺序pop,判断pop序列是否是可能的出栈序列。
限定条件:push,pop元素不重复
例子:
push={1,2,3,4,5}
pop={1,2,3,4,5} 返回true
pop={3,1,2,5,4} 返回false
思路:将push逐个入栈,每次入栈判断栈顶元素是否和pop[i=0]相等,如果相等则该元素出栈,并且i++,push序列全部入栈但是stack不为空则说明pop序列不是有效的出栈序列
代码如下
public boolean checkPopOrder(int[] push, int[] pop){
if(push.length == 0 || pop.length == 0 || push.length != pop.length){
return false;
}
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0, j = 0; i < push.length; i++) {
stack.push(push[i]);
while (j < pop.length && !stack.isEmpty() && stack.peek() == pop[j]){
stack.pop();
j++;
}
}
return stack.isEmpty();
}
网友评论