31:栈的压入、弹出序列
2018-09-12 本文已影响0人
stoneyang94
题目31：栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
举例说明
序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路
解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。
判断一个序列是不是栈的弹出序列的规律：
- 压栈序列：
int[] push - 弹出序列：
int[] pop - 辅助栈：
Stack<Integer> help = new Stack<>(); - 判断弹出元素是不是栈顶元素
help.peek() != pop[nextPop]
- 如果Stack下一个弹出的数字刚好是栈顶数字，那么直接弹出
- 如果Stack下一个弹出的数字不在栈顶，把push[]中还没有入栈的数字压入help，直到把下一个需要弹出的数字压入栈顶为止
- 如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列
代码实现
public class _31 {
public static boolean isPopOrder(int[] push, int[] pop) {
boolean isPossible = false;
// a. 都不为空 b. 都有数据，且数据个数都相等
if (push != null && pop != null && push.length > 0 && push.length == pop.length) {
Stack<Integer> help = new Stack<>();// 用于存放入栈时的数据
int nextPush = 0;
int nextPop = 0;
while (nextPop < pop.length) { // 如果pop[] 没有处理完就继续进行处理
// a. 栈为空 b. 栈顶的元素与当前处理的出栈元素不相同
while (help.isEmpty() || help.peek() != pop[nextPop]) {
if (nextPush >= push.length) {//若入栈的元素已经全部入栈了
break;//就退出内层循环
}
//说明没被break。nextPush < push.length,还有push[] 可以入栈
help.push(push[nextPush]);// 将push[]元素 入 help栈
nextPush++;// 指向下一个要处理的入栈元素的位置
}
// 执行到此处有两种情况：
// 第一种：在栈顶上找到了一个与入栈元素相等的元素
// 第二种：在栈顶上没有找到一个与入栈元素相等的元素，但输入栈的元素已经全部入栈了
// 对于第二种情况就说弹出栈的顺序是不符合要求的，退出外层循环
if (help.peek() != pop[nextPop]) {
break;
}
help.pop();// 对应到第一种情况：需要要栈的栈顶元素弹出
nextPop++;// 指向pop[]下一个要处理的出栈元素的位置
}
// 执行到此处有两种情况
// 第一种：外层while循环被break
// 第二种：所有的出栈元素都被正确匹配
// 对于出现的第一种情况其stack.isEmpty()必不为空，原因为分析如下：
// 所有的入栈元素一定会入栈，但是只有匹配的情况下才会出栈，
// 匹配的次数最多与入栈元素个数元素相同（两个数组的长度相等），如果有不匹配的元素，
// 必然会使出栈的次数比入栈的次数少，这样栈中至少会有一个元素
// 对于第二种情况其stack.isEmpty()一定为空
// 所以书本上的nextPop == pop.length（pNextPop-pPop==nLength）是多余的
if (help.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 = { 4, 3, 5, 1, 2 };
System.out.println(isPopOrder(push, pop1));// true
System.out.println(isPopOrder(push, pop2));// false
}
}
输出：
true
false
