题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入元素和在队列头部删除节点的功能。

1 template 
     
      class CQueue 2 { 3 public: 4     CQueue(void); 5     ~CQueue(void); 6  7     void appendTail(const T& element); 8     T deleteHead(); 9 10 private:11     stack
      
        stack1;12     stack
       
         stack2;13 };
       
      
     

思路：栈是先进后出，而队列是先进先出的，而要用栈实现队列的话，两步操作如下：

进队列：第一个栈stack1专门用来压入数据；

出队列：要把队列头部元素输出，而这个头部会在stack1中的底部，因此我们需要利用辅助栈stack2 ，把stack1元素依次压入stack2，这样原来stack1中的底部元素变成stack2的栈顶，而这就是队列的head，将之输出即可。

　　　　上面分析是针对stack2空的情况，若stack2非空，则要继续把stack2中元素依次pop出来。

实现代码：

1 //进队列 2 template 
     
       void CQueue
      
       ::appendTail(const T& element) 3 { 4     stack1.push(element); 5 } 6 //出队列 7 template 
       
         T CQueue
        
         ::deleteHead() 8 { 9     if (stack2.empty())10     {11         //若stack2是空的，则把stack1的元素copy过来12         while (!stack1.empty())13         {14             T& data = stack1.top();15             stack1.pop();16             stack2.push(data);17         }18     }19     if (stack2.empty())20     {21         throw new exception("queue is empty");22     }23     //取stack2栈顶元素，即队列的head24     T head = stack2.top();25     stack2.pop();26     return head;27 28 }
        
       
      
     

腾讯实习生一面的时候被问了这个问题，好像这个考得比较多。

一面的时候还问了一个用数组实现队列的问题，我就说使用int 类型的Head 和 Tail 分别指向头部和尾部，进队列就Tail++，出队列就Head++；以前没对这个问题做过多的思考，总认为只要数组足够长就可以了；后来他问 如果数组大小规定，比如说Size = 10，那该如何操作？我回答的是：Head和Tail继续加下去，只是进出队列的时候，Head和Tail要对size求余；他接着问，怎么判断队列是否满了？于是我写了Tail - Head >= Size，他说OK，你的Head和Tail会不会越界？当时我一开始我以为是int范围不够，于是说改unsigned int 并增加越界的判断；他继续说，实际工作中就是用数组实现队列，腾讯用户那么多，肯定会越界的，你有没有解决办法？我当时回答使用字符串模拟，他问除了这个还有没有别的；我想了一会，才发现其实Head 和Tail 超过了Size之后，前面的值就没用了，于是说可以把Head 和Tail减掉Size的倍数，使他们维持在0~Size的范围，他才满意地点头~~接下来就被它的智力题完虐了……过了一面后，第二天的二面悲剧了。。。

 数组实现队列

code:

1 //数组实现队列 2 template 
     
      class CArrayQueue 3 { 4 public: 5     CArrayQueue(void); 6     ~CArrayQueue(void); 7      8     void appendTail(const T& element); 9     T deleteHead();10 11 private:12     const static int nSize;13     T Array[10];14     int nHead;15     int nTail;16 };17 template 
      
        const int CArrayQueue
       
        :: nSize = 10;18 template 
        
          CArrayQueue
         
          ::CArrayQueue(void)19 {20     this->nHead = 0;21     this->nTail = -1;22 23 }24 template 
          
            CArrayQueue
           
            ::~CArrayQueue(void)25 {26 this->nHead = 0;27 this->nTail = -1;28 }29 //进队列30 template 
            
              void CArrayQueue
             
              ::appendTail(const T& element)31 {32 if (nTail - nHead >= nSize)33 {34 throw new exception("Queue is full!");35 }36 Array[(++nTail) % nSize] = element;37 if (nHead / nSize > 0 )38 {39 nTail -= nSize;40 nHead -= nSize;41 } 42 }43 //出队列44 template 
              
                T CArrayQueue
               
                ::deleteHead()45 {46 T Head = Array[nHead++];47 return Head;48 }