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

题目:分别给定入栈序列和出栈序列,然后判断出栈序列是否合法。如入栈序列是[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.何海涛.电子工业出版社.

    原文作者:恋喵大鲤鱼
    原文地址: https://blog.csdn.net/K346K346/article/details/50981740
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞