算法-出栈顺序是否正确

末蓝、 2024-04-18 07:50 57阅读 0赞

## 1. 判断出栈顺序是否正确 ##

给出元素进栈顺序，判断出栈序列是否合法。  
例如：

*  入栈 1,2,3,4,5
 *  出栈 4,5,3,2,1

可判断其出栈顺序合法。

## 2. 解法 ##

借用一个辅助的栈，遍历压栈顺序，先将第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈数组下标向后移动一位， 直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

> 入栈1,2,3,4,5  
> 出栈4,5,3,2,1  
> 首先1入辅助栈，此时栈顶1≠4，继续入栈2  
> 此时栈顶2≠4，继续入栈3  
> 此时栈顶3≠4，继续入栈4  
> 此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，辅助栈里面是1,2,3

public boolean isPopOrder(int[] pushA, int[] popA) {
        
           if (pushA.length == 0 || popA.length == 0 || pushA.length != popA.length) {
        
               return false;
           }
           Stack<Integer> s = new Stack<>();
            int popIndex = 0;
            for (int i = 0; i < pushA.length; i++) {
        
                s.push(pushA[i]);//入栈操作
                while (!s.empty() && s.peek() == popA[popIndex]) {
        
                    //如果栈不为空，且栈顶元素等于弹出序列
                    s.pop();//出栈
                    popIndex++; //弹出序列向后一位
                }
            }
            return s.empty();
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-出栈顺序是否正确

1. 判断出栈顺序是否正确给出元素进栈顺序，判断出栈序列是否合法。例如： * 入栈 1,2,3,4,5 * 出栈 4,5,3,2,1 可判断其出栈...

末蓝、/ 2024年04月18日 07:50/ 0 赞/ 58 阅读

相关栈压入和弹出顺序

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

柔情只为你懂/ 2024年02月18日 22:20/ 0 赞/ 47 阅读

相关判断入栈顺序和出栈顺序是否匹配的问题

class Solution2: def IsPopOrder(self, pushV, popV): stack = []

Love The Way You Lie/ 2022年12月31日 01:22/ 0 赞/ 152 阅读

相关 “顺序栈”判断表达式中的括号是否正确配对

问题及代码： / Copyright (c) 2016, 烟台大学计算机与控制工程学院 All rights reserved. 文件名

桃扇骨/ 2022年07月28日 08:35/ 0 赞/ 120 阅读

相关判断元素出栈、入栈顺序的合法性

元素出栈、入栈顺序的合法性。如：入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1），则合法。入栈的序列（1,2,3,4,5），出栈序列为（4,5,2,3,1

ゝ一纸荒年。/ 2022年06月12日 11:39/ 0 赞/ 230 阅读

相关顺序栈的压栈和出栈

include<iostream> using namespace std; const int StackSize=10;

港控/mmm°/ 2022年06月07日 10:50/ 0 赞/ 200 阅读

相关线性表：顺序栈算法实现

顺序栈介绍顺序栈就是用顺序存储结构构成的后进先出这样结构的栈。一般我们用数组来进行模拟。为了让后顺序栈更通用呢，我们还是在数据类型上使用void\，我们只负责维护用户提

爱被打了一巴掌/ 2022年05月31日 12:39/ 0 赞/ 211 阅读

相关数据结构--栈：进栈顺序1234，出栈顺序有哪些？3142不可能

进栈顺序1234，出栈顺序有 1234 1243 1324 1342 1432 2134 2143 2314 2341 2431

港控/mmm°/ 2022年05月28日 11:05/ 0 赞/ 218 阅读

相关判断入栈顺序和出栈顺序是否合理 python实现

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

朴灿烈づ我的快乐病毒、/ 2022年05月14日 07:37/ 0 赞/ 212 阅读

相关出栈顺序

之前参加过华北计算机研究所和优酷土豆的笔试，都考到出栈顺序，之前数据结构学的不到位，遇到这类题时，还着实把我愣了一会，现在总结下，省得以后再遇到这类问题，也希望能给遇到同样问题

电玩女神/ 2022年02月01日 01:55/ 0 赞/ 272 阅读