优先级队列(Priority Queue)

优先级队列(Priority Queue)

注：队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。

1. 优先级队列的概念

1.1 优先级队列的定义

1.2 优先级队列的特点

2. 最小优先级队列的实现——基于一维数组的存储表示

2.1 最小优先级队列的类定义及其操作的实现

文件：PriorityQueue.h

#ifndef PRIORITY_QUEUE_H_#define PRIORITY_QUEUE_H_#include <iostream>#include <string>#include <strstream>using namespace std;const int defaultSize = 50;template <class T>class PriorityQueue{public:PriorityQueue(int sz = defaultSize); //构造函数~PriorityQueue(); //析构函数public:bool getHead(T& x) const; //读取队头(具最小优先权)的值bool Insert(const T& x); //将新元素x插入到队尾bool RemoveMin(T& x); //将队头元素删除 bool IsEmpty() const; //判断队列是否为空bool IsFull() const; //判断队列是否为满void MakeEmpty();//置优先级队列为空int getSize() const; //求优先级队列中元素个数public:template <class T>friend ostream& operator<<(ostream& os, const PriorityQueue<T>& q); //输出队列元素的重载操作<<private:void adjust(); //队列调整private:T *pqelements; //存放队列元素的队列数组int maxSize; //队列最大可容纳元素个数int count;//当前元素个数(长度)};//构造函数template <class T>PriorityQueue<T>::PriorityQueue(int sz){cout << "$ 执行构造函数" << endl;if (sz >= 0){maxSize = sz; count = 0;pqelements = new T[maxSize];}} //析构函数template <class T>PriorityQueue<T>::~PriorityQueue(){cout << "$ 执行析构函数" << endl;delete[] pqelements;pqelements = NULL;} //读取队头(具最小优先权)的值template <class T>bool PriorityQueue<T>::getHead(T& x) const{if (true == IsEmpty()){return false;}x = pqelements[0];return true;}//将新元素x插入到队尾template <class T>bool PriorityQueue<T>::Insert(const T& x){if (true == IsFull()){return false;}pqelements[count++] = x;adjust(); //按优先权进行调整return true;}//将队头元素删除template <class T>bool PriorityQueue<T>::RemoveMin(T& x){if (true == IsEmpty()){return false;}x = pqelements[0];for (int i = 1; i < count; i++){pqelements[i - 1] = pqelements[i];}count--;return true;}//判断队列是否为空template <class T>bool PriorityQueue<T>::IsEmpty() const{return (0 == count) ? true : false;}//判断队列是否为满template <class T>bool PriorityQueue<T>::IsFull() const{return (maxSize == count) ? true : false;}//置优先级队列为空template <class T>void PriorityQueue<T>::MakeEmpty(){delete[] pqelements;count = 0;pqelements = new T[maxSize];}//求优先级队列中元素个数template <class T>int PriorityQueue<T>::getSize() const{return count;}//输出队列元素的重载操作<<template <class T>ostream& operator<<(ostream& os, const PriorityQueue<T>& q){for (int i = 0; i < q.count; i++){os << "[" << i << "]" << " : " << q.pqelements[i] << endl;}return os;}//队列调整template <class T>void PriorityQueue<T>::adjust(){int i = 0;T temp = pqelements[count - 1];for (i = count - 2; i >= 0; i--){if (pqelements[i] <= temp){break;}pqelements[i + 1] = pqelements[i];}pqelements[i + 1] = temp;}#endif /* PRIORITY_QUEUE_H_ */

2.2 主函数(main函数)的实现

文件：main.cpp

#include "PriorityQueue.h"#define EXIT 0 //退出#define GETHEAD 1 //读取队头(具最小优先权)的值#define INSERT 2 //将新元素x插入到队尾#define REMOVEMIN 3//将队头元素删除#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： 读取队头(具最小优先权)的值" << endl;cout << "#2： 将新元素x插入到队尾" << endl;cout << "#3： 将队头元素删除" << endl;cout << "#4： 判断队列是否为空" << endl;cout << "#5： 判断队列是否为满" << endl;cout << "#6： 置优先级队列为空" << endl;cout << "#7： 求优先级队列中元素个数" << endl;cout << "#8： 输出队列元素的重载操作<<" << endl;cout << "--------------------------------------------------------------------" << endl;}//判断输入的字符串每个字符是否都是数值0~9bool 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型转为模板类型Ttemplate <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>int get_maxsize(){cout << "> 请输入数组的最大长度，maxsize = ";string s_maxsize;cin >> s_maxsize;while (false == IsNumber(s_maxsize)){cout << "* 输入有误，请重新输入：";cin >> s_maxsize;}return atoi(s_maxsize.c_str());}//构造优先级队列template <class T>PriorityQueue<T>* construct_priorityqueue(){cout << "\n==> 创建优先级队列" << endl;int n_maxsize = get_maxsize<T>();PriorityQueue<T> *priorityQueue = new PriorityQueue<T>(n_maxsize);return priorityQueue;}//析构优先级队列template <class T>void destory_priorityqueue(PriorityQueue<T>* priorityQueue){cout << "\n==> 释放优先级队列在堆中申请的空间，并将指向该空间的指针变量置为空" << endl;delete priorityQueue;priorityQueue = NULL;}//读取队头(具最小优先权)的值template <class T>void gethead(PriorityQueue<T>* priorityQueue){cout << "$ 执行读取队头(具最小优先权)的值函数" << endl;T data;if (false == priorityQueue->getHead(data)){cout << "* 读取队头元素失败" << endl;return;}cout << "* 读取队头元素成功，data = " << data << endl;}//将新元素x插入到队尾template <class T> void insert(PriorityQueue<T>* priorityQueue){cout << "$ 执行将新元素x插入到队尾函数" << endl;T data = get_data<T>();if (false == priorityQueue->Insert(data)){cout << "* 入队失败" << endl;return;}cout << "* 入队成功，data = " << data << endl;}//将队头元素删除template <class T> void removemin(PriorityQueue<T>* priorityQueue){cout << "$ 执行将队头元素删除函数" << endl;T data;if (false == priorityQueue->RemoveMin(data)){cout << "* 出队失败" << endl;return;}cout << "* 出队成功，data = " << data << endl;}//判断队列是否为空template <class T> void isempty(PriorityQueue<T>* priorityQueue){cout << "$ 执行判断队列是否为空函数，IsEmpty = " << priorityQueue->IsEmpty() << endl;}//判断队列是否为满template <class T> void isfull(PriorityQueue<T>* priorityQueue){cout << "$ 执行判断队列是否为满函数，IsFull = " << priorityQueue->IsFull() << endl;}//置优先级队列为空template <class T>void makeempty(PriorityQueue<T>* priorityQueue){cout << "$ 执行置优先级队列为空函数" << endl;priorityQueue->MakeEmpty();}//求优先级队列中元素个数template <class T> void getsize(PriorityQueue<T>* priorityQueue){cout << "$ 执行求优先级队列中元素个数函数，Size = " << priorityQueue->getSize() << endl;}//输出队列元素的重载操作<<template <class T>void operator_ostream(PriorityQueue<T>* priorityQueue){cout << "$ 执行输出队列元素的重载操作<<函数" << endl;cout << *priorityQueue;//或operator<<(cout, *priorityQueue);}//优先级队列操作选择template <class T>void select_operation(PriorityQueue<T>* priorityQueue){if (NULL == priorityQueue){cout << "* 没有构造优先级队列，请先构造优先级队列。" << endl;return;}string s_operation;while (s_operation != "0"){cout << "\n==> 请输入功能选项编号(按\"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://读取队头(具最小优先权)的值{gethead(priorityQueue);break;}case INSERT://将新元素x插入到队尾{insert(priorityQueue);break;}case REMOVEMIN://将队头元素删除{removemin(priorityQueue);break;}case ISEMPTY://判断队列是否为空{isempty(priorityQueue);break;}case ISFULL://判断队列是否为满{isfull(priorityQueue);break;}case MAKEEMPTY://置优先级队列为空{makeempty(priorityQueue);break;}case GETSIZE://求优先级队列中元素个数{getsize(priorityQueue);break;}case OPERATOR_OSTREAM://输出队列元素的重载操作<<{operator_ostream(priorityQueue);break;}default:{cout << "* 请输入正确的功能选项编号" << endl;break;}}}}int main(int argc, char* argv[]){print_description();PriorityQueue<int> *priorityQueue = construct_priorityqueue<int>();select_operation(priorityQueue);destory_priorityqueue(priorityQueue);system("pause");return 0;}

3. 最小优先级队列的实现——基于单链表的存储表示

3.1 最小优先级队列的类定义及其操作的实现

文件：PriorityQueue.h

#ifndef PRIORITY_QUEUE_H_#define PRIORITY_QUEUE_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; }};template <class T>class PriorityQueue{public:PriorityQueue();//构造函数~PriorityQueue();//析构函数public:bool getHead(T& x) const; //读取队头(具最小优先权)的值bool Insert(const T& x); //将新元素x插入到队尾bool RemoveMin(T& x); //将队头元素删除 bool IsEmpty() const; //判断队列是否为空bool IsFull() const; //判断队列是否为满void MakeEmpty();//置优先级队列为空int getSize() const; //求优先级队列中元素个数public:template <class T>friend ostream& operator<<(ostream& os, const PriorityQueue<T>& q); //输出队列中元素的重载操作<<private:void adjust(LinkNode<T> *newNode); //队列调整private:LinkNode<T> *front; //队头指针，即链头指针};//构造函数template <class T>PriorityQueue<T>::PriorityQueue(): front(NULL){cout << "$ 执行构造函数" << endl;} //析构函数template <class T>PriorityQueue<T>::~PriorityQueue(){cout << "$ 执行析构函数" << endl;MakeEmpty();} //读取队头(具最小优先权)的值template <class T>bool PriorityQueue<T>::getHead(T& x) const{if (true == IsEmpty()){return false;}x = front->data;return true;}//将新元素x插入到队尾template <class T>bool PriorityQueue<T>::Insert(const T& x){LinkNode<T> *newNode = new LinkNode<T>(x);if (NULL == newNode){return false;}if (NULL == front){front = newNode;return true;}adjust(newNode);return true;}//将队头元素删除template <class T>bool PriorityQueue<T>::RemoveMin(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 PriorityQueue<T>::IsEmpty() const{return (NULL == front) ? true : false;}//判断队列是否为满template <class T>bool PriorityQueue<T>::IsFull() const{return false;}//置优先级队列为空template <class T>void PriorityQueue<T>::MakeEmpty(){LinkNode<T> *curNode = NULL;while (NULL != front) //当链表不为空时，删去链表中所有结点{curNode = front; //保存被删结点front = curNode->link;//被删结点的下一个结点成为头结点delete curNode; //从链表上摘下被删结点}}//求优先级队列中元素个数template <class T>int PriorityQueue<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 PriorityQueue<T>& q){int i = 0;LinkNode<T> *curNode = q.front;while (NULL != curNode){os << "[" << i++ << "]" << " : " << curNode->data << endl;curNode = curNode->link;}return os;}//队列调整template <class T>void PriorityQueue<T>::adjust(LinkNode<T> *newNode){LinkNode<T> *preNode = NULL;LinkNode<T> *curNode = front;while (NULL != curNode){if (curNode->data > newNode->data){break;}preNode = curNode;curNode = curNode->link;}if (preNode == NULL){newNode->link = curNode;front = newNode;}else{preNode->link = newNode;newNode->link = curNode;}}#endif /* PRIORITY_QUEUE_H_ */

3.2 主函数(main函数)的实现

文件：main.cpp

#include "PriorityQueue.h"#define EXIT 0 //退出#define GETHEAD 1 //读取队头(具最小优先权)的值#define INSERT 2 //将新元素x插入到队尾#define REMOVEMIN 3//将队头元素删除#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： 读取队头(具最小优先权)的值" << endl;cout << "#2： 将新元素x插入到队尾" << endl;cout << "#3： 将队头元素删除" << endl;cout << "#4： 判断队列是否为空" << endl;cout << "#5： 判断队列是否为满" << endl;cout << "#6： 置优先级队列为空" << endl;cout << "#7： 求优先级队列中元素个数" << endl;cout << "#8： 输出队列元素的重载操作<<" << endl;cout << "--------------------------------------------------------------------" << endl;}//判断输入的字符串每个字符是否都是数值0~9bool 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型转为模板类型Ttemplate <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>PriorityQueue<T>* construct_priorityqueue(){cout << "\n==> 创建优先级队列" << endl;PriorityQueue<T> *priorityQueue = new PriorityQueue<T>;return priorityQueue;}//析构优先级队列template <class T>void destory_priorityqueue(PriorityQueue<T>* priorityQueue){cout << "\n==> 释放优先级队列在堆中申请的空间，并将指向该空间的指针变量置为空" << endl;delete priorityQueue;priorityQueue = NULL;}//读取队头(具最小优先权)的值template <class T>void gethead(PriorityQueue<T>* priorityQueue){cout << "$ 执行读取队头(具最小优先权)的值函数" << endl;T data;if (false == priorityQueue->getHead(data)){cout << "* 读取队头元素失败" << endl;return;}cout << "* 读取队头元素成功，data = " << data << endl;}//将新元素x插入到队尾template <class T>void insert(PriorityQueue<T>* priorityQueue){cout << "$ 执行将新元素x插入到队尾函数" << endl;T data = get_data<T>();if (false == priorityQueue->Insert(data)){cout << "* 入队失败" << endl;return;}cout << "* 入队成功，data = " << data << endl;}//将队头元素删除template <class T>void removemin(PriorityQueue<T>* priorityQueue){cout << "$ 执行将队头元素删除函数" << endl;T data;if (false == priorityQueue->RemoveMin(data)){cout << "* 出队失败" << endl;return;}cout << "* 出队成功，data = " << data << endl;}//判断队列是否为空template <class T>void isempty(PriorityQueue<T>* priorityQueue){cout << "$ 执行判断队列是否为空函数，IsEmpty = " << priorityQueue->IsEmpty() << endl;}//判断队列是否为满template <class T>void isfull(PriorityQueue<T>* priorityQueue){cout << "$ 执行判断队列是否为满函数，IsFull = " << priorityQueue->IsFull() << endl;}//置优先级队列为空template <class T>void makeempty(PriorityQueue<T>* priorityQueue){cout << "$ 执行置优先级队列为空函数" << endl;priorityQueue->MakeEmpty();}//求优先级队列中元素个数template <class T>void getsize(PriorityQueue<T>* priorityQueue){cout << "$ 执行求优先级队列中元素个数函数，Size = " << priorityQueue->getSize() << endl;}//输出队列元素的重载操作<<template <class T>void operator_ostream(PriorityQueue<T>* priorityQueue){cout << "$ 执行输出队列元素的重载操作<<函数" << endl;cout << *priorityQueue;//或operator<<(cout, *priorityQueue);}//优先级队列操作选择template <class T>void select_operation(PriorityQueue<T>* priorityQueue){if (NULL == priorityQueue){cout << "* 没有构造优先级队列，请先构造优先级队列。" << endl;return;}string s_operation;while (s_operation != "0"){cout << "\n==> 请输入功能选项编号(按\"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://读取队头(具最小优先权)的值{gethead(priorityQueue);break;}case INSERT://将新元素x插入到队尾{insert(priorityQueue);break;}case REMOVEMIN://将队头元素删除{removemin(priorityQueue);break;}case ISEMPTY://判断队列是否为空{isempty(priorityQueue);break;}case ISFULL://判断队列是否为满{isfull(priorityQueue);break;}case MAKEEMPTY://置优先级队列为空{makeempty(priorityQueue);break;}case GETSIZE://求优先级队列中元素个数{getsize(priorityQueue);break;}case OPERATOR_OSTREAM://输出队列元素的重载操作<<{operator_ostream(priorityQueue);break;}default:{cout << "* 请输入正确的功能选项编号" << endl;break;}}}}int main(int argc, char* argv[]){print_description();PriorityQueue<int> *priorityQueue = construct_priorityqueue<int>();select_operation(priorityQueue);destory_priorityqueue(priorityQueue);system("pause");return 0;}

参考文献：

[1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第三章

[2] 百度搜索关键字：优先级队列