2.13 priority_queue优先队列容器

priority_queue优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认为按元素的值由大到小排序；当然，可以重载“<”操作符来重新定义比较规则。

使用priority_queue需要声明头文件包含语句“#include <queue>”，它与queue队列共用一个头文件，queue文件在C:\Program Files\Microsoft Visual Studio\VC98\Include文件夹中。

2.13.1 优先队列的使用方法

优先队列包含入队push()（插入元素）、出队pop()（删除元素）、读取队首元素top()、判断队列是否为空empty()和读取队列元素数量size()等方法。

下面这个程序详细说明了优先队列的使用方法：

        #include <queue>
        #include <iostream>
        using namespace std;

       int main(int argc, char * argv[])
        {
          //定优先队列，元素类型为整型
          priority_queue<int> pq;
          //入队，插入新元素
          pq.push(1);
          pq.push(2);
          pq.push(3);
          pq.push(9);
          //返回队列中元素数目
          cout<<pq.size()<<endl;
          //所有元素出队，删除所有元素
          while(pq.empty()! =true)
          {
              //读取当前队首元素
              cout<<pq.top()<<" ";
              //出队，删除队首元素
              pq.pop();
          }
          //回车换行
          cout<<endl;
          return 0;
        }

运行结果：

        4
        9 3 2 1

2.13.2 重载“<”操作符来定义优先级

如果优先队列的元素类型是结构体，可以通过在结构体中重载“<”操作符的方法来修改优先队列的优先性。

下面这个程序很好地说明了如何在结构体中重载“<”操作符：

    #include <queue>
    #include <string>
    #include <iostream>
    using namespace std;

   //定义结构体
    struct Info{
      string name;
      float score;
      //重载“<”操作符，指定优先规则（排序规则）
      bool operator < (const Info &a) const
      {
          //按score由小到大排列。如果要由大到小排列，使用“>”号即可
          return a.score<score;
      }
    };
    int main(int argc, char * argv[])
    {
      //定义优先队列，元素类型为Info结构体
      priority_queue<Info> pq;
      //定义结构体变量
      Info info;

     //入队
      info.name="Jack";
      info.score=68.5;
      pq.push(info);

     info.name="Bomi";
      info.score=18.5;
      pq.push(info);

     info.name="Peti";
      info.score=90;
      pq.push(info);

     //元素全部出队
      while(pq.empty()! =true)
      {
          //返回队首元素
          cout<<pq.top().name<<" : "<<pq.top().score<<endl;
          //出队，删除队首元素
          pq.pop();
      }
      return 0;
    }

运行结果：

    Bomi : 18.5
    Jack : 68.5
    Peti : 90

2.13.3 重载“()”操作符来定义优先级

如果优先队列的元素不是结构体类型，则可以通过重载“()”操作符的方式来定义优先级。当然，元素是结构体类型，也可以通过重载“()”操作符的方式来定义优先级，而不是一定要在结构体内重载“<”操作符才行。

下面这个程序说明了如何重载“()”操作符：

        #include <queue>
        #include <vector>
        #include <iostream>
        using namespace std;

       //重载“()”操作符
        struct myComp
        {
          bool operator()(const int &a, const int &b)
          {
              //由小到大排列采用“>”号；如果要由大到小排列，则采用“<”号
              return a>b;
          }
        };

       int main(int argc, char * argv[])
        {
          //定义优先队列，元素类型为Info结构体，显式说明内部结构是vector
          priority_queue<int, vector<int>, myComp> pq;
          //入队
          pq.push(1);
          pq.push(9);
          pq.push(2);
          pq.push(30);
          //元素全部出队
          while(pq.empty()! =true)
          {
              //返回队首元素
              cout<<pq.top()<<" ";
              //出队，删除队首元素
              pq.pop();
          }
          cout<<endl;
          return 0;
        }

运行结果：

        1 2 9 30