面試100 24判斷棧的push序列和pop序列是否相等

                面試100 24判斷棧的push序列和pop序列是否正確

  一 問題描述
       

  使用一個輔助棧，當push的時候，將一個元素push進這個輔助棧，當pop的時候，將一個元素pop進這個輔助棧
 
  具體步驟
  (1)順序掃描出棧隊列，取其隊列的a[i]
  (2)判斷a[i]和當前的輔助棧棧頂top，是否相等，相等的話直接彈出輔助棧棧頂。
  (3)若是不相等，則去查找push隊列。若是能找到a[i]，則將小于等于a[i]的元素，都加入進輔助棧，并在push隊列中刪除。
  (4)若是沒有找到，則應該返回false。表示為不符合的出棧隊列。 

#include <iostream>
#include <stack>
#include <vector>
#include <iterator>
  using namespace std ;
  
  const int N = 5 ;
  
  //判斷push和pop序列是否正確 
  bool pushpop(stack<int> &s ,vector <int> &v ,vector <int> &input)
  {
       
        bool ok = true ;
       vector<int>::iterator iter = input.begin() ; //逐次遍歷輸入堆棧 
       for(; iter < input.end() ; iter++) 
       {
          if(!s.empty() && *iter == s.top())  //若棧頂和pop隊列相同，則直接拋出 
          {            
             s.pop() ;      
             continue ;           
           } 
           //若是不相等,需要去v數組中查找，找不到的話，則報錯，找到的話，將小于等于該值的所有元素都插入 
           
            vector<int>::iterator iters = v.begin() ; //逐次遍歷輸入堆棧 
            for(; iters < v.end() ; iters++) 
               {
                 if(*iters == *iter) //則將之后的全部添加進s中 
                 {
                    vector<int>::iterator i = v.begin() ; //逐次遍歷輸入堆棧 
                       for(; i <= iters ; i++)
                        {
                          s.push(*i) ;                            
                        } 
                        v.erase(v.begin() , iters +1) ;         
                            
                 }        
               }
               
             if(*iter == s.top())  //若棧頂和pop隊列相同，則直接拋出 
             {            
                s.pop() ;      
                         
             }  
              else
             {
               ok = false ;  
               return ok ;    
             } 
           
       }  
       return ok ;     
  }
  
  
  
  int main()
  {
    int i ;
    stack  <int> s; //pop棧 
    vector <int> v; //push隊列 
    vector <int> input ; //輸入的pop隊列 
     int x ;
    for(i = 0 ; i < N ;i++)
    {
      v.push_back(i+1) ;          
      cin>>x ;
      input.push_back(x) ;
    }
    cout<<pushpop(s , v, input) ;
    system("pause") ;
    return 0 ;    
  }

posted on 2011-05-19 09:59 kahn 閱讀(671) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關