Java栈的压入、弹出序列（详解）

雨点打透心脏的1/2处 2023-10-16 16:26 11阅读 0赞

**目录**

1.题目描述

2.题解

方法1

方法2

--------------------

## 1.题目描述 ##

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

> 1. 0<=pushV.length == popV.length <=1000
> 
> 2. -1000<=pushV\[i\]<=1000
> 
> 3. pushV 的所有数字均不相同

**示例：**

> **输入：**\[1,2,3,4,5\],\[4,5,3,2,1\]
> 
> **返回：**true

> **输入：**\[1,2,3,4,5\],\[4,3,5,1,2\]
> 
> **返回：**false

## 2.题解 ##

### 方法1 ###

**思路分析：**

判断两个序列是否符合入栈、出栈的次序，我们可以使用一个栈来模拟。

入栈：栈顶元素不等于出栈序列当前元素

出栈：栈顶元素等于出栈序列当前元素

**具体过程：**

![6762ed24c88d4cddb468327f23c6ff52.png][]

**具体实现：**

1.创建一个栈，来模拟入栈、出栈次序

2.使用i、j来遍历pushV、popV数组，i < pushV.length，入栈

3.栈顶元素等于popV数组当前元素时，出栈

4.遍历完pushV数组后，判断栈是否为空，栈为空，弹出序列为正确的出栈顺序；反之，则为错误的出栈顺序

**代码实现：**

public class Solution {
        public boolean IsPopOrder (int[] pushV, int[] popV) {
            Stack<Integer> stack = new Stack<>();
            int j = 0;
            for (int i = 0; i < pushV.length; i++) {
                stack.push(pushV[i]);
                //判断是否有元素出栈
                while(j < popV.length && !stack.empty()){
                    int k = stack.peek();
                    if(k == popV[j]){
                        stack.pop();
                        j++;
                    }else{
                        break;
                    }
                }
            }
            return stack.empty();
        }
    }

### 方法2 ###

**思路分析：**

由于数组本身就可用于实现栈，我们可以将pushV数组当作栈，使用p来标记栈顶，

入栈：pushV\[p\](栈顶元素)不等于当前出栈数组中元素，p++(入栈)

出栈：pushV\[p\](栈顶元素)等于当前出栈数组中元素，p--(出栈)

**具体过程：**

**![4c19ca5b0e7d4c9abc2e25157f86ca7b.png][]**

**具体实现：**

1.使用p来标识栈顶元素

2.使用i、j来遍历pushV、popV数组，pushV\[p\](栈顶元素)不等于当前出栈数组中元素，

pushV\[p\] = pushV\[i\]，p++

3.pushV\[p\](栈顶元素)等于当前出栈数组中元素，p--

4.遍历完pushV数组后，判断p的大小，若p为0，则表示所有元素都已出栈，出栈序列为正确的出栈顺序，返回true，否则，返回false

**代码实现：**

public class Solution {
        public boolean IsPopOrder (int[] pushV, int[] popV) {
            int p = 0;//标识栈顶
            int j = 0;//出栈序列下标
            for(int n : pushV){
                pushV[p] = n;
                while( p>=0 && j < popV.length && pushV[p] == popV[j]){
                    j++;
                    p--;
                }
                p++;
            }
            return p==0;
        }
    }

**题目来自：**

[栈的压入、弹出序列\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com]

[6762ed24c88d4cddb468327f23c6ff52.png]: https://img-blog.csdnimg.cn/6762ed24c88d4cddb468327f23c6ff52.png
[4c19ca5b0e7d4c9abc2e25157f86ca7b.png]: https://img-blog.csdnimg.cn/4c19ca5b0e7d4c9abc2e25157f86ca7b.png
[_nowcoder.com]: https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking