算法-出栈顺序是否正确

末蓝、 2024-04-18 07:50 158阅读 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 条评论，158人围观）

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

相关阅读

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

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

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

相关栈内存中方法的入栈，出栈顺序测试

一、代码在main()方法中调用f1()，在f1()中调用f2()，测试三个方法在栈内存中的执行顺序。![933182c82d1549b3bde299cabcaad3b

- 日理万妓/ 2023年09月30日 19:07/ 0 赞/ 122 阅读

相关【算法与数据结构 05】后进先出的栈——顺序栈、链栈知多少?

文章目录 1.栈的简介 2. 栈的基本操作（1）顺序栈（2）链栈 3. push和p

客官°小女子只卖身不卖艺/ 2023年02月26日 10:25/ 0 赞/ 100 阅读

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

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

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

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

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

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

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

元素出栈、入栈顺序的合法性。如：入栈的序列（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 赞/ 372 阅读

相关顺序栈的压栈和出栈

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

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

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

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

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

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

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

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

相关出栈顺序

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

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