题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路
借助一个辅助栈，如果下一个要弹出的数字刚好在栈顶则直接弹出，若不是则到压栈序列中依次将数字压入栈，直至遇到需要弹出的数字，判断的时候根据辅助栈弹出的元素跟弹出栈的顺序是否相等
源代码
public class IsPopOrder {
public boolean isPopOrder1(int[] pushA, int[] popA) {
//定义一个辅助栈
Stack<Integer> stack=new Stack<>();
int j=0;
for(int i=0;i<pushA.length;i++){
if(popA[j]!=pushA[i]){
stack.push(pushA[i]);
}else{
j++;
}
}
for(int i=0;i<stack.size();i++){
if(stack.pop()!=popA[j]){
return false;
}
j++;
}
return true;
}
@SuppressWarnings("unchecked")
public boolean isPopOrder2(ArrayList<Integer> pushA, ArrayList<Integer> popA) {
@SuppressWarnings("rawtypes")
Stack stack = new Stack();
if (pushA.size() == 0 && popA.size() == 0) {
return false;
}
for (int i = 0, j = 0; i < pushA.size(); i++) {
stack.push(pushA.get(i));
while ((!stack.empty()) && (stack.peek() == popA.get(j))) {
stack.pop();
j++;
}
}
return stack.empty() == true;
}
public static void main(String args[]) {
IsPopOrder t = new IsPopOrder();
// ArrayList<Integer> pushA=new ArrayList<Integer>();
// ArrayList<Integer> popA=new ArrayList<Integer>();
// for(int i=1;i<6;i++){
// pushA.add(i);
// }
// popA.add(4);
// popA.add(5);
// popA.add(3);
// popA.add(2);
// popA.add(1);
int[] pushA = new int[] { 1, 2, 3, 4, 5 };
int[] popA = new int[] { 4, 5, 3, 2, 1 };
System.out.println(t.isPopOrder1(pushA, popA));
}
}
注：两种方法思路一样，只是过程简写了