STL之queue、priority_queue學習總結（C++）

STL之queue、priority_queue用法

• 概述
• 具體用法
• • 0. 頭檔案
  • 1. 聲明和初始化
  • • 1.1 queue
    • 1.2 priority_queue
    • • 1.2.1 基本資料類型，以int為例
      • 1.2.2 結構體
  • 2. 常用函數（查詢）
  • • 2.1 empty()
    • 2.2 size()
    • 2.3 front()——queue；
    • 2.4 back()——queue
    • 2.5 top()——priority_queue
    • 2.6 輸出
  • 3. 常用函數（操作）
  • • 3.1 push()
    • 3.2 emplace()
    • 3.3 pop()
    • 3.4 swap()
  • 4. 實際使用出現的問題和方案
  • • 4.1 插入時判斷是否已存在相同的元素值？
    • 4.2 将某個值删除（若有重複值）

概述

1. STL提供3種容器擴充卡：stack、queue、priority_queue。容器擴充卡不是第一類容器，因為它們不提供存放資料的實際資料結構的實作方法。而且容器擴充卡不支援疊代器。容器擴充卡的好處：程式員可以選擇相應的基礎資料結構。
2. queue模闆類讓底層類（預設是deque）展示典型的隊列接口。
3. queue類的限制比deque更多，不允許随機通路隊列元素、不允許周遊隊列。而是提供的功能可以從基礎資料結構的結尾插入或在開頭删除（先進先出FIFO）。priority_queue提供的功能可以按排列順序插入基礎資料結構，并從基礎資料結構的前面删除。
4. queue能用list和deque實作。priority_queue能用vector和deque實作。預設情況下，queue用deque實作。priority_queue用vector實作。 這兩個實作都是其最佳性能。

5. 在priority_queue中增加元素時，該元素自動按優先順序插入，使最高優先級元素（預設是最大值）首先從priority_queue中取出。

   通常是用堆排序技術實作的。 這種資料結構成為堆(heap)。預設的元素比較器是less。

   優先隊列常見用法是是處理堆的有關操作。預設優先隊列是大頂堆。

6. priority_queue插入與删除

   -push操作：根據優先順序将元素插入相應位置(先調用基礎容器的push_back函數，然後用堆排序重新排列元素)；

   -pop操作：删除最高優先級元素（删除堆頂上的元素後調用基礎容器的pop_back函數）。

具體用法

0. 頭檔案

#include<queue>

1. 聲明和初始化

1.1 queue

//聲明queue，預設以deque容器實作
	queue<int>q1;
//聲明queue，以list容器實作
	queue<int, list<int>>q1;

//聲明一個int類型的queue2,将queue1的元素複制給queue2
	queue<int>queue2=queue1;
或	queue<int> queue2(queue1);

           

1.2 priority_queue

1.2.1 基本資料類型，以int為例

//聲明priority_queue，預設以vector容器實作，預設排序是從大到小
	priority_queue<int>q11;
//聲明priority_queue，以deque容器實作，預設排序是從大到小
	priority_queue<int, deque<int>>q11;

//聲明priority_queue，設定排序為：從小到大，需要三個參數
//參數内容：存儲元素類型、容器類型、順序定義
	priority_queue<int, vector<int>,greater<int>>q11;

           

1.2.2 結構體

對于結構體而言，排序順序需要自己實作。

//法一：在結構體裡内重載比較函數(使用友元）
struct A{
	int x;
	int y;
	A(int _x, int _y):x(_x),y(_y) {}

	friend bool operator < (A a, A b) {
		return a.y > b.y;    //重載小于号使得小的先出隊列    
	}
};

priority_queue<A> p1; //或priority_queue<A,vector<A>> p1;

//法二：在結構體裡内重載比較函數
struct A{
	int x;
	int y;
	A(int _x, int _y):x(_x),y(_y) {}

	bool operator < (const A &a) const {
		return y > a.y;    //重載小于号使得小的先出隊列    
	}
};

priority_queue<A> p1; //或priority_queue<A,vector<A>> p1;

//法三：在結構體外
struct A{
	int x;
	int y;
	A(int _x, int _y):x(_x),y(_y) {}
};
struct cmp {
	bool operator ()(const A &a, const A &b) {
		return a.y > b.y; //重載使得小的先出隊列
	}
};

priority_queue<A, vector<A>,cmp> p1; //定義需要3個參數

           

2. 常用函數（查詢）

未特别标注的都是queue、priority_queue通用的函數方法。

2.1 empty()

queue1.empty(); //傳回值bool類型，若queue1為空，則傳回true
           

2.2 size()

queue1.size(); //傳回值為int類型，queue1目前存放的元素的個數
           

2.3 front()——queue；

條件是queue不為空

queue1.front(); //傳回隊列頭部元素
           

2.4 back()——queue

條件是queue不為空

queue1.back(); //傳回隊列末尾元素
           

2.5 top()——priority_queue

條件是priority_queue不為空

queue1.top(); //傳回隊列頭部元素
           

2.6 輸出

//設定一個輸出函數
void display_queue(queue<int> nums) {
	while (!nums.empty()) {
		cout << nums.front() << " ";
		nums.pop();
	}
	cout << endl;
}
           

3. 常用函數（操作）

3.1 push()

//在queue1的隊列末尾放入元素2
	queue1.push(2)
           

3.2 emplace()

push()函數和emplace()都是在隊列這個容器的末尾插入一個新的元素。

• push() 實際上是調用的底層容器的push_back()函數，新元素的值是push函數參數的一個拷貝。
• emplace() 實際上是調用的底層容器的emplace_back()函數，新元素的值是在容器内部就地構造的，不需要移動或者拷貝。

//在stack1的棧頂放入元素2
	stack1.emplace(2);
           

3.3 pop()

//删除queue1隊列頭部元素
	queue1.pop()
           

3.4 swap()

//将queue1和queue2交換
	queue1.swap(queue2);
           

4. 實際使用出現的問題和方案

4.1 插入時判斷是否已存在相同的元素值？

由于沒有find()、count()函數，無法直接調用函數得知隊列是否存在相同值。

4.2 将某個值删除（若有重複值）

int key=pq.top();
while(key==pq.top()){
	pq.pop();
}