美文网首页
栈有效出栈序列

栈有效出栈序列

作者: nafoahnaw | 来源:发表于2018-05-04 06:44 被阅读0次

给定栈的输入顺序push和输出顺序pop,判断pop序列是否是可能的出栈序列。
限定条件:push,pop元素不重复

例子:
push={1,2,3,4,5}
pop={1,2,3,4,5} 返回true
pop={3,1,2,5,4} 返回false

思路:将push逐个入栈,每次入栈判断栈顶元素是否和pop[i=0]相等,如果相等则该元素出栈,并且i++,push序列全部入栈但是stack不为空则说明pop序列不是有效的出栈序列
代码如下

    public boolean checkPopOrder(int[] push, int[] pop){
        if(push.length == 0 || pop.length == 0 || push.length != pop.length){
            return false;
        }
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0, j = 0; i < push.length; i++) {
            stack.push(push[i]);
            while (j < pop.length && !stack.isEmpty() && stack.peek() == pop[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

相关文章

  • 栈有效出栈序列

    给定栈的输入顺序push和输出顺序pop,判断pop序列是否是可能的出栈序列。限定条件:push,pop元素不重复...

  • 栈-N946-验证栈序列

    题目 概述:给定一个入栈序列和出栈序列,判断如果以入栈序列的顺序入栈,所给定的出栈序列的顺序是否是合理的 输入:入...

  • 一些常见的算法题目

    合法的出栈序列 已知1至n的数字序列,按顺序入栈,每个数字入栈后即可出栈,也可在栈中停留,返回等待后面的数字入栈出...

  • 算法+数据结构+栈

    堆栈 JVM中的堆栈 入栈出栈。假设序列为abcdefg等, 如果abc 出栈。a,b,c没有入,或a入a出,b入...

  • 入栈出栈序列问题

    时隔将近三年,我又准备在简书上发文章了,初衷依然是将自己对一些算法的理解和感悟记录下来。今天开始动笔时看了一下自己...

  • Swift基础之实现一个栈

    首先栈是一个遵从“后进先出,先进后出”规则的序列。同时还有两个操作:入栈操作,将一个元素放入栈中;出栈操作,当栈不...

  • ACM——栈

    知识点: (原理)所谓栈即只能单进单出的顺序列,对于一串以某种顺序进栈的数列A我们要判断它是否能通过某种序列B出栈...

  • LeetCode-20 有效的括号

    题目:20. 有效的括号 难度:简单 分类:栈 解决方案:入栈出栈 今天我们学习第20题有效的括号,这是一道关于栈...

  • 栈和队列算法设计题(二)

    题目 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作顺序可表示为仅由I和O组成的序列,...

  • Java数据结构:栈(stack)

    1.栈的基本介绍 栈是一个先入后出(FILO-First In Last Out)的有序列表。 栈(stack)是...

网友评论

      本文标题:栈有效出栈序列

      本文链接:https://www.haomeiwen.com/subject/oaprrftx.html