栈--判断出栈序列是否合法

源地址:http://blog.chinaunix.net/uid-21712186-id-1818123.html

假设入栈序列A按照1,2,3,4…n   编号。   

  每次我们可以把序列A中的第一个元素移入堆栈,   

  也可以是从堆栈顶弹出一个元素放入出栈序列B.   

  这样,经过n次入栈和出栈操作后,我们可以得到一个出栈序列B。   

    

  现在,你的任务是对给定的一段序列B:   

  判断序列B是不是序列A:{1,2,3,4…}的出栈序列。   

    

  为了简化大家编程,你只要给出一个像下面这样的函数就行了:   

    

  bool   is_valid_sqnc(int*   s,   int   n);   

    

  其中     

  s:             表示待检验的序列,   

  n:             表示序列s中元素的个数。(1   <   n   <   100)   

  返回值:如果序列s是序列{1,2,3…n}的出栈序列,函数返回   TRUE   ,反之,返回FALSE。     

    

  example:   

  s={3,1,2};           n=3;           返回值:   FALSE       

  s={4,3,2,1};       n=4;           返回值:   TRUE   

  s={1,4,2,3,5};   n=5;           返回值:   FALSE   

    

  (检验序列中不会出现相同编号元素,编号小于1,或大于n等明显错误情况。   

  如s={0,1,5,5}.)   

方法一:

bool   is_valid_sqnc(int*   s,   int   n)   {   

          if(s[0]<1   ||   s[0]>n)   return   false;   

          for(j=1;   j<=s[0];   j++)   stack[top++]   =   j;   

          top–;   //   第一个出栈   

          i=1;   

          while(i<n)   {   //   依次考查后继元素   

                  if(s[i]<0   ||   s[i]>n)   return   false;   //检查范围   

                  if(s[i]>s[i-1])   {   

                          for(;j<=s[i];j++)   stack[top++]   =   j;   

                          top–;   //   又找到一个   

                  }   

                  else   {   

                          e   =   stack[–top];     //   是当前考察元素吗?   

                          if(e!=s[i])   return   false;   

                  }   

                  i++;   

          }   

          return   true;   

  }   

方法二:充要条件

/*     

    *   若出栈序列合法,则一定不存在   1<=i<j<k<=n,使s[j]<s[k]<s[i]   

    *   

    */   

    

  int   is_valid_sqnc(int   *s,   int   n)   

  {   

          int   i,j,k;   

            

          for(i=0;i<n-2;i++){   

                  for(j=i+1;j<n-1;j++){   

                          if(s[j]<s[i]){   

                                  for(k=j+1;k<n;k++){   

          if(s[k]>s[j]&&s[k]<s[i])   return   0;   

                                  }   

                          }   

                  }   

          }   

    

          return   1;   

  }

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