题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。解题思路：
解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。
判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。
代码实现：{/*** 输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。* 假设压入栈的所有数字均不相等。例如序列1 、2、3 、4、5 是某栈压栈序列，* 序列4、5、3、2、1是该压栈序列对应的一个弹出序列，* 但4、3、5、1、2就不可能是该压棋序列的弹出序列。* 【与书本的的方法不同】** @param push 入栈序列* @param pop 出栈序列* @return true：出栈序列是入栈序列的一个弹出顺序*/(int[] push, int[] pop) {(push == null || pop == null || pop.length == 0 || push.length == 0 || push.length != pop.length) {return false;}// 经过上面的参数校验，两个数组中一定有数据，且数据数目相等// 用于存放入栈时的数据Stack<Integer> stack = new Stack<>();// 用于记录入栈数组元素的处理位置int pushIndex = 0;// 用于记录出栈数组元素的处理位置int popIndex = 0;// 如果还有出栈元素要处理while (popIndex < pop.length) {(pushIndex < push.length && (stack.isEmpty() || stack.peek() != pop[popIndex])) {// 入栈数组中的元素入栈stack.push(push[pushIndex]);// 指向下一个要处理的入栈元素pushIndex++;}// 如果在上一步的入栈过程中找到了与出栈的元素相等的元素if (stack.peek() == pop[popIndex]) {// 将元素出栈stack.pop();// 处理下一个出栈元素popIndex++;}{return false;}};}/*** 输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。* 【按书本上的思路进行求解，两者相差不大】** @param push 入栈序列* @param pop 出栈序列* @return true：出栈序列是入栈序列的一个弹出顺序*/(int[] push, int[] pop) {// 用于记录判断出栈顺序是不是入栈顺的一个出栈序列，，默认falseboolean 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++;}(stack.peek() != pop[nextPop]) {break;}// 对应到第一种情况：需要要栈的栈顶元素弹出stack.pop();// 指向下一个要处理的出栈元素的位置nextPop++;}(stack.isEmpty()) {isPossible = true;}}return isPossible;}(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(“true: ” + isPopOrder(push, pop1));System.out.println(“true: ” + isPopOrder(push, pop2));System.out.println(“false: ” + isPopOrder(push, pop3));System.out.println(“false: ” + isPopOrder(push, pop4));int[] push5 = {1};int[] pop5 = {2};System.out.println(“false: ” + isPopOrder(push5, pop5));int[] push6 = {1};int[] pop6 = {1};System.out.println(“true: ” + isPopOrder(push6, pop6));System.out.println(“false: ” + isPopOrder(null, null));// 测试方法2System.out.println();System.out.println(“true: ” + isPopOrder2(push, pop1));System.out.println(“true: ” + isPopOrder2(push, pop2));System.out.println(“false: ” + isPopOrder2(push, pop3));System.out.println(“false: ” + isPopOrder2(push, pop4));System.out.println(“false: ” + isPopOrder2(push5, pop5));System.out.println(“true: ” + isPopOrder2(push6, pop6));System.out.println(“false: ” + isPopOrder2(null, null));}}运行结果：
听他第二十八次提起童年往事，每年的同一天和他庆祝生日，
