FilesExpand file tree

master

/

31. 栈的压入、弹出序列.md

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

36 lines (23 loc) · 1.26 KB

master

/

31. 栈的压入、弹出序列.md

Copy path

Top

File metadata and controls

• Code
• Blame

36 lines (23 loc) · 1.26 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# 31. 栈的压入、弹出序列

[NowCoder](https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github)

## 题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

## 解题思路

使用一个栈来模拟压入弹出操作。

```java

public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {

int n = pushSequence.length;

Stack<Integer> stack = new Stack<>();

for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {

stack.push(pushSequence[pushIndex]);

while (popIndex < n && !stack.isEmpty()

&& stack.peek() == popSequence[popIndex]) {

stack.pop();

popIndex++;

}

}

return stack.isEmpty();

}

```

<div align="center"><img width="320px" src="https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/githubio/公众号二维码-2.png"></img></div>