给定入栈序列,判断出栈序列是否合法

题目:分别给定入栈序列和出栈序列,然后判断出栈序列是否合法。如入栈序列是[1,3,2,4,5],出栈序列[3,1,2,4,5]是合法的,[3,1,5,2,4]是不合法的。

思路: 判断出栈序列是否合法的标准是:栈顶如果是需要出栈的元素,则出栈,如果不是则将未入栈的元素按入栈序列依次入栈,直到栈顶为出栈的元素。如果所有元素都入栈了,仍然没有找到要弹出的元素,那么该出栈序列一定不是合法的。

参考代码:

#include <iostream>
#include <stack>
using namespace std;

bool isPopOrder(int* pushOrder, int* popOrder, int len){
    if(len<=0)
        return false;

    int* pushIndex=pushOrder,*popIndex=popOrder;
    stack<int> s;
    while(popIndex!=popOrder+len){
        if(!s.empty()&&s.top()==*popIndex){   //从栈顶查找
            s.pop();
            ++popIndex;
        }else{                                //从未入栈的序列查找
            while((pushIndex-pushOrder<len)&&(*pushIndex!=*popIndex)){
                s.push(*pushIndex);
                ++pushIndex;
            }
            if(pushIndex-pushOrder<len&&(*pushIndex==*popIndex)){   //在未入栈的元素中找到了需要出栈的元素
                ++popIndex;
            }
            else                            //没有找到
                return false;
        }
    }
    return true;
}

int main(){
   int pushOrder[5]={1,3,2,4,5};
   int popOrderRight[5]={5,4,2,3,1};
   int popOrderWrong[5]={3,1,5,2,4};

   if(isPopOrder(pushOrder,popOrderRight,5))
       cout<<"popOrderRight is right"<<endl;
   else
       cout<<"popOrderRight is wrong"<<endl;

   if(isPopOrder(pushOrder,popOrderWrong,5))
       cout<<"popOrderWrong is right"<<endl;
   else
       cout<<"popOrderWrong is wrong"<<endl;

实验结果: 打印输出:

popOrderRight is right
popOrderWrong is wrong

如果代码有bugs,欢迎猿友留言指正。


参考文献

[1]剑指Offer.何海涛.电子工业出版社.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

java计算集合对称差

两个集合的对称差是只属于其中一个集合,而不属于另一个集合的元素组成的集合。 集合A和B的对称差通常表示为AΔB,对称差的符号在有些图论书籍中也使用符号⊕来表示。...

10930
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列13

一、说出一些常用的类,包,接口,请各举5个 常用的类:BufferedReader BufferedWriter FileReader FileWirter ...

28630
来自专栏算法修养

UESTC 485 Game(康托,BFS)

Today I want to introduce an interesting game to you. Like eight puzzle, it is a...

28170
来自专栏电光石火

3X3 九宫格

题目:3X3 的九宫格,每个横竖斜相加都等于15,使用1-9数字。 要求:PHP语言,1-9数字不重复。 解题思路分析: 1:可以知道和为15,所以获...

48470
来自专栏猿人谷

出栈顺序

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

34960
来自专栏公众号_薛勤的博客

Java过滤掉字符串中的html标签、style标签、script标签

11020
来自专栏公众号_薛勤的博客

Java多线程核心技术(五)单例模式与多线程

什么是立即加载?立即加载就是使用类的时候已经将对象创建完毕,常见的实现办法就是直接 new 实例化。

7330
来自专栏武培轩的专栏

剑指Offer-整数中1出现的次数(从1到n整数中1出现的次数)

package Other; /** * 整数中1出现的次数(从1到n整数中1出现的次数) * 求出1~13的整数中1出现的次数,并算出100~1300的...

29630
来自专栏行者常至

009.多线程-AtomicInteger

版权声明:本文为博主原创文章,允许转载,请标明出处。

8320
来自专栏葡萄城控件技术团队

深入浅出OOP(四): 多态和继承(抽象类)

在本文中,我们讨论OOP中的热点之一:抽象类。抽象类在各个编程语言中概念是一致的,但是C#稍微有些不一样。本文中我们会通过代码来实现抽象类,并一一进行解析。 A...

20060

扫码关注云+社区

领取腾讯云代金券