Java栈的压入、弹出序列(详解)

目录

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

思路分析:

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

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

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

具体过程:

 具体实现:

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--(出栈)

具体过程:

具体实现:

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)文章来源地址https://www.uudwc.com/A/R62mo/

原文地址:https://blog.csdn.net/2301_76161469/article/details/133418172

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年10月26日 15:36
【GESP考级C++】1级样题 闰年统计
下一篇 2023年10月26日 17:07