STL priority_queue（優(yōu)先隊列）詳解

更新時間：2016年10月26日 11:17:03 投稿：lqh

這篇文章主要介紹了 STL priority_queue（優(yōu)先隊列）詳解的相關資料,需要的朋友可以參考下

構(gòu)造，析構(gòu)

priority_queue() //默認構(gòu)造函數(shù)，生成一個空的排序隊列 

priority_queue(const queue&); //拷貝構(gòu)造函數(shù) 

priority_queue(const Compare& comp);
//構(gòu)造生成一個空的priority_queue對象，
//使用comp作為priority_queue的comparison 

priority_queue(const value_type* first, const value_type* last); 
//帶有兩個參數(shù)的構(gòu)造函數(shù)， 
//使用默認的Comparison作為第三個參數(shù) 

priority_queue& operator=(const priority_queue &);  
//賦值運算符重載 

c.~priority_queue() //銷毀所有元素并釋放內(nèi)存

### 常用函數(shù)###

empty();//判斷是否為空 

push(Elem e);//隊列尾部增加一元素 

pop();//隊列頭部數(shù)據(jù)出隊 

top();//返回頭部數(shù)據(jù) 

size();//返回棧中元素個數(shù)

### 改變排列順序###
priority_queue < Type, Container, Functional >
如果我們把后面?zhèn)z個參數(shù)缺省的話，優(yōu)先隊列就是大頂堆，
隊頭元素最大。在很多時候，我們需要的不一定是最大值，
也有可能是最小值。這是就需要我們來改變priority_queue中的順序。

方法有兩種：
1.如果加入優(yōu)先隊列的是基本類型，那么我們就可以這樣，我們以int為例：

//注意greater<int> >這之間有一個空格
priority_queue<int, vector<int>, greater<int> >Q;

2.對于自定義數(shù)據(jù)類型的話，我們不論是要改變排序方式，還是不改變都要這樣 – 重載小于( < ) 運算符：
因為，如果你不重載比較運算符的話，編譯器無法比較自定義數(shù)據(jù)類型的大小關系。然而又因為在priority_queue的內(nèi)部，只需用到小于號（<），所以我們只需要重載小于號即可。當然對于自定義數(shù)據(jù)類型來說，也是必須重載，否則將無法使用priority_queue。重載小于號，我們可以有兩種方式，一種用成員函數(shù)，一種使用友元函數(shù)（這里就不多說了，不會的同學，自己在好好復習復習C++）

### 優(yōu)先隊列的使用范例###

#include <queue> 
#include <list> 
#include <cstdio> 
using namespace std; 
/** 
 優(yōu)先級隊列的使用范例 
*/ 
int main(){ 
  //優(yōu)先隊列默認是使用vector作為容器 
  priority_queue<int> a; 
  // priority_queue<int,list<int>> b;//可以這樣定義，但無法使用 
  int i; 
  //壓入數(shù)據(jù) 
  for(i=0;i<10;i++){ 
   a.push(i*2-5); 
   //b.push(i);//編譯錯誤 
  } 
  printf("優(yōu)先隊列的大小=%d\n",a.size()); 
  while(!a.empty()){ 
    printf("%d\n",a.top()); 
    a.pop();//出隊 
  } 
  putchar('\n'); 
  return 0; 
}

### 優(yōu)先隊列帶比較函數(shù)示例（針對結(jié)構(gòu)體）###

下面程序是針對結(jié)構(gòu)體的，對數(shù)據(jù)的比較是通過對結(jié)構(gòu)體重載operator()。
程序功能是模擬排隊過程，每人有姓名和優(yōu)先級，優(yōu)先級相同則比較姓名，開始有5個人進入隊列，然后隊頭2個人出隊，再有3個人進入隊列，最后所有人都依次出隊，程序會輸出離開隊伍的順序

#include <queue> 
#include <cstring> 
#include <cstdio> 
using namespace std; 
/** 
 結(jié)構(gòu)體 
*/ 
struct Node{ 
  char szName[20];//人名 
  int priority;//優(yōu)先級 
  //構(gòu)造函數(shù) 
  Node(int nri, char *pszName){ 
    strcpy(szName, pszName); 
    priority = nri; 
  } 
}; 
/** 
 結(jié)構(gòu)體的比較方法 改寫operator() 
*/ 
struct NodeCmp{ 
//重寫operator()方法,注意這里重寫的寫法，operator()(參數(shù)1，...) 
  bool operator()(const Node &na, const Node &nb){ 
    if (na.priority != nb.priority) 
      return na.priority <= nb.priority; 
    else 
      return strcmp(na.szName, nb.szName) > 0; 
  } 
}; 
/** 
 打印節(jié)點 
*/ 
void PrintfNode(Node na){ 
  printf("%s %d\n", na.szName, na.priority); 
} 
int main(){ 
  //優(yōu)先級隊列默認是使用vector作容器，底層數(shù)據(jù)結(jié)構(gòu)為堆。 
  priority_queue<Node, vector<Node>, NodeCmp> a; 

  //有5個人進入隊列 
  a.push(Node(5, "小譚")); 
  a.push(Node(3, "小劉")); 
  a.push(Node(1, "小濤")); 
  a.push(Node(5, "小王")); 

  //隊頭的2個人出隊 
  PrintfNode(a.top()); 
  a.pop(); 
  PrintfNode(a.top()); 
  a.pop(); 
  printf("--------------------\n"); 

  //再進入3個人 
  a.push(Node(2, "小白")); 
  a.push(Node(2, "小強")); 
  a.push(Node(3, "小新")); 

  //所有人都依次出隊 
  while (!a.empty()){ 
    PrintfNode(a.top()); 
    a.pop(); 
  } 
  return 0; 
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章: