原地址：http://blog.csdn.net/cainv89/article/details/51526229
链式队列(Linked Queue)
1. 链式队列的概念
1.1 链式队列的定义
- 链式队列是基于单链表的存储表示实现的队列。
1.2 链式队列中各元素的逻辑及存储关系
- 链式队列可以采用单链表作为其存储表示，因此，可以在链式队列的声明中用单链表定义它的存储空间。
- 链式队列的队头指针指向单链表的第一个结点，队尾指针指向单链表的最后一个结点。
- 注：链式队列的队头元素存放在单链表的第一个结点内，若要从队列中退出一个元素，必须从单链表中删去第一个结点，而存放着新元素的结点应插在队列的队尾，即单链表的最后一个结点后面，这个新节点将成为新的队尾。
1.3 链式队列的特点
- 用单链表表示的链式队列特别适合于数据元素变动比较大的情况，而且不存在队列满而产生溢出的情况。
- 若程序中要使用多个队列，与多个栈的情形一样，用链接表示不仅能够提高效率，还可以达到共享存储空间的目的。
- 使用链式队列不会出现存储分配不合理的问题，也不需要进行存储的移动，
2. 链式队列的实现
2.1 链表结点结构的定义
文件：LinkNode.h
#ifndef LINK_NODE_H_ #define LINK_NODE_H_ #include <iostream> #include <string> #include <strstream> using namespace std; template <class T> struct LinkNode //链表结点类的定义 { T data; //数据域 LinkNode<T> *link; //指针域——后继指针 //仅初始化指针成员的构造函数 LinkNode(LinkNode<T>* ptr = NULL){ link = ptr; } //初始化数据与指针成员的构造函数 LinkNode(const T& value, LinkNode<T>* ptr = NULL){ data = value; link = ptr; } }; #endif /* LINK_NODE_H_ */
2.2 链式队列的类定义及其操作的实现
-
文件：LinkedQueue.h
#ifndef LINKED_QUEUE_H_ #define LINKED_QUEUE_H_ #include "LinkNode.h" #include "Queue.h" template <class T> class LinkedQueue : public Queue<T> { public: LinkedQueue(); //构造函数 virtual ~LinkedQueue(); //析构函数 public: virtual bool getHead(T& x) const; //读取队头元素，并将该元素的值保存至x virtual bool EnQueue(const T& x); //新元素x入队 virtual bool DeQueue(T& x); //队头元素出队，并将该元素的值保存至x virtual bool IsEmpty() const; //判断队列是否为空 virtual bool IsFull() const; //判断队列是否为满 virtual void MakeEmpty(); //清空队列的内容 virtual int getSize() const; //计算队列中元素个数 public: template <class T> friend ostream& operator<<(ostream& os, const LinkedQueue<T>& q); //输出队列中元素的重载操作<< private: LinkNode<T> *front; //队头指针，即链头指针 LinkNode<T> *rear; //队尾指针，即链尾指针 }; //构造函数 template <class T> LinkedQueue<T>::LinkedQueue() : front(NULL), rear(NULL) { cout << "$ 执行构造函数" << endl; } //析构函数 template <class T> LinkedQueue<T>::~LinkedQueue() { cout << "$ 执行析构函数" << endl; MakeEmpty(); } //读取队头元素，并将该元素的值保存至x template <class T> bool LinkedQueue<T>::getHead(T& x) const { if (true == IsEmpty()) { return false; } x = front->data; return true; } //新元素x入队 template <class T> bool LinkedQueue<T>::EnQueue(const T& x) { LinkNode<T> *newNode = new LinkNode<T>(x); if (NULL == newNode) { return false; } if (NULL == front) { front = newNode; rear = newNode; } else { rear->link = newNode; rear = rear->link; } return true; } //队头元素出队，并将该元素的值保存至x template <class T> bool LinkedQueue<T>::DeQueue(T& x) { if (true == IsEmpty()) { return false; } LinkNode<T> *curNode = front; front = front->link; x = curNode->data; delete curNode; return true; } //判断队列是否为空 template <class T> bool LinkedQueue<T>::IsEmpty() const { return (NULL == front) ? true : false; } //判断队列是否为满 template <class T> bool LinkedQueue<T>::IsFull() const { return false; } //清空队列的内容 template <class T> void LinkedQueue<T>::MakeEmpty() { LinkNode<T> *curNode = NULL; while (NULL != front) //当链表不为空时，删去链表中所有结点 { curNode = front; //保存被删结点 front = curNode->link; //被删结点的下一个结点成为头结点 delete curNode; //从链表上摘下被删结点 } } //计算队列中元素个数 template <class T> int LinkedQueue<T>::getSize() const { int count = 0; LinkNode<T> *curNode = front; while (NULL != curNode) { curNode = curNode->link; count++; } return count; } //输出队列中元素的重载操作<< template <class T> ostream& operator<<(ostream& os, const LinkedQueue<T>& q) { int i = 0; LinkNode<T> *curNode = q.front; while (NULL != curNode) { os << "[" << i++ << "]" << " : " << curNode->data << endl; curNode = curNode->link; } return os; } #endif /* LINKED_QUEUE_H_ */
2.3 主函数(main函数)的实现
-
文件：main.cpp
-
#include "LinkedQueue.h" #define EXIT 0 //退出 #define GETHEAD 1 //读取队头元素，并将该元素的值保存至x #define ENQUEUE 2 //新元素x入队 #define DEQUEUE 3 //队头元素出队，并将该元素的值保存至x #define ISEMPTY 4 //判断队列是否为空 #define ISFULL 5 //判断队列是否为满 #define MAKEEMPTY 6 //清空队列的内容 #define GETSIZE 7 //计算队列中元素个数 #define OPERATOR_OSTREAM 8 //输出队列元素的重载操作<< void print_description() { cout << "------------------------------>链式队列<------------------------------" << endl; cout << "功能选项说明：" << endl; cout << "#0： 退出" << endl; cout << "#1： 读取队头元素，并将该元素的值保存至x" << endl; cout << "#2： 新元素x入队" << endl; cout << "#3： 队头元素出队，并将该元素的值保存至x" << endl; cout << "#4： 判断队列是否为空" << endl; cout << "#5： 判断队列是否为满" << endl; cout << "#6： 清空队列的内容" << endl; cout << "#7： 计算队列中元素个数" << endl; cout << "#8： 输出队列元素的重载操作<<" << endl; cout << "--------------------------------------------------------------------" << endl; } //判断输入的字符串每个字符是否都是数值0~9 bool IsNumber(const string& s_num) { for (size_t i = 0; i < s_num.size(); i++) { if ((s_num[i] < '0') || (s_num[i] > '9')) { return false; } } return true; } //类型转换——将string型转为模板类型T template <class T> T StrToTtype(const string& s_num) { T n_num; strstream ss_num; ss_num << s_num; ss_num >> n_num; return n_num; } //输入数据值 template <class T> T get_data() { cout << "> 请输入数据值，data = "; string s_data; cin >> s_data; return StrToTtype<T>(s_data); } //构造链式队列 template <class T> LinkedQueue<T>* construct_linkedqueue() { cout << " ==> 创建链式队列" << endl; LinkedQueue<T> *linkedQueue = new LinkedQueue<T>; return linkedQueue; } //析构链式队列 template <class T> void destory_linkedqueue(LinkedQueue<T>* linkedQueue) { cout << " ==> 释放链式队列在堆中申请的空间，并将指向该空间的指针变量置为空" << endl; delete linkedQueue; linkedQueue = NULL; } //读取队头元素，并将该元素的值保存至x template <class T> void gethead(LinkedQueue<T>* linkedQueue) { cout << "$ 执行读取队头元素并将该元素的值保存至x函数" << endl; T data; if (false == linkedQueue->getHead(data)) { cout << "* 读取队头元素失败" << endl; return; } cout << "* 读取队头元素成功，data = " << data << endl; } //新元素x入队 template <class T> void enqueue(LinkedQueue<T>* linkedQueue) { cout << "$ 执行新元素x入队函数" << endl; T data = get_data<T>(); if (false == linkedQueue->EnQueue(data)) { cout << "* 入队失败" << endl; return; } cout << "* 入队成功，data = " << data << endl; } //队头元素出队，并将该元素的值保存至x template <class T> void dequeue(LinkedQueue<T>* linkedQueue) { cout << "$ 执行队头元素出队并将该元素的值保存至x函数" << endl; T data; if (false == linkedQueue->DeQueue(data)) { cout << "* 出队失败" << endl; return; } cout << "* 出队成功，data = " << data << endl; } //判断队列是否为空 template <class T> void isempty(LinkedQueue<T>* linkedQueue) { cout << "$ 执行判断队列是否为空函数，IsEmpty = " << linkedQueue->IsEmpty() << endl; } //判断队列是否为满 template <class T> void isfull(LinkedQueue<T>* linkedQueue) { cout << "$ 执行判断队列是否为满函数，IsFull = " << linkedQueue->IsFull() << endl; } //清空队列的内容 template <class T> void makeempty(LinkedQueue<T>* linkedQueue) { cout << "$ 执行清空队列的内容函数" << endl; linkedQueue->MakeEmpty(); } //计算队列中元素个数 template <class T> void getsize(LinkedQueue<T>* linkedQueue) { cout << "$ 执行计算队列中元素个数函数，Size = " << linkedQueue->getSize() << endl; } //输出队列元素的重载操作<< template <class T> void operator_ostream(LinkedQueue<T>* linkedQueue) { cout << "$ 执行输出队列元素的重载操作<<函数" << endl; cout << *linkedQueue;//或operator<<(cout, *linkedQueue); } //链式队列操作选择 template <class T> void select_operation(LinkedQueue<T>* linkedQueue) { if (NULL == linkedQueue) { cout << "* 没有构造链式队列，请先构造链式队列。" << endl; return; } string s_operation; while (s_operation != "0") { cout << " ==> 请输入功能选项编号(按"0"退出程序)："; cin >> s_operation; while (false == IsNumber(s_operation)) { cout << "* 输入有误，请重新输入："; cin >> s_operation; } int n_operation = atoi(s_operation.c_str()); switch (n_operation) { case EXIT://退出 { cout << "$ 退出程序" << endl; break; } case GETHEAD://读取队头元素，并将该元素的值保存至x { gethead(linkedQueue); break; } case ENQUEUE://新元素x入队 { enqueue(linkedQueue); break; } case DEQUEUE://队头元素出队，并将该元素的值保存至x { dequeue(linkedQueue); break; } case ISEMPTY://判断队列是否为空 { isempty(linkedQueue); break; } case ISFULL://判断队列是否为满 { isfull(linkedQueue); break; } case MAKEEMPTY://清空队列的内容 { makeempty(linkedQueue); break; } case GETSIZE://计算队列元素个数 { getsize(linkedQueue); break; } case OPERATOR_OSTREAM://输出队列元素的重载操作<< { operator_ostream(linkedQueue); break; } default: { cout << "* 请输入正确的功能选项编号" << endl; break; } } } } int main(int argc, char* argv[]) { print_description(); LinkedQueue<int> *linkedQueue = construct_linkedqueue<int>(); select_operation(linkedQueue); destory_linkedqueue(linkedQueue); system("pause"); return 0; }
参考文献：
[1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第三章
[2]《C/C++常用算法手册》秦姣华、向旭宇——第二章
[3] 百度搜索关键字：链式队列