题目
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。 例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。 （注意：这两个序列的长度是相等的）
分析
设定辅助栈，如果当前弹出的数字刚好是栈顶数字，就直接弹出，如果不是栈顶数字，就继续压栈，如果找到了相等的 数字，就开始进行出栈操作， 如果最后全部出栈，辅助栈为空，则这个序列是一个弹出序列，反之。
代码
import java.util.Stack;
public class offer21 {
public static void main(String[] args) {
offer21 offer21 = new offer21();
int [] pushA = {1,2,3,4,5};
int [] popA = {4,5,3,2,1};
System.out.println(offer21.IsPopOrder(pushA, popA));
}
public boolean IsPopOrder(int [] pushA,int [] popA) {
if (pushA == null || popA == null || pushA.length == 0 || popA.length == 0 || pushA.length != popA.length) {
return false;
}
Stack<Integer> helpStack = new Stack<>();
int popIndex = 0;
for(int i = 0;i < pushA.length;i++){
helpStack.push(pushA[i]);
while ( helpStack.size() > 0 && helpStack.peek() == popA[popIndex] ) {
helpStack.pop();
popIndex++;
}
}
if (helpStack.isEmpty()) {
return true;
}else{
return false;
}
}
}
补充
很多笔试题中，都有这么样一个题：
一个栈输入序列为1,2,3,4,5,则下列序列中不可能是栈的输出序列是( )
A．1 2 3 4 5
B．5 4 3 2 1
C．2 3 4 5 1
D．4 1 2 3 5
答案是D。我们分析，假如大数先弹出，那么比这个数小的数一定还没有弹出过，这些小数都是从小到大依次入栈的，那么既然他们还没出过栈，当他们出栈的时候一定是 按照先进后出的顺序出栈，也就是大的先出栈，小的后出栈。按照这个判断标准，我们去看四个选项。
只有D不满足。
