队列——用C++模板实现

enqueue.h

[cpp] view plaincopyprint?

1. //用"链表"实现队列  
2. //入队和出队的时间复杂度为O(1)  
3. //复制、清空和遍历队列的时间复杂度为O(n)  
4. template <class DT>  
5. struct Node{  
6.     DT info;  
7.     Node<DT> *next;  
8. };  
9. template <class DT>  
10. class Queue  
11. {  
12. public:  
13.     Queue();  
14.     Queue(const Queue<DT> &apqueue);  
15.     ~Queue();  
16.     Queue<DT>& operator=(const Queue<DT> &apqueue);  
17.     void enqueue(const DT &element);  
18.     bool dequeue(DT &deqEle);  
19.     bool peek(DT &frontEle);   //得到对头的数据  
20.     bool isEmpty() const;  
21.     void makeEmpty();  
22. private:  
23.     Node<DT> *front;    //指向header  
24.     Node<DT> *back;      //指向对尾结点  
25.     Node<DT> header;     //设置一个空的头结点  
26.     inline void deepCopy(const Queue<DT> &apqueue);       //"深复制"  
27. };  

 

enqueue.cpp

[cpp] view plaincopyprint?

1. #include "enqueue.h"  
2. template<class DT>  
3. Queue<DT>::Queue()  
4. {  
5.     front = back = &header;  
6. }  
7. template<class DT>  
8. Queue<DT>::Queue(const Queue<DT> &apqueue)  
9. {  
10.     deepCopy(apqueue);  
11. }  
12. template<class DT>  
13. Queue<DT>::~Queue()  
14. {  
15.     makeEmpty();  
16. }  
17. template<class DT>  
18. void Queue<DT>::enqueue(const DT &element)  
19. {  
20.     Node<DT> *ptr = new Node<DT>;  
21.     ptr->info = element;  
22.     back->next = ptr;  
23.     back = ptr;  
24. }  
25. template<class DT>  
26. bool Queue<DT>::dequeue(DT &deqEle)  
27. {  
28.     if(back == &header)  
29.         return false;  
30.     Node<DT> *ptr;  
31.     ptr = front->next;  
32.     deqEle = ptr->info;  
33.     front->next = ptr->next;  
34.     if(back == ptr)  
35.         back = front;  
36.     delete ptr;  
37.     return true;  
38. }  
39. template<class DT>  
40. bool Queue<DT>::peek(DT &frontEle)  
41. {  
42.     if(back == &header)  
43.         return false;  
44.     frontEle = front->next->info;  
45.     return true;  
46. }  
47. template<class DT>  
48. bool Queue<DT>::isEmpty() const  
49. {  
50.     return front == back;  
51. }  
52. template<class DT>  
53. void Queue<DT>::makeEmpty()  
54. {  
55.     DT temp;  
56.     while( dequeue(temp) );  
57. }  
58. template<class DT>  
59. void Queue<DT>::deepCopy(const Queue<DT> &apqueue)  
60. {  
61.     Node<DT> *oriPtr = apqueue.front;  
62. //  Node<DT> *ptr = new Node<DT>;  
63. //  front = ptr = oriPtr;   //这样赋值就把apqueue和this绑在一起拉...  
64.     Node<DT> *ptr = front = &header;  
65.     while(oriPtr != apqueue.back)  //循环体中操作oriPtr->next的内容，这样就可以把apqueue.back拷贝进去！  
66.     {  
67.         ptr->next = new Node<DT>;  
68.         ptr = ptr->next;  
69.         oriPtr = oriPtr->next;  
70.         ptr->info = oriPtr->info;  
71.     }  
72.     back = ptr;  
73. }  

 

测试用例：

[cpp] view plaincopyprint?

1. #include<iostream>  
2. #include<string>  
3. #include "enqueue.cpp"  
4. using namespace std;  
5. void main()  
6. {  
7.     string str[9] = {"the","quick","fox","jumps","over","the","slow","red","turtle"};  
8.     Queue<string> obj;  
9.     string s;  
10.     for(size_t ix=0;ix<9;++ix)  
11.     {  
12.         obj.enqueue(str[ix]);  
13.     }  
14.     Queue<string> obj1(obj);  //测试复制构造函数  
15.     obj1.peek(s);  
16.     cout<<s<<endl;  
17.     for(size_t ix=0;ix<9;++ix)     //利用dequeue进行毁灭式遍历队列  
18.     {   
19.         obj1.dequeue(s);  
20.         cout<<s<<",";  
21.     }  
22.     if(obj1.isEmpty())  
23.         cout<<endl<<"obj1 is empty!"<<endl;  
24.     Queue<string> obj2 = obj;    //测试重载“=”操作符  
25.     obj2.peek(s);  
26.     cout<<s<<endl;  
27.     for(size_t ix=0;ix<9;++ix)  
28.     {   
29.         obj.dequeue(s);  
30.         cout<<s<<",";  
31.     }  
32. }