【Weiss】【第03章】队列例程

前几个例程还是相当简单的，把链表即时改了一下就是队列了。

还有想了一下，决定这种例程的代码放法是：先把测试代码默认折叠放在前面，然后把实现代码默认展开放在后面。

测试代码如下：

 #include <iostream>

 #include "queue.h"

 using namespace std;

 using namespace queue;

 template class Queue<int>;

 int main(void)

 {

     Queue<int> number;

     //测试插入

     cout << "/*additem()*/" << endl;

     number.enqueue();

     number.enqueue();

     number.enqueue();

     number.enqueue();

     number.enqueue();

     number.traverse();

     cout << "\n/*end*/\n\n" << flush;

     //测试获取长度

     cout << "/*length()*/" << endl;

     cout << number.size() << endl;

     cout << "/*end*/\n\n" << flush;

     //测试获得头元素

     cout << "/*getfirst()*/" << endl;

     cout << number.getfirst() << endl;

     cout << "/*end*/\n\n" << flush;

     //测试获得尾元素

     cout << "/*getfirst()*/" << endl;

     cout << number.getlast() << endl;

     cout << "/*end*/\n\n" << flush;

     //测试出队

     cout << "/*remove()*/" << endl;

     number.dequeue();

     number.dequeue();

     number.traverse();

     cout << "\n/*end*/\n\n" << flush;

     //测试清空，并测试从空表中出队

     cout << "/*clear(),remove()*/" << endl;

     number.clear();

     number.dequeue();

     cout << "/*end*/\n\n" << flush;

     system("pause");

 }

队列实现代码如下：

 #ifndef QUEUE

 #define QUEUE

 #include <iostream>

 using namespace std;

 namespace queue

 {

 //节点模板

 template <typename T> struct Node

 {

     Node<T>() : next(nullptr){}

     Node<T>(const T &item, Node<T>* ptr = nullptr) : data(item), next(ptr){}

     T data;

     Node<T>* next;

 };

 //头节点及主体操作

 template <typename T> class Queue

 {

 //构造函数

 public:

     Queue<T>() : length(), front(nullptr), rear(nullptr){}

 //接口

 public:

     //返回长度

     unsigned int size()const{ return length; }

     //返回头指针

     Node<T>* begin()const{ return front; }

     //判断是否为空

     bool empty()const{ return length == ; }

     //获得头元素

     T getfirst()const{ return front->data; }

     //获得尾元素

     T getlast()const{ return rear->data; }

     //#查找元素所在地址

     Node<T>* find(const T &item)const;

     //#入队，插入队尾

     bool enqueue(const T &item);

     //#出队，删除队首元素

     bool dequeue();

     //#遍历并输出队列元素

     void traverse()const;

     //#清空队列

     void clear();

 //辅助函数

 private:

     //#查找元素前驱

     Node<T>* find_prev(const T& item)const;

 //数据

 private:

     unsigned int length;

     Node<T>* front;

     Node<T>* rear;

 };

 //如果元素为头元素或元素不存在则返回nullptr，否则返回前驱

 template <typename T> Node<T>* Queue<T>::find_prev(const T& item)const

 {

     if (length == )

         return nullptr;

     if (front->data == item)

         return nullptr;

     for (Node<T>* iter = front; iter->next != nullptr; iter = iter->next)

     {

         if (iter->next->data == item)

             return iter;

     }

     return nullptr;

 }

 //调用find_prev，如果元素存在则返回地址，不存在则返回nullptr

 template <typename T> Node<T>* Queue<T>::find(const T &item)const

 {

     Node<T>* iter = find_prev(item);

     if (length == )

         return nullptr;

     if (front->data == item)

         return front;

     return iter->next;

 }

 template <typename T> bool Queue<T>::enqueue(const T &item)

 {

     Node<T>* pnew = new Node<T>(item);

     if (length == )

         front = rear = pnew;

     else

     {

         rear->next = pnew;

         rear = rear->next;

     }

     ++length;

     return true;

 }

 template <typename T> bool Queue<T>::dequeue()

 {

     if (length == )

     {

         cout << "No data!" << endl;

         return false;

     }

     Node<T>* save = front;

     front = front->next;

     //如果出队后队列为空，则尾指针同时置空

     if (length == )

         rear = nullptr;

     delete save;

     --length;

     return true;

 }

 template <typename T> void Queue<T>::traverse()const

 {

     if (length != )

     {

         for (Node<T>* iter = front; iter != nullptr; iter = iter->next)

             cout << iter->data << ends;

     }

 }

 template <typename T> void Queue<T>::clear()

 {

     Node<T>* iter;

     while (front != nullptr)

     {

         iter = front;

         front = front->next;

         delete iter;

     }

     front = rear = nullptr;

     length = ;

 }

 }

 #endif

巴特西

【Weiss】【第03章】队列例程

最新文章

热门文章