優(yōu)先隊(duì)列(priority queue) 普通的隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊(duì)列尾追加，而從隊(duì)列頭刪除。在優(yōu)先隊(duì)列中，元素被賦予優(yōu)先級。當(dāng)訪問元素時，具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊(duì)列具有最高級先出 （first in, largest out）的行為特征。

優(yōu)先隊(duì)列是隊(duì)列的一種，不過它可以按照自定義的一種方式（數(shù)據(jù)的優(yōu)先級）來對隊(duì)列中的數(shù)據(jù)進(jìn)行動態(tài)的排序

每次的push和pop操作，隊(duì)列都會動態(tài)的調(diào)整，以達(dá)到我們預(yù)期的方式來存儲。

例如：我們常用的操作就是對數(shù)據(jù)排序，優(yōu)先隊(duì)列默認(rèn)的是數(shù)據(jù)大的優(yōu)先級高

所以我們無論按照什么順序push一堆數(shù)，最終在隊(duì)列里總是top出最大的元素。

?優(yōu)先隊(duì)列的常用操作

優(yōu)先級隊(duì)列支持的操作

q.empty()???????? 如果隊(duì)列為空，則返回true，否則返回false q.size()????????????返回隊(duì)列中元素的個數(shù) q.pop()???????????? 刪除隊(duì)首元素，但不返回其值 q.top()???????????? 返回具有最高優(yōu)先級的元素值，但不刪除該元素 q.push(item)???? 在基于優(yōu)先級的適當(dāng)位置插入新元素

用法：

示例：將元素5，3，2，4，6依次push到優(yōu)先隊(duì)列中，print其輸出。

1.?標(biāo)準(zhǔn)庫默認(rèn)使用元素類型的<操作符來確定它們之間的優(yōu)先級關(guān)系。

priority_queue<int> pq;

通過<操作符可知在整數(shù)中元素大的優(yōu)先級高。
故示例1中輸出結(jié)果為： 6 5 4 3 2

?

2. 數(shù)據(jù)越小，優(yōu)先級越高

priority_queue<int, vector<int>, greater<int> >pq;

其中
第二個參數(shù)為容器類型。
第二個參數(shù)為比較函數(shù)。
故示例2中輸出結(jié)果為：2 3 4 5 6

3. 自定義優(yōu)先級，重載比較符號

重載默認(rèn)的 < 符號

struct node {friend bool operator< (node n1, node n2){return n1.priority < n2.priority;}int priority;int value; };

這時，需要為每個元素自定義一個優(yōu)先級。

注：重載>號會編譯出錯，因?yàn)闃?biāo)準(zhǔn)庫默認(rèn)使用元素類型的<操作符來確定它們之間的優(yōu)先級關(guān)系。
而且自定義類型的<操作符與>操作符并無直接聯(lián)系

#include<iostream> #include<functional> #include<queue> using Namespace stdnamespace std; struct node {friend bool operator< (node n1, node n2){return n1.priority < n2.priority;}int priority;int value; }; int main() {const int len = 5;int i;int a[len] = {3,5,9,6,2};//示例1priority_queue<int> qi;for(i = 0; i < len; i++)qi.push(a[i]);for(i = 0; i < len; i++){cout<<qi.top()<<" ";qi.pop();}cout<<endl;//示例2priority_queue<int, vector<int>, greater<int> >qi2;for(i = 0; i < len; i++)qi2.push(a[i]);for(i = 0; i < len; i++){cout<<qi2.top()<<" ";qi2.pop();}cout<<endl;//示例3priority_queue<node> qn;node b[len];b[0].priority = 6; b[0].value = 1; b[1].priority = 9; b[1].value = 5; b[2].priority = 2; b[2].value = 3; b[3].priority = 8; b[3].value = 2; b[4].priority = 1; b[4].value = 4; for(i = 0; i < len; i++)qn.push(b[i]);cout<<"優(yōu)先級"<<'\t'<<"值"<<endl;for(i = 0; i < len; i++){cout<<qn.top().priority<<'\t'<<qn.top().value<<endl;qn.pop();}return 0; }
先級隊(duì)列可以用向量(vector)或雙向隊(duì)列(deque)來實(shí)現(xiàn)(注意list container 不能用來實(shí)現(xiàn)queue，因?yàn)閘ist 的迭代器不是任意存取iterator，而pop 中用到堆排序時是要求randomaccess iterator 的!)：
priority_queue<vector<int>, less<int>> pq1; // 使用遞增less<int>函數(shù)對象排序
priority_queue<deque<int>, greater<int>> pq2; // 使用遞減greater<int>函數(shù)對象排序
其成員函數(shù)有“判空(empty)” 、“尺寸(Size)” 、“棧頂元素(top)” 、“壓棧(push)” 、“彈棧(pop)”等。

例：
?1?#include?<iostream>
?2?#include?<queue>?
?3?using?namespace?std;
?4??
?5?class?T?{
?6?public:
?7?????int?x,?y,?z;?
?8?????T(int?a,?int?b,?int?c):x(a),?y(b),?z(c)
?9?????{?
10?????}
11?};
12?bool?operator?<?(const?T?&t1,?const?T?&t2)?
13?{
14?????return?t1.z?<?t2.z;?//?按照z的順序來決定t1和t2的順序
15?}?
16?main()
17?{?
18?????priority_queue<T>?q;?
19?????q.push(T(4,4,3));?
20?????q.push(T(2,2,5));?
21?????q.push(T(1,5,4));?
22?????q.push(T(3,3,6));?
23?????while?(!q.empty())?
24?????{?
25?????????T?t?=?q.top();?
26?????????q.pop();?
27?????????cout?<<?t.x?<<?"?"?<<?t.y?<<?"?"?<<?t.z?<<?endl;?
28?????}?
29?????return?1;?
30?} ????? 輸出結(jié)果為(注意是按照z的順序從大到小出隊(duì)的)：?
????? 3 3 6?
????? 2 2 5?
????? 1 5 4?
????? 4 4 3

????? 再看一個按照z的順序從小到大出隊(duì)的例子： ?1?#include?<iostream>?
?2?#include?<queue>?
?3?using?namespace?std;?
?4?class?T?
?5?{?
?6?public:?
?7?????int?x,?y,?z;?
?8?????T(int?a,?int?b,?int?c):x(a),?y(b),?z(c)?
?9?????{
10?????}?
11?};?
12?bool?operator?>?(const?T?&t1,?const?T?&t2)?
13?{?
14?????return?t1.z?>?t2.z;?
15?}?
16?main()?
17?{?
18?????priority_queue<T,?vector<T>,?greater<T>?>?q;?
19?????q.push(T(4,4,3));?
20?????q.push(T(2,2,5));?
21?????q.push(T(1,5,4));?
22?????q.push(T(3,3,6));?
23?????while?(!q.empty())?
24?????{?
25?????????T?t?=?q.top();?
26?????????q.pop();?
27?????????cout?<<?t.x?<<?"?"?<<?t.y?<<?"?"?<<?t.z?<<??endl;?
28?????}?
29?????return?1;?
30?} ????? 輸出結(jié)果為：?
????? 4 4 3?
????? 1 5 4?
????? 2 2 5?
????? 3 3 6
????? 如果我們把第一個例子中的比較運(yùn)算符重載為： bool operator < (const T &t1, const T &t2) { return t1.z > t2.z; // 按照z的順序來決定t1和t2的順序} 則第一個例子的程序會得到和第二個例子的程序相同的輸出結(jié)果。

總結(jié)

以上是生活随笔為你收集整理的优先队列c++ STL用法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。