注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

linux 学习

 
 
 

日志

 
 

【转】C++模板实现队列  

2014-06-10 16:10:52|  分类: 应用编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

我准备练习一下模板的知识,然后自己实现vector类。在这之前,先用模板实现一个队列来热身吧。队列的底层是链表。主要是熟悉一下模板的写法。

另外,就是模板的定义和实现都要写在一个文件中(export关键字可以避免这样。还没用过),所以倒数第二行我加了个# include "queue.hpp",只能是hpp,不能是cpp。不然报错。我用的是4.5.2。


  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

  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

  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;  



运行结果:

empty
empty
queue 2: 1
queue 2: 2
the size of queue 2: 2
queue 1: 1
queue 1: 2
gauss
jiawenjie


  评论这张
 
阅读(561)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017