题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
解法1：
代码如下：
package demo;
import java.util.Stack;
public class Test22 {
/**
* @param push
* 入栈序列
* @param pop
* 出栈序列
* @return true：出栈序列是入栈序列的一个弹出顺序
*/
public static boolean isPopOrder(int[] push, int[] pop) {
// 判断出栈序列是不是入栈序列的一个弹出顺序，默认为false
boolean isPossible = false;
if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
// 辅助栈：存放入栈时的数据
Stack<Integer> stack = new Stack<>();
// 记录下一个要处理的入栈元素的位置
int nextPush = 0;
// 记录下一个要处理的出栈元素的位置
int nextPop = 0;
// 如果出栈元素没有处理完，就继续进行处理
while (nextPop < pop.length) {
// 如果栈为空，或者栈顶元素与当前处理的出栈元素不相同，一直进行操作
while (stack.isEmpty() || stack.peek() != pop[nextPop]) {
// 如果入栈元素已经全部入栈了，就退出内层循环
if (nextPush >= push.length) {
break;
}
// 还有入栈元素可以入栈
stack.push(push[nextPush]);
nextPush++;
}
/*
* 此次有2种情况：
* 1.在栈顶上找到了一个与出栈元素相等的元素
* 2.在栈顶上没有找到一个与出栈元素相等的元素，而且入栈元素已经全部入栈了
*/
// 2.
if (stack.peek() != pop[nextPop]) {
break;
}
// 第1种情况，就将出栈的栈顶元素弹出
stack.pop();
// 指向下一个要处理的出栈元素的位置
nextPop++;
}
/*
* 此处有2种情况：
* 1. 外层while循环在第2种情况下退出，此时stack必不为空
* 2. 所有的出栈元素都被正确匹配，此时stack为空
*/
if (stack.isEmpty()) {
isPossible = true;
}
}
return isPossible;
}
public static void main(String[] args) {
int[] push = { 1, 2, 3, 4, 5 };
int[] pop1 = { 4, 5, 3, 2, 1 };
int[] pop2 = { 3, 5, 4, 2, 1 };
int[] pop3 = { 4, 3, 5, 1, 2 };
int[] pop4 = { 3, 5, 4, 1, 2 };
System.out.println(isPopOrder(push, pop1));
System.out.println(isPopOrder(push, pop2));
System.out.println(isPopOrder(push, pop3));
System.out.println(isPopOrder(push, pop4));
int[] push5 = { 1 };
int[] pop5 = { 1 };
System.out.println(isPopOrder(push5, pop5));
System.out.println(isPopOrder(null, null));
}
}
运行结果
