问题描述:采用一个不带头结点只有一个尾结点指针rear的循环单链表存储队列,设计出这种链队的进队、出队、判队空和求队中元素个数的算法。 ios
代码示例:算法
#include <iostream> using namespace std; template <typename T> struct LinkNode //链队数据结点类型 { T data; //结点数据域 LinkNode *next; //指向下一个结点 }; template <typename T> class LinkQueueClass2 { LinkNode<T> *rear; //链队队尾指针 public: LinkQueueClass2(); //构造函数,用于队列初始化 ~LinkQueueClass2(); //析构函数,用于释放队列空间 bool QueueEmpty(); //判队空运算算法 void enQueue(T e); //进队运算算法 bool deQueue(T &e); //出队运算算法 int GetCount(); //求链队中元素个数 }; template <typename T> LinkQueueClass2<T>::LinkQueueClass2() //构造函数,用于队列初始化 { rear = NULL; } template <typename T> LinkQueueClass2<T>::~LinkQueueClass2() //析构函数,用于释放队列空间 { LinkNode<T> *pre = rear, *p; if (rear == NULL) return; p = pre->next; while (p != rear) { delete pre; pre = p; p = p->next; } delete pre; } template <typename T> bool LinkQueueClass2<T>::QueueEmpty() //判队空运算算法 { return (rear == NULL); } template <typename T> void LinkQueueClass2<T>::enQueue(T e) //进队运算算法 { LinkNode<T> *p; p = new LinkNode<T>(); p->data = e; if (rear == NULL) { p->next = p; rear = p; } else { p->next = rear->next; rear->next = p; rear = p; } } template <typename T> bool LinkQueueClass2<T>::deQueue(T &e) //出队运算算法 { LinkNode<T> *q; if (rear == NULL) return false; else if (rear->next == rear) { e = rear->data; delete rear; rear = NULL; } else { q = rear->next; e = q->data; rear->next = q->next; delete q; } return true; } template <typename T> int LinkQueueClass2<T>::GetCount() //求链队中元素个数 { LinkNode<T> *p = rear; if (rear == NULL) return 0; p = rear->next; int i = 1; while (p != rear) { i++; p = p->next; } return i; } //===main函数用做调试 void main() { LinkQueueClass2<char> lq; //定义一个字符链队lq char e; cout << "创建一个空队lq\n"; cout << "队lq" << (lq.QueueEmpty() ? "空" : "不空") << endl; cout << "元素a进队\n"; lq.enQueue('a'); cout << "元素b进队\n"; lq.enQueue('b'); cout << "元素c进队\n"; lq.enQueue('c'); cout << "元素d进队\n"; lq.enQueue('d'); cout << "元素e进队\n"; lq.enQueue('e'); cout << "队lq" << (lq.QueueEmpty() ? "空" : "不空") << endl; cout << "全部元素出队次序:"; while (!lq.QueueEmpty()) //队不空循环 { lq.deQueue(e); //出队元素e cout << e << " "; //输出元素e } cout << endl; cout << "销毁队lq" << endl; }