queue 和 priority_queue 都是容器介面卡,要使用它們,必須包含標頭檔案 <queue>。
queue
queue 就是“佇列”。佇列是先進先出的,和排隊類似。隊頭的存取和刪除操作只能在隊頭進行,新增操作只能在隊尾進行。不能存取佇列中間的元素。
queue 可以用 list 和 deque 實現,預設情況下用 deque 實現。
queue 的定義如下:
template < class T, class Cont = deque<T> >
class queue{
...
};
queue 同樣也有和 stack 類似的 push、pop、top 函數。區別在於,queue 的 push 發生在隊尾,pop 和 top 發生在隊頭。
priority_queue
priority_queue 是“優先佇列”。它和普通佇列的區別在於,優先佇列的隊頭元素總是最大的——即執行 pop 操作時,刪除的總是最大的元素;執行 top 操作時,返回的是最大元素的參照。
priority_queue 可以用 vector 和 deque 實現,預設情況下用 vector 實現。
priority_queue 預設的元素比較器是 less <T>。也就是說,在預設情況下,要放入 priority_queue 的元素必須是能用“<”運算子進行比較的,而且 priority _queue 保證以下條件總是成立:對於隊頭的元素 x 和任意非隊頭的元素 y,表示式“x<y”必為 false。
priority_queue 定義如下:
template < class T, class Container = vector <T>, class Compare = less<T> >
class priority_queue{
...
};
priority_queue 的第三個型別引數可以用來指定排序規則。
和 set/multiset 不同,priority_queue 是使用“堆排序”技術實現的,其內部並非完全有序,但卻能確保最大元素總在隊頭。因此,priority_queue 特別適用於“不停地在一堆元素中取走最大的元素”這種情況。priority_queue 插入和刪除元素的複雜度都是 O(log(n))。雖然用 set/multiset 也能完成此項工作,但是 priority_queue 比它們略快一些。
priority_queue 隊頭的元素只能被檢視或者修改,不能被刪除。
priority_queue的用法範例如下。
#include <queue>
#include <iostream>
using namespace std;
int main()
{
priority_queue<double> pq1;
pq1.push(3.2); pq1.push(9.8); pq1.push(9.8); pq1.push(5.4);
while(!pq1.empty()) {
cout << pq1.top() << " ";
pq1.pop();
} //上面輸出 9.8 9.8 5.4 3.2
cout << endl;
priority_queue<double,vector<double>,greater<double> > pq2;
pq2.push(3.2); pq2.push(9.8); pq2.push(9.8); pq2.push(5.4);
while(!pq2.empty()) {
cout << pq2.top() << " ";
pq2.pop();
}
//上面輸出 3.2 5.4 9.8 9.8
return 0;
}
程式的輸出結果是:
9.8 9.8 5.4 3.2
3.2 5.4 9.8 9.8
pq2 的排序規則和 pq1 相反,因此元素出隊的順序也相反。