面試100 兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

        18兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

   一問題描述
      

兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列的操作
appendTail
 
  將要插入的元素push進(jìn)s1。注意此處不需要，再把s2中的元素導(dǎo)入到s1了，因?yàn)閟1和s2兩者的順序是相反的。
 
deleteHead
 如果s2中的元素不為空，則直接彈出棧頂
 若為空，則需要把s1中的元素依次push進(jìn)s2中，并刪除s2中的棧頂  

綜上
  可以直接插入s1中元素，刪除時(shí)，若是s2為空，則需要把s1中的元素插入進(jìn)s2中，然后對(duì)s2實(shí)行刪除操作。

二 代碼如下
    

#include <iostream>
#include <stack>
#include <assert.h>
 using namespace std ;
 template <class T>
  class CQueue
  {
    public :
        CQueue() {}     
        ~CQueue() {} 
        
        void appendTail(const T & node) ;
        void deleteHead() ;
        
    private :
        stack <T> m_stack1 ;
        stack <T> m_stack2 ;                 
  } ;
 template <class T>  
 void CQueue<T>::appendTail(const T & node) //添加尾部 
 {    
    m_stack1.push(node) ;
 }
 
 template <class T>
 void CQueue<T>::deleteHead()  //刪除頭部 
 {
    if(!m_stack2.empty())
   {
     cout<<m_stack2.top()<<endl ;   
     m_stack2.pop() ;
   }    
   else
   { 
     assert(!m_stack1.empty()) ; //兩個(gè)棧都為空，則出現(xiàn)異常錯(cuò)誤 
     
        
     while(!m_stack1.empty())  //將s1中的元素全部push進(jìn)s2,最后在s2中=刪除棧頂 
     {
       m_stack2.push(m_stack1.top()) ;
       m_stack1.pop() ;                   
     }     
   }  
 }
 
  
  
   
 int main()
 {
   CQueue<int> queue ;
  /**//* queue.appendTail(5) ;
   queue.appendTail(4) ;
   queue.appendTail(3) ;
  */ 
   
   queue.deleteHead() ;
   queue.deleteHead() ;
   queue.deleteHead() ;
   queue.appendTail(2);
   queue.appendTail(1);
   queue.deleteHead() ;
   queue.deleteHead() ;
    queue.deleteHead() ;
     queue.deleteHead() ;
   system("pause") ;
   return 0 ;    
 }

posted on 2011-05-18 10:16 kahn 閱讀(572) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法相關(guān)