面试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 阅读(650) 评论(0)  编辑 收藏 引用 所属分类: 算法相关