31:栈的压入、弹出序列

发表于 | 分类于

题目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]
  1. 如果Stack下一个弹出的数字刚好是栈顶数字，那么直接弹出
  2. 如果Stack下一个弹出的数字不在栈顶，把push[]中还没有入栈的数字压入help，直到把下一个需要弹出的数字压入栈顶为止
  3. 如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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
	}
}

输出：

1
2
true
false

参考文章
图解
【剑指Offer学习】【面试题22：栈的压入、弹出序列】

> >