面试题7：用两个栈实现队列

stack1负责如队列，stack2负责出队列，当stack2为空时，要将stack1的元素及时放入stack2

两个队列也可以实现一个栈，P61

写程序的时候出了两个问题：

if (stack2.empty())
    {
        while (!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
    }

不要写成while(!stack1.empty() && !stack2.empty())，这样的话只会放入stack1中的一个元素

另外模板函数前不要忘记加类型

template <typename T> void CQueue<T>::appendTail(const T& node)

template <typename T> T CQueue<T>::deleteHead()

完整程序：

 1 #include <iostream>
 2 using namespace std;
 3 #include <stack>
 4 
 5 template <typename T> class CQueue
 6 {
 7 public:
 8     CQueue(void);
 9     ~CQueue(void);
10 
11     // 在队列末尾添加一个结点
12     void appendTail(const T& node);
13 
14     // 删除队列的头结点
15     T deleteHead();
16 
17 private:
18     stack<T> stack1;
19     stack<T> stack2;
20 };
21 
22 template <typename T> CQueue<T>::CQueue(void)
23 {
24 }
25 
26 template <typename T> CQueue<T>::~CQueue(void)
27 {
28 }
29 
30 template <typename T> void CQueue<T>::appendTail(const T& node)
31 {
32     stack1.push(node);
33 }
34 
35 template <typename T> T CQueue<T>::deleteHead()
36 {
37     if (stack2.empty())
38     {
39         while (!stack1.empty())
40         {
41             stack2.push(stack1.top());
42             stack1.pop();
43         }
44     }
45 
46     if (stack2.size() == 0)
47         throw new exception("queue is empty");
48 
49     T head = stack2.top();
50     stack2.pop();
51 
52     return head;
53 
54 }
55 
56 void Test(char actual, char expected)
57 {
58     if (actual == expected)
59         printf("Test passed.
");
60     else
61         printf("Test failed.
");
62 }
63 
64 int main()
65 {
66     CQueue<char> queue;
67 
68     queue.appendTail('a');
69     queue.appendTail('b');
70     queue.appendTail('c');
71 
72     char head = queue.deleteHead();
73     Test(head, 'a');
74 
75     head = queue.deleteHead();
76     Test(head, 'b');
77 
78     queue.appendTail('d');
79     head = queue.deleteHead();
80     Test(head, 'c');
81 
82     queue.appendTail('e');
83     head = queue.deleteHead();
84     Test(head, 'd');
85 
86     head = queue.deleteHead();
87     Test(head, 'e');
88 
89     system("pause");
90     return 0;
91 }