jake1036

面试100 两个栈实现一个队列

        18两个栈实现一个队列

   一问题描述
      

两个栈实现一个队列的操作
appendTail
 
  将要插入的元素push进s1。注意此处不需要，再把s2中的元素导入到s1了，因为s1和s2两者的顺序是相反的。
 
deleteHead
 如果s2中的元素不为空，则直接弹出栈顶
 若为空，则需要把s1中的元素依次push进s2中，并删除s2中的栈顶  

综上
  可以直接插入s1中元素，删除时，若是s2为空，则需要把s1中的元素插入进s2中，然后对s2实行删除操作。

二 代码如下
    

#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()) ; //两个栈都为空，则出现异常错误 
     
        
     while(!m_stack1.empty())  //将s1中的元素全部push进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 阅读(554) 评论(0)  编辑 收藏 引用 所属分类: 算法相关


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理