题目：用两个栈实现一个队列。队列的生命如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。template 
     
      class CQueue{public:　　CQueue(void);　　~CQueue(void);　　void appendtail(const T& node);　　T deleteHead();private:　　stack
      
        stack1;　　stack
       
         stack2;};
       
      
     

解题思路：

插入操作在stack1中进行，删除操作在stack2中进行，如果stack2为空，则将stack1中的所有元素转移到stack2中。

代码实例：

#include
      
       #include
       
        #include
        
         using namespace std;template 
         
          class CQueue{public:    CQueue(void);    ~CQueue(void);    void appendtail(const T& node);    T deleteHead();private:    stack
          
            stack1;    stack
           
             stack2;};//构造函数template 
            
              CQueue
             
              ::CQueue(void){}//析构函数template 
              
                CQueue
               
                ::~CQueue(void){}//插入元素template 
                
                  void CQueue
                 
                  ::appendtail(const T& node){ stack1.push(node);}//删除元素并返回template 
                  
                    T CQueue
                   
                    ::deleteHead(){ if(stack2.size()<=0) { while(stack1.size()>0) { stack2.push(stack1.top()); stack1.pop(); } } if(stack2.size()==0) throw new exception("队列为空"); T head=stack2.top(); stack2.pop(); return head;}void main(){ CQueue
                    
                      queue; queue.appendtail(1); queue.appendtail(2); queue.appendtail(3); queue.appendtail(4); int len=4; while(len>0) { cout<
                     
                      <
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

使用两个队列实现一个栈

参考文献：

解法：

1. 有两个队列q1和q2，先往q1内插入a，b，c，这做的都是栈的push操作。
2. 现在要做pop操作，即要得到c，这时可以将q1中的a,b两个元素全部dequeue并存入q2中，这时q2中元素为a，b，对q1再做一次dequeue操作即可得到c。
3. 如果继续做push操作，比如插入d，f，则把d，f插入到q2中，
4. 此时若要做pop操作，则做步骤2
5. 以此类推，就实现了用两个队列来实现一个栈的目的。

注意在此过程中，新push进来的元素总是插入到非空队列中，空队列则用来保存pop操作之后的那些元素，那么此时空队列不为空了，原来的非空队列变为空了，总是这样循环。

对于push和pop操作，其时间为O(n).

代码实例

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;template 
          
           class CStack{public:    CStack(void){};    ~CStack(void){};    void push(const T& node);    T pop();private:    queue
           
             queue1; queue
            
              queue2; };//插入元素template 
             
               void CStack
              
               ::push(const T& element){ if(queue1.size()>0)//如果queue1不为空则往queue1中插入元素 queue1.push(element); else if(queue2.size()>0)//如果queue2不为空则往queue2中插入元素 queue2.push(element); else//如果两个队列都为空，则往queue1中插入元素 queue1.push(element); }//删除元素template 
               
                 T CStack
                
                 ::pop(){ if(queue1.size()==0)//如果queue1为空 { while(queue2.size()>1)//保证queue2中有一个元素，将其余元素保存到queue1中 { queue1.push(queue2.front()); queue2.pop(); } T& data=queue2.front(); queue2.pop(); return data; } else//如果queue2为空 { while(queue1.size()>1)//保证queue2中有一个元素，将其余元素保存到queue1中 { queue2.push(queue1.front()); queue1.pop(); } T& data=queue1.front(); queue1.pop(); return data; }}void main(){ CStack
                 
                   stack; stack.push(1); stack.push(2); stack.push(3); stack.push(4); int len=4; while(len>0) { cout<
                  
                   <<" "; --len; } system("pause");}