C--模板实现队列.docx

C++模板实现队列
分类： 准备笔试2011-08-28 20:02 2088人阅读 评论(0) 收藏 举报
c++classvectorinclude
我准备练习一下模板的知识，然后自己实现vector类。在这之前，先用模板实现一个队列来热身吧。队列的底层是链表。主要是熟悉一下模板的写法。
另外，就是模板的定义和实现都要写在一个文件中（export关键字可以避免这样。还没用过），所以倒数第二行我加了个# include "queue.hpp"，只能是hpp，不能是cpp。不然报错。我用的是4.5.2。
1.queue.h
[cpp] view plaincopy
1. /* 
2.  * queue.h 
3.  * 
4.  *  Created on: 2011-8-28 
5.  *      Author: gauss 
6.  */  
7.   
8. #ifndef QUEUE_H_  
9. #define QUEUE_H_  
10.   
11. template<typename T> class queue;  
12.   
13. template<typename T>  
14. class queue_item {  
15.     friend class queue<T> ; //注意此处友元类的声明形式  
16.     queue_item(const T& i) :  
17.         item(i), next(0) {  
18.     }  
19.     T item;  
20.     queue_item *next;  
21. };  
22.   
23. template<typename T>  
24. class queue {  
25. public:  
26.     queue() :  
27.         head(0), tail(0), n(0) {  
28.     }  
29.     queue(const queue &q);  
30.     queue& operator=(const queue &q);  
31.     ~queue();  
32.     void push(const T &i);  
33.     void pop();  
34.     T front();  
35.     T back();  
36.     bool empty() {  
37.         if (n > 0)  
38.             return false;  
39.         else  
40.             return true;  
41.     }  
42.     size_t size() {  
43.         return n;  
44.     }  
45.     void clear();  
46.   
47. private:  
48.     queue_item<T> *head;  
49.     queue_item<T> *tail;  
50.     size_t n;  
51.     void copy_item(const queue &q);  
52. };  
53. #include "queue.hpp"               //注意这句话。  
54. #endif /* QUEUE_H_ */  

2.queue.hpp
[cpp] view plaincopy
1. /* 
2.  * queue.hpp 
3.  * 
4.  *  Created on: 2011-8-28 
5.  *      Author: gauss 
6.  */  
7.   
8. #ifndef QUEUE_HPP_  
9. #define QUEUE_HPP_  
10.   
11. template<typename T>  
12. void queue<T>::push(const T &i) //注意类作用域的形式：queue<T>::  
13. {  
14.     queue_item<T> *item = new queue_item<T> (i);  
15.   
16.     if (n == 0) {  
17.         head = tail = item;  
18.     } else {  
19.         tail->next = item;  
20.         tail = item;  
21.     }  
22.     ++n;  
23. }  
24.   
25. template<typename T>  
26. void queue<T>::pop() {  
27.     if (n > 0) {  
28.         queue_item<T> *temp = head;  
29.         head = head->next;  
30.         delete temp;  
31.         --n;  
32.     }  
33. }  
34.   
35. template<typename T>  
36. T queue<T>::front() {                       //这里的返回显然可以是T&  
37.     if (n > 0) {  
38.         return head->item;  
39.     } else {                            //这里处理的不太好，返回了一个默认初始化的T，实现不知道返回什么好  
40.         T t;  
41.         return t;  
42.     }  
43. }  
44.   
45. template<typename T>  
46. T queue<T>::back() {                  //这里的返回显然可以是T&  
47.     if (n > 0) {  
48.         return tail->item;  
49.     } else {                      //这里我处理的不太好，反回了一个默认初始化的T，实现不知道返回什么好  
50.         T t;  
51.         return t;  
52.     }  
53. }  
54.   
55. template<typename T>  
56. void queue<T>::clear() {  
57.     while (n > 0) {  
58.         pop();  
59.     }  
60. }  
61.   
62. template<typename T>  
63. queue<T>::~queue() {  
64.     clear();  
65. }  
66.   
67. template<typename T>  
68. queue<T>::queue(const queue &q) :  
69.     head(0), tail(0), n(0) {  
70.     copy_item(q);  
71. }  
72.   
73. template<typename T>  
74. queue<T>& queue<T>::operator=(const queue &q)  
75. //注意此处，函数返回类型需此种形式queue<T>&， 不能是queue&  
76. {  
77.     if (this != &q) {  
78.         clear();  
79.         n = 0;  
80.         copy_item(q);  
81.     }  
82.     return *this;  
83. }  
84.   
85. template<typename T>  
86. void queue<T>::copy_item(const queue &q) {  
87.     queue_item<T> *temp = q.head;  
88.     while (temp) {  
89.         push(temp->item);  
90.         temp = temp->next;  
91.     }  
92. }  
93. #endif /* QUEUE_HPP_ */  
3.main.cpp
[cpp] view plaincopy
1. #include <cstdlib>  
2. #include <iostream>  
3. #include "queue.h"  
4. #include <string>  
5.   
6. using namespace std;  
7.   
8. // test the queue class template  
9. int main(int argc, char *argv[]) {  
10.     queue<int> q;  
11.     if (q.empty())  
12.         cout << "empty" << endl;  
13.     else  
14.         cout << "not empty" << endl;  
15.     q.push(1);  
16.     q.push(2);  
17.     queue<int> q2(q);  
18.     q.clear();  
19.     if (q.empty())  
20.         cout << "empty" << endl;  
21.     else  
22.         cout << "not empty" << endl;  
23.     cout << "queue 2: " << q2.front() << endl;  
24.     cout << "queue 2: " << q2.back() << endl;  
25.     cout << "the size of queue 2: " << q2.size() << endl;  
26.     q = q2;  
27.     cout << "queue 1: " << q.front() << endl;  
28.     cout << "queue 1: " << q.back() << endl;  
29.   
30.     queue<string> qs;  
31.     qs.push("gauss");  
32.     qs.push("randy");  
33.     qs.push("jiawenjie");  
34.     cout << qs.front() << endl;  
35.     cout << qs.back() << endl;  
36.     return EXIT_SUCCESS;  
37. }  

运行结果：
empty
empty
queue 2: 1
queue 2: 2
the size of queue 2: 2
queue 1: 1
queue 1: 2
gauss
jiawenjie

读C++ Primer 之队列类模板
分类： c/c++2011-08-08 20:33 1575人阅读 评论(0) 收藏 举报
c++classmakefiledatenull语言
在C语言学习阶段，我们学过了队列的C语言的实现，但是在C++里面，我们使用泛型实现了实现了队列类的模板，虽然有现成的队列类的模板，但是这对于我们了解怎样用泛型以及泛型编程中的一些需要注意的地方却是受益匪浅，特别是容易忘记的地方。
好了，接下来咱们上代码
首先是 templateclass.h 文件的实现
1. /* 
2. * author:xizero00 
3. * mail:xizero00@ 
4. * date:2011-08-08 01:34:33  
5. * Template Queue Sample  模板队列示例 
6. */  
7.   
8.   
9. #ifndef TEMPLATECLASS_H  
10. #define TEMPLATECLASS_H  
11.   
12. #include <iostream>  
13.   
14. using namespace std;  
15.   
16.   
17. //Queue的实现类  
18. //这里是特定的模板友元关系，即类可以只授权特定的实例的访问权，即类Queue和类QueueItem是一对一的关系  
19. template<class T> class Queue;  
20. template <class T>  
21. class QueueItem  
22. {  
23.     //因为Queue是需要使用到这个不公开接口的类中的成员,所以需要将Queue声明为友元类  
24.     friend class Queue<T>;  
25. private:  
26.     //复制构造函数  
27.     QueueItem<T>( const T &q ): item( q ) , next( 0 )  {}  
28.       
29.       
30.     //元素值  
31.     T item;  
32.       
33.     //指向下一个元素的指针  
34.     QueueItem<T> *next;  
35. };  
36.   
37. //类模板  
38. template <class T>  
39. class Queue  
40. {  
41. public:  
42.     //需要注意的一点是,一般在类中实现的函数都会是内联函数  
43.     //使用内联函数的要求是,该函数的代码一般只有几行,并且经常执行  
44.       
45.       
46.       
47.     //默认构造函数  
48.       
49.     //这样的声明也是可以的  
50.     //Queue() :head( 0 ) , tail( 0 ) {}  
51.     Queue<T>() :head( 0 ) , tail( 0 ) {}  
52.       
53.       
54.       
55.     //复制构造函数  
56.       
57.     //当然这样的声明也是可以的  
58.     //Queue( const Queue &q ): head( q.head ) , tail( q.tail ) { copy_elems( q ); }  
59.     Queue<T>( const Queue<T> &q) :head( q.head ) , tail( q.tail ) { copy_elem( q ); }  
60.       
61.       
62.       
63.     //操作符重载  
64.     Queue<T>& operator= ( const Queue<T>& );  
65.       
66.       
67.     //析构函数  
68.     ~Queue(){ destroy(); }    
69.       
70.       
71.     //获取头节点的元素  
72.     T& front() { return head->item; }  
73.       
74.     //下面这个是const版本的  
75.     //const T& front() { return head->item; }  
76.       
77.       
78.       
79.       
80.       
81.     //入队列  
82.     void push( const T& );  
83.       
84.     //出队列  
85.     void pop();  
86.       
87.     //判断是否为空  
88.     bool empty() const { return NULL == head; }  
89.       
90.       
91.     //显示队列元素  
92.     void ShowElements() ;  
93.       
94.       
95.       
96. private:  
97.     //队列的头指针,尾指针,主要用于出入队列用  
98.     QueueItem<T> *head;  
99.     QueueItem<T> *tail;  
100.       
101.     //销毁队列数据  
102.     void destroy();  
103.       
104.     //复制元素  
105.     void copy_elems( const Queue& );  
106. };  
107.   
108. //出队列,即删除队列头部的元素  
109. template<typename T>   
110. void Queue<T>::pop()  
111. {     
112.     //判断是否为空指针  
113.     if( NULL == head )  
114.     {  
115.         return;  
116.     }  
117.       
118.     //保存当前指针的值  
119.     QueueItem<T> *p = head;  
120.       
121.     //将头指针指向下一个元素  
122.     head = head->next;  
123.       
124.     //删除  
125.     delete p;  
126. }  
127.   
128.   
129. //入队列,即从队列的尾部插入数据  
130. template<typename T>  
131. void Queue<T>::push( const T &t )  
132. {  
133.     //构造一个对象  
134.     QueueItem<T> *p = new QueueItem<T>( t );  
135.       
136.       
137.     //在插入队列尾部的时候需要判断队列是否为空的！  
138.     if( empty() )  
139.     {  
140.         head = tail = p;  
141.     }  
142.     else  
143.     {  
144.         //将尾指针的指向下一个元素的指针指向生成的数据  
145.         tail->next = p;  
146.           
147.         //将尾指针移动到最后一个数据上去  
148.         tail = p;  
149.     }  
150. }  
151.   
152.   
153.   
154. //销毁数据  
155. template<typename T>  
156. void Queue<T>::destroy()  
157. {  
158.     //不断地出队列即可  
159.     while( !empty() )  
160.     {  
161.         pop();  
162.     }  
163. }  
164.   
165.   
166. //赋值操作符重载  
167. template<typename T>  
168. Queue<T>& Queue<T>::operator= (const Queue<T> &q)  
169. {  
170.     //复制队列元素,结束条件是head为空的时候  
171.     for( QueueItem<T> *p= q.head ; p  ; p = p->next )  
172.     {  
173.         push( p->item );  
174.     }  
175.       
176. }  
177.   
178.   
179. template<typename T>  
180. void Queue<T>::ShowElements()  
181. {  
182.     cout << "当前队列元素为:" << endl;  
183.     if( !head )  
184.     {  
185.         cout << "oops,当前队列为空...." << endl;  
186.     }  
187.       
188.       
189.     for( QueueItem<T> *p = head ; p  ; p = p->next )  
190.     {  
191.         cout << p->item  << endl;  
192.     }  
193. }  
194.   
195. #endif //TEMPLATECLASS_H  

在看完模板类的声明以及定义之后，我想提醒一下：养成良好的习惯，不要省略指定模板参数即<T>，即便是在类的声明中也不要省略<T>，这样会让你不会忘记模板参数。
否则当你在类的外面实现的时候会忘记写模板参数。
好了接下来看 templatesample.cc文件
1. /* 
2. * author:xizero00 
3. * mail:xizero00@ 
4. * date:2011-08-08 01:34:33  
5. * Template Queue Sample  模板队列示例 
6. */  
7.   
8. #include "templateclass.h"  
9.   
10. int main( int argc , char **argv )  
11. {  
12.     Queue<int> q;  
13.     int data[] = { 1, 2, 4 ,5 };  
14.       
15.     //入队列  
16.     for( int i = 0 ; i < 4 ; i++ )  
17.     {  
18.         q.push( data[i] );  
19.     }  
20.     cout << "q队列元素如下：" << endl;  
21.     q.ShowElements();  
22.       
23.     Queue<int> p;  
24.       
25.     //复制队列元素  
26.     p = q;  
27.       
28.     cout << "p队列元素如下(它是复制的q队列的元素):" << endl;  
29.     p.ShowElements();  
30.       
31.     cout << "对p队列进行出队列操作" << endl;  
32.     p.pop();  
33.     p.ShowElements();  
34.       
35.     cout << "出队列操作进行3次" << endl;  
36.     p.pop();  
37.     p.pop();  
38.     p.pop();  
39.     p.ShowElements();  
40.       
41.       
42.       
43.       
44.     return 0;  
45. }  

下面给出编译所需的Makefile
1. # author:xizero00  
2. # mail:xizero00@  
3. # date:2011-08-08 01:37:39   
4. # Makefile for Template Queue Sample  模板队列示例  
5.   
6. compile:  
7.     g++ templatesample.cc -g -o template  
8.     ./template  
9. clean:  
10.     rm -f template  
11.     ls -al template*  

下面给出我的运行结果：
1. q队列元素如下：  
2. 当前队列元素为:  
3. 1  
4. 2  
5. 4  
6. 5  
7. p队列元素如下(它是复制的q队列的元素):  
8. 当前队列元素为:  
9. 1  
10. 2  
11. 4  
12. 5  
13. 对p队列进行出队列操作  
14. 当前队列元素为:  
15. 2  
16. 4  
17. 5  
18. 出队列操作进行3次  
19. 当前队列元素为:  
20. oops,当前队列为空....  

总结：在学习模板类的时候，我想最重要的还是需要动手，其次是养成良好的编码习惯，能够让你的注释清晰易懂，让你的理解也能够让别人理解，代码看起来清清爽爽的才是最终目的，学习的目的就是和他们分享，一起进步！