剑指Offer利用两个栈实现一个队列

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

 1 template <typename T>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<T> stack1;
12     stack<T> stack2;
13 };

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

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

出队列：要把队列头部元素输出，而这个头部会在stack1中的底部，因此我们需要利用辅助栈stack2 ，把stack1元素依次压入stack2，这样原来stack1中的底部元素变成stack2的栈顶，而这就是队列的head，将之输出即可。
　　　　上面分析是针对stack2空的情况，若stack2非空，则要继续把stack2中元素依次pop出来。

实现代码：

 1 //进队列
 2 template <typename T> void CQueue<T>::appendTail(const T& element)
 3 {
 4     stack1.push(element);
 5 }
 6 //出队列
 7 template <typename T> T CQueue<T>::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栈顶元素，即队列的head
24     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 <typename T>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 <typename T> const int CArrayQueue<T>:: nSize = 10;
18 template <typename T> CArrayQueue<T>::CArrayQueue(void)
19 {
20     this->nHead = 0;
21     this->nTail = -1;
22 
23 }
24 template <typename T> CArrayQueue<T>::~CArrayQueue(void)
25 {
26     this->nHead = 0;
27     this->nTail = -1;
28 }
29 //进队列
30 template <typename T> void CArrayQueue<T>::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 <typename T> T CArrayQueue<T>::deleteHead()
45 {
46     T Head = Array[nHead++];
47     return Head;
48 }