首页 > 程序开发 > 软件开发 > 其他 >

优先级队列(Priority Queue)

2016-06-06

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

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

1. 优先级队列的概念

1.1 优先级队列的定义

优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

1.2 优先级队列的特点

优先级队列是0个或多个元素的集合,每个元素都有一个优先权或值。 当给每个元素分配一个数字来标记其优先级,不妨设较小的数字具有较高的优先级,这样就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。 对优先级队列,执行的操作主要有:(1)查找,(2)插入,(3)删除。 在最小优先级队列(min Priority Queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素。 在最大优先级队列(max Priority Queue)中,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素。 插入操作均只是简单地把一个新的元素加入到队列中。 注:每个元素的优先级根据问题的要求而定。当从优先级队列中删除一个元素时,可能出现多个元素具有相同的优先权。在这种情况下,把这些具有相同优先权的元素视为一个先来先服务的队列,按他们的入队顺序进行先后处理。

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

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

文件:PriorityQueue.h


#ifndef PRIORITY_QUEUE_H_


#define PRIORITY_QUEUE_H_



#include 


#include 


#include 


using namespace std;

const int defaultSize = 50;

template 
class PriorityQueue
{
public:
    PriorityQueue(int sz = defaultSize);        //构造函数
    ~PriorityQueue();                           //析构函数
public:
    bool Insert(const T& x);        //将新元素x插入到队尾
    bool RemoveMin(T& x);           //将队头元素删除
    bool getFront(T& x) const;      //读取队头(具最小优先权)的值
    void MakeEmpty();               //置优先级队列为空
    bool IsEmpty() const;           //判断队列是否为空
    bool IsFull() const;            //判断队列是否为满
    int getSize() const;            //求优先级队列中元素个数
public:
    template 
    friend ostream& operator<<(ostream& os, const PriorityQueue& q); //输出队列元素的重载操作<<
private:
    void adjust();                  //队列调整
private:
    T *pqelements;  //存放队列元素的队列数组
    int maxSize;    //队列最大可容纳元素个数
    int count;      //当前元素个数(长度)
};

//构造函数
template 
PriorityQueue::PriorityQueue(int sz)
{
    cout << "$ 执行构造函数" << endl;
    if (sz >= 0)
    {
        maxSize = sz;           
        count = 0;      
        pqelements = new T[maxSize];
    }
}                       

//析构函数
template 
PriorityQueue::~PriorityQueue()
{
    cout << "$ 执行析构函数" << endl;
    delete[] pqelements;
    pqelements = NULL;
}   

//将新元素x插入到队尾
template 
bool PriorityQueue::Insert(const T& x)
{
    if (true == IsFull())
    {
        return false;
    }
    pqelements[count++] = x;
    adjust();   //按优先权进行调整
    return true;
}

//将队头元素删除
template 
bool PriorityQueue::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 
bool PriorityQueue::getFront(T& x) const
{
    if (true == IsEmpty())
    {
        return false;
    }
    x = pqelements[0];
    return true;
}

//置优先级队列为空
template 
void PriorityQueue::MakeEmpty()
{
    delete[] pqelements;
    count = 0;
    pqelements = new T[maxSize];
}

//判断队列是否为空
template 
bool PriorityQueue::IsEmpty() const
{
    return (0 == count) ? true : false;
}

//判断队列是否为满
template 
bool PriorityQueue::IsFull() const
{
    return (maxSize == count) ? true : false;
}

//求优先级队列中元素个数
template 
int PriorityQueue::getSize() const
{
    return count;
}

//输出队列元素的重载操作<<
template 
ostream& operator<<(ostream& os, const PriorityQueue& q)
{
    for (int i = 0; i < q.count; i++)
    {
        os << "[" << i << "]" << " : " << q.pqelements[i] << endl;
    }
    return os;
}

//队列调整
template 
void PriorityQueue::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 INSERT 1            //将新元素x插入到队尾


#define REMOVEMIN    2      //将队头元素删除


#define GETFRONT 3          //读取队头(具最小优先权)的值


#define MAKEEMPTY 4         //置优先级队列为空


#define ISEMPTY  5          //判断队列是否为空


#define ISFULL 6            //判断队列是否为满


#define GETSIZE 7           //求优先级队列中元素个数


#define OPERATOR_OSTREAM 8  //输出队列元素的重载操作<<


void print_description()
{
    cout << "------------------------------>优先级队列<------------------------------" << endl;
    cout << "功能选项说明:" << endl;
    cout << "#0: 退出" << endl;
    cout << "#1: 将新元素x插入到队尾" << endl;
    cout << "#2: 将队头元素删除" << endl;
    cout << "#3: 读取队头(具最小优先权)的值" << 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] < &#39;0&#39;) || (s_num[i] > &#39;9&#39;))
        {
            return false;
        }
    }
    return true;
}

//类型转换——将string型转为模板类型T
template 
T StrToTtype(const string& s_num)
{
    T n_num;
    strstream ss_num;
    ss_num << s_num;
    ss_num >> n_num;
    return n_num;
}

//输入数据值
template 
T get_data()
{
    cout << "> 请输入数据值,data = ";
    string s_data;
    cin >> s_data;
    return StrToTtype(s_data);
}

//输入数组的最大长度
template 
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 
PriorityQueue* construct_priorityqueue()
{
    cout << "\n==> 创建优先级队列" << endl;
    int n_maxsize = get_maxsize();
    PriorityQueue *priorityQueue = new PriorityQueue(n_maxsize);
    return priorityQueue;
}

//析构优先级队列
template 
void destory_priorityqueue(PriorityQueue* priorityQueue)
{
    cout << "\n==> 释放优先级队列在堆中申请的空间,并将指向该空间的指针变量置为空" << endl;
    delete priorityQueue;
    priorityQueue = NULL;
}

//将新元素x插入到队尾
template               
void insert(PriorityQueue* priorityQueue)
{
    cout << "$ 执行将新元素x插入到队尾函数" << endl;
    T data = get_data();
    if (false == priorityQueue->Insert(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功,data = " << data << endl;
}

//将队头元素删除
template   
void removemin(PriorityQueue* priorityQueue)
{
    cout << "$ 执行将队头元素删除函数" << endl;
    T data;
    if (false == priorityQueue->RemoveMin(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功,data = " << data << endl;
}

//读取队头(具最小优先权)的值
template   
void getfront(PriorityQueue* priorityQueue)
{
    cout << "$ 执行读取队头(具最小优先权)的值函数" << endl;
    T data;
    if (false == priorityQueue->getFront(data))
    {
        cout << "* 读取队头元素失败" << endl;
        return;
    }
    cout << "* 读取队头元素成功,data = " << data << endl;
}

//置优先级队列为空
template 
void makeempty(PriorityQueue* priorityQueue)
{
    cout << "$ 执行置优先级队列为空函数" << endl;
    priorityQueue->MakeEmpty();
}

//判断队列是否为空
template   
void isempty(PriorityQueue* priorityQueue)
{
    cout << "$ 执行判断队列是否为空函数,IsEmpty = " << priorityQueue->IsEmpty() << endl;
}

//判断队列是否为满
template   
void isfull(PriorityQueue* priorityQueue)
{
    cout << "$ 执行判断队列是否为满函数,IsFull = " << priorityQueue->IsFull() << endl;
}

//求优先级队列中元素个数
template   
void getsize(PriorityQueue* priorityQueue)
{
    cout << "$ 执行求优先级队列中元素个数函数,Size = " << priorityQueue->getSize() << endl;
}

//输出队列元素的重载操作<<
template 
void operator_ostream(PriorityQueue* priorityQueue)
{
    cout << "$ 执行输出队列元素的重载操作<<函数" << endl;
    cout << *priorityQueue;//或operator<<(cout, *priorityQueue);
}

//优先级队列操作选择
template 
void select_operation(PriorityQueue* 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 INSERT://将新元素x插入到队尾
            {
                insert(priorityQueue);
                break;
            }
            case REMOVEMIN://将队头元素删除
            {
                removemin(priorityQueue);
                break;
            }
            case GETFRONT://读取队头(具最小优先权)的值
            {
                getfront(priorityQueue);
                break;
            }
            case MAKEEMPTY://置优先级队列为空
            {
                makeempty(priorityQueue);
                break;
            }
            case ISEMPTY://判断队列是否为空
            {
                isempty(priorityQueue);
                break;
            }
            case ISFULL://判断队列是否为满
            {
                isfull(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 *priorityQueue = construct_priorityqueue();
    select_operation(priorityQueue);
    destory_priorityqueue(priorityQueue);
    system("pause");
    return 0;
}

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

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

文件:PriorityQueue.h


#ifndef PRIORITY_QUEUE_H_


#define PRIORITY_QUEUE_H_



#include 


#include 


#include 


using namespace std;

template 
struct LinkNode         //链表结点类的定义
{
    T data;             //数据域
    LinkNode *link;  //指针域——后继指针
    //仅初始化指针成员的构造函数
    LinkNode(LinkNode* ptr = NULL){ link = ptr; }
    //初始化数据与指针成员的构造函数
    LinkNode(const T& value, LinkNode* ptr = NULL){ data = value; link = ptr; }
};

template 
class PriorityQueue
{
public:
    PriorityQueue();                //构造函数
    ~PriorityQueue();               //析构函数
public:
    bool Insert(const T& x);        //将新元素x插入到队尾
    bool RemoveMin(T& x);           //将队头元素删除
    bool getFront(T& x) const;      //读取队头(具最小优先权)的值
    void MakeEmpty();               //置优先级队列为空
    bool IsEmpty() const;           //判断队列是否为空
    bool IsFull() const;            //判断队列是否为满
    int getSize() const;            //求优先级队列中元素个数
public:
    template 
    friend ostream& operator<<(ostream& os, const PriorityQueue& s); //输出队列中元素的重载操作<<
private:
    void adjust(LinkNode *newNode);  //队列调整
private:
    LinkNode *front; //队头指针,即链头指针
};

//构造函数
template 
PriorityQueue::PriorityQueue()
: front(NULL)
{
    cout << "$ 执行构造函数" << endl;
}                       

//析构函数
template 
PriorityQueue::~PriorityQueue()
{
    cout << "$ 执行析构函数" << endl;
    MakeEmpty();
}   

//将新元素x插入到队尾
template 
bool PriorityQueue::Insert(const T& x)
{
    LinkNode *newNode = new LinkNode(x);
    if (NULL == newNode)
    {
        return false;
    }

    if (NULL == front)
    {
        front = newNode;
        return true;
    }
    adjust(newNode);
    return true;
}

//将队头元素删除
template 
bool PriorityQueue::RemoveMin(T& x)
{
    if (true == IsEmpty())
    {
        return false;
    }
    LinkNode *curNode = front;
    front = front->link;
    x = curNode->data;
    delete curNode;
    return true;
}

//读取队头(具最小优先权)的值
template 
bool PriorityQueue::getFront(T& x) const
{
    if (true == IsEmpty())
    {
        return false;
    }
    x = front->data;
    return true;
}

//置优先级队列为空
template 
void PriorityQueue::MakeEmpty()
{
    LinkNode *curNode = NULL;
    while (NULL != front)           //当链表不为空时,删去链表中所有结点
    {
        curNode = front;            //保存被删结点
        front = curNode->link;      //被删结点的下一个结点成为头结点
        delete curNode;             //从链表上摘下被删结点
    }
}

//判断队列是否为空
template 
bool PriorityQueue::IsEmpty() const
{
    return (NULL == front) ? true : false;
}

//判断队列是否为满
template 
bool PriorityQueue::IsFull() const
{
    return false;
}

//求优先级队列中元素个数
template 
int PriorityQueue::getSize() const
{
    int count = 0;
    LinkNode *curNode = front;
    while (NULL != curNode)
    {
        curNode = curNode->link;
        count++;
    }
    return count;
}

//输出队列中元素的重载操作<<
template 
ostream& operator<<(ostream& os, const PriorityQueue& s)
{
    int i = 0;
    LinkNode *curNode = s.front;
    while (NULL != curNode)
    {
        os << "[" << i++ << "]" << " : " << curNode->data << endl;
        curNode = curNode->link;
    }
    return os;
}

//队列调整
template 
void PriorityQueue::adjust(LinkNode *newNode)
{
    LinkNode *preNode = NULL;
    LinkNode *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 INSERT 1            //将新元素x插入到队尾


#define REMOVEMIN    2      //将队头元素删除


#define GETFRONT 3          //读取队头(具最小优先权)的值


#define MAKEEMPTY 4         //置优先级队列为空


#define ISEMPTY  5          //判断队列是否为空


#define ISFULL 6            //判断队列是否为满


#define GETSIZE 7           //求优先级队列中元素个数


#define OPERATOR_OSTREAM 8  //输出队列元素的重载操作<<


void print_description()
{
    cout << "------------------------------>优先级队列<------------------------------" << endl;
    cout << "功能选项说明:" << endl;
    cout << "#0: 退出" << endl;
    cout << "#1: 将新元素x插入到队尾" << endl;
    cout << "#2: 将队头元素删除" << endl;
    cout << "#3: 读取队头(具最小优先权)的值" << 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] < &#39;0&#39;) || (s_num[i] > &#39;9&#39;))
        {
            return false;
        }
    }
    return true;
}

//类型转换——将string型转为模板类型T
template 
T StrToTtype(const string& s_num)
{
    T n_num;
    strstream ss_num;
    ss_num << s_num;
    ss_num >> n_num;
    return n_num;
}

//输入数据值
template 
T get_data()
{
    cout << "> 请输入数据值,data = ";
    string s_data;
    cin >> s_data;
    return StrToTtype(s_data);
}

//构造优先级队列
template 
PriorityQueue* construct_priorityqueue()
{
    cout << "\n==> 创建优先级队列" << endl;
    PriorityQueue *priorityQueue = new PriorityQueue;
    return priorityQueue;
}

//析构优先级队列
template 
void destory_priorityqueue(PriorityQueue* priorityQueue)
{
    cout << "\n==> 释放优先级队列在堆中申请的空间,并将指向该空间的指针变量置为空" << endl;
    delete priorityQueue;
    priorityQueue = NULL;
}

//将新元素x插入到队尾
template 
void insert(PriorityQueue* priorityQueue)
{
    cout << "$ 执行将新元素x插入到队尾函数" << endl;
    T data = get_data();
    if (false == priorityQueue->Insert(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功,data = " << data << endl;
}

//将队头元素删除
template 
void removemin(PriorityQueue* priorityQueue)
{
    cout << "$ 执行将队头元素删除函数" << endl;
    T data;
    if (false == priorityQueue->RemoveMin(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功,data = " << data << endl;
}

//读取队头(具最小优先权)的值
template 
void getfront(PriorityQueue* priorityQueue)
{
    cout << "$ 执行读取队头(具最小优先权)的值函数" << endl;
    T data;
    if (false == priorityQueue->getFront(data))
    {
        cout << "* 读取队头元素失败" << endl;
        return;
    }
    cout << "* 读取队头元素成功,data = " << data << endl;
}

//置优先级队列为空
template 
void makeempty(PriorityQueue* priorityQueue)
{
    cout << "$ 执行置优先级队列为空函数" << endl;
    priorityQueue->MakeEmpty();
}

//判断队列是否为空
template 
void isempty(PriorityQueue* priorityQueue)
{
    cout << "$ 执行判断队列是否为空函数,IsEmpty = " << priorityQueue->IsEmpty() << endl;
}

//判断队列是否为满
template 
void isfull(PriorityQueue* priorityQueue)
{
    cout << "$ 执行判断队列是否为满函数,IsFull = " << priorityQueue->IsFull() << endl;
}

//求优先级队列中元素个数
template 
void getsize(PriorityQueue* priorityQueue)
{
    cout << "$ 执行求优先级队列中元素个数函数,Size = " << priorityQueue->getSize() << endl;
}

//输出队列元素的重载操作<<
template 
void operator_ostream(PriorityQueue* priorityQueue)
{
    cout << "$ 执行输出队列元素的重载操作<<函数" << endl;
    cout << *priorityQueue;//或operator<<(cout, *priorityQueue);
}

//优先级队列操作选择
template 
void select_operation(PriorityQueue* 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 INSERT://将新元素x插入到队尾
            {
                insert(priorityQueue);
                break;
            }
            case REMOVEMIN://将队头元素删除
            {
                removemin(priorityQueue);
                break;
            }
            case GETFRONT://读取队头(具最小优先权)的值
            {
                getfront(priorityQueue);
                break;
            }
            case MAKEEMPTY://置优先级队列为空
            {
                makeempty(priorityQueue);
                break;
            }
            case ISEMPTY://判断队列是否为空
            {
                isempty(priorityQueue);
                break;
            }
            case ISFULL://判断队列是否为满
            {
                isfull(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 *priorityQueue = construct_priorityqueue();
    select_operation(priorityQueue);
    destory_priorityqueue(priorityQueue);
    system("pause");
    return 0;
}
相关文章
最新文章
热点推荐