C++STL之Priority_queue(優(yōu)先隊列)

138824 閱讀 0 評論 0 點贊

1. 簡介

優(yōu)先隊列是一種極其特殊的隊列，他與標準的隊列使用線性結構進行計算不同，優(yōu)先隊列的底層是以散列的狀態(tài)（非線性）表現(xiàn)的，他與標準的隊列有如下的區(qū)別，標準的隊列遵從嚴格的先進先出，優(yōu)先隊列并不遵從標準的先進先出，而是對每一個數(shù)據(jù)賦予一個權值，根據(jù)當前隊列權值的狀態(tài)進行排序，使得權值最大（或最?。┑挠肋h排在隊列的最前面。

2. 相關頭文件

由于其屬于隊列的一種，因此可以直接使用隊列的頭文件#include<queue>

3. 優(yōu)先隊列的初始化

priority_queue<T, Container, Compare>
priority_queue<T>        //直接輸入元素則使用默認容器和比較函數(shù)

與往常的初始化不同，優(yōu)先隊列的初始化涉及到一組而外的變量，這里解釋一下初始化：

a) T就是Type為數(shù)據(jù)類型

b) Container是容器類型，（Container必須是用數(shù)組實現(xiàn)的容器，比如vector,deque等等，但不能用 list。STL里面默認用的是vector）

c) Compare是比較方法，類似于sort第三個參數(shù)那樣的比較方式，對于自定義類型，需要我們手動進行比較運算符的重載。與sort直接Bool一個函數(shù)來進行比較的簡單方法不同，Compare需要使用結構體的運算符重載完成，直接bool cmp(int a,int b){ return a>b; } 這么寫是無法通過編譯的。

使用的舉例有：

struct cmp
{ //這個比較要用結構體表示
    bool operator()(int &a, int &b) const
    {
        return a > b;
    }
};
 
priority_queue<int,vector<int>,cmp> q;    //使用自定義比較方法
priority_queue<int> pq;

4. 常用接口

我們預先通過priority_queue <int> q創(chuàng)建了一個隊列，命名為q，方便舉例。

a)大小size()

返回隊列元素的個數(shù)

函數(shù)原型：size_type size() const;

cout<<q.size()<<endl;   //直接返回隊列中元素的個數(shù)

b) 入隊push()

進行入隊操作，在隊尾處進行插入

函數(shù)原型：void push (const value_type& val);

q.push(100);

c) 出隊pop()

進行出隊操作，在對頭出進行彈出

函數(shù)原型：void pop();

q.pop();

d) 訪問隊頭元素top()

與標準隊列不同，優(yōu)先隊列只允許訪問隊頭元素，不允許訪問其余的數(shù)據(jù)，由于堆的特殊性質，堆頂元素的優(yōu)先權最高（或者最低），訪問其余元素沒有意義，因此，優(yōu)先隊列只允許訪問隊頭元素，這和棧的訪問類型類似所以使用棧訪問棧頂?shù)拿鹴op

函數(shù)原型是：

reference& top();

const_reference& top() const;

 cout<<q.top()<<endl;

e) 判空empty()

返回一個bool類型的值，只存在真和假，當隊列為空時為真，不為空時為假

函數(shù)原型

bool empty() const;

可以利用empty()進行隊列的遍歷操作，這里建議先使用初始化函數(shù)將隊列進行復制，否則遍歷之后隊列就為空了。

  while(q.empty()){
        cout<<q.pop()<<endl;
        q.pop();
    }

5.實例代碼

可以通過這個代碼進行參考，可以看的輸出的結果是順序的。

#include <queue>
#include <iostream>
using namespace std;
struct cmp
{ //這個比較要用結構體表示
    bool operator()(int &a, int &b) const
    {
        return a > b;
    }
};
int main()
{
    priority_queue<int, vector<int>, cmp> q;
    for (int i = 1; i <= 5; i++)
    {
        q.push(i * 10);
        cout << "push element " << i << endl;
    }
    q.push(15);
    q.push(4);
    int i = 1;
    while (!q.empty())
    {
        int temp = q.top();
        q.pop();
        cout << "No " << i++ << " element is: " << temp << endl;
    }
    return 0;
}

輸出：

push element 1
push element 2
push element 3
push element 4
push element 5
No 1 element is: 4
No 2 element is: 10
No 3 element is: 15
No 4 element is: 20
No 5 element is: 30
No 6 element is: 40
No 7 element is: 50