前几个例程还是相当简单的，把链表即时改了一下就是队列了。
还有想了一下，决定这种例程的代码放法是：先把测试代码默认折叠放在前面，然后把实现代码默认展开放在后面。
测试代码如下：
1 #include <iostream> 2 #include "queue.h" 3 using namespace std; 4 using namespace queue; 5 template class Queue<int>; 6 int main(void) 7 { 8 Queue<int> number; 9 10 //测试插入 11 cout << "/*additem()*/" << endl; 12 number.enqueue(2); 13 number.enqueue(3); 14 number.enqueue(5); 15 number.enqueue(7); 16 number.enqueue(11); 17 number.traverse(); 18 cout << " /*end*/ " << flush; 19 20 //测试获取长度 21 cout << "/*length()*/" << endl; 22 cout << number.size() << endl; 23 cout << "/*end*/ " << flush; 24 25 //测试获得头元素 26 cout << "/*getfirst()*/" << endl; 27 cout << number.getfirst() << endl; 28 cout << "/*end*/ " << flush; 29 30 //测试获得尾元素 31 cout << "/*getfirst()*/" << endl; 32 cout << number.getlast() << endl; 33 cout << "/*end*/ " << flush; 34 35 //测试出队 36 cout << "/*remove()*/" << endl; 37 number.dequeue(); 38 number.dequeue(); 39 number.traverse(); 40 cout << " /*end*/ " << flush; 41 42 //测试清空，并测试从空表中出队 43 cout << "/*clear(),remove()*/" << endl; 44 number.clear(); 45 number.dequeue(); 46 cout << "/*end*/ " << flush; 47 48 system("pause"); 49 }
队列实现代码如下：
1 #ifndef QUEUE 2 #define QUEUE 3 #include <iostream> 4 using namespace std; 5 6 namespace queue 7 { 8 9 //节点模板 10 template <typename T> struct Node 11 { 12 Node<T>() : next(nullptr){} 13 Node<T>(const T &item, Node<T>* ptr = nullptr) : data(item), next(ptr){} 14 T data; 15 Node<T>* next; 16 }; 17 //头节点及主体操作 18 template <typename T> class Queue 19 { 20 //构造函数 21 public: 22 Queue<T>() : length(0), front(nullptr), rear(nullptr){} 23 //接口 24 public: 25 //返回长度 26 unsigned int size()const{ return length; } 27 //返回头指针 28 Node<T>* begin()const{ return front; } 29 //判断是否为空 30 bool empty()const{ return length == 0; } 31 //获得头元素 32 T getfirst()const{ return front->data; } 33 //获得尾元素 34 T getlast()const{ return rear->data; } 35 //#查找元素所在地址 36 Node<T>* find(const T &item)const; 37 //#入队，插入队尾 38 bool enqueue(const T &item); 39 //#出队，删除队首元素 40 bool dequeue(); 41 //#遍历并输出队列元素 42 void traverse()const; 43 //#清空队列 44 void clear(); 45 46 //辅助函数 47 private: 48 //#查找元素前驱 49 Node<T>* find_prev(const T& item)const; 50 //数据 51 private: 52 unsigned int length; 53 Node<T>* front; 54 Node<T>* rear; 55 }; 56 57 //如果元素为头元素或元素不存在则返回nullptr，否则返回前驱 58 template <typename T> Node<T>* Queue<T>::find_prev(const T& item)const 59 { 60 if (length == 0) 61 return nullptr; 62 if (front->data == item) 63 return nullptr; 64 for (Node<T>* iter = front; iter->next != nullptr; iter = iter->next) 65 { 66 if (iter->next->data == item) 67 return iter; 68 } 69 return nullptr; 70 } 71 //调用find_prev，如果元素存在则返回地址，不存在则返回nullptr 72 template <typename T> Node<T>* Queue<T>::find(const T &item)const 73 { 74 Node<T>* iter = find_prev(item); 75 if (length == 0) 76 return nullptr; 77 if (front->data == item) 78 return front; 79 return iter->next; 80 } 81 template <typename T> bool Queue<T>::enqueue(const T &item) 82 { 83 Node<T>* pnew = new Node<T>(item); 84 if (length == 0) 85 front = rear = pnew; 86 else 87 { 88 rear->next = pnew; 89 rear = rear->next; 90 } 91 ++length; 92 return true; 93 } 94 template <typename T> bool Queue<T>::dequeue() 95 { 96 if (length == 0) 97 { 98 cout << "No data!" << endl; 99 return false; 100 } 101 Node<T>* save = front; 102 front = front->next; 103 //如果出队后队列为空，则尾指针同时置空 104 if (length == 1) 105 rear = nullptr; 106 delete save; 107 --length; 108 return true; 109 } 110 template <typename T> void Queue<T>::traverse()const 111 { 112 if (length != 0) 113 { 114 for (Node<T>* iter = front; iter != nullptr; iter = iter->next) 115 cout << iter->data << ends; 116 } 117 } 118 template <typename T> void Queue<T>::clear() 119 { 120 Node<T>* iter; 121 while (front != nullptr) 122 { 123 iter = front; 124 front = front->next; 125 delete iter; 126 } 127 front = rear = nullptr; 128 length = 0; 129 } 130 131 } 132 #endif