C++複習（三）：STL庫之deque、stack、queue、priority_queue容器

本文主要參考https://blog.csdn.net/weixin_34128839/article/details/91686932

queue，stack是基于deque實作的，都是順序容器。

deque支援随機通路，queue和stack由于容器特性屏蔽了随機通路（operator []）。

priority_queue是基于vector實作的，底層資料結構是堆。

vector支援随機通路，priority_queue由于容器特性屏蔽了随機通路（operator []）。

一般需要用到最小堆、最大堆時可以用priority_queue來實作。

一般需要用到隊列時可以用queue來實作。

一般需要用到棧時可以用stack來實作。

一般需要用到雙向隊列時可以用deque來實作。

 為下一段先介紹一下list。list的本質是一個雙向連結清單，記憶體空間不連續，通過指針進行操作。

deque是一個double-ended queue，由多個連續記憶體塊構成，deque是list和vector的相容，分為多個塊，每一個塊大小是512位元組，塊通過map塊管理，map塊裡儲存每個塊得首位址。是以該容器也有索引操作operator[]，效率沒vector高。另外，deque比vector多了push_front()和pop_front( )操作，在兩端進行此操作時與list的效率差不多。

1、構造和指派

#include<iostream>
//#include<deque>    stack和queue庫中都包含了deque
#include<stack>
#include<queue>    //queue庫中包含了priority_queue
#include<string>
using namespace std;

//以下int，string等可替換成其他類型，若類型為struct和class時可能還需考慮操作符重載
//deque的其他構造函數基本和vector一緻。
deque<string> dq1(5, "hello");    //建立一個大小為5、值均為"hello"的deque
deque<int> dq2 = { 9,5,2,7 };    //建立一個deque并指派{9,5,2,7}
//一般隻會按如下方式建立，并且除dequeue外隻能這麼建立
deque<int> dq3;
queue<int> q1;    //建立一個空queue。不能加括号，會出問題。
stack<int> st1;    //建立一個空stack。不能加括号，會出問題。
priority_queue<int> pr_q1;    //建立一個空priority_queue。不能加括号，會出問題。預設大的元素優先級高，即大頂堆/最大堆。
priority_queue<int, vector<int>, less<int>> pr_q2;    //這樣寫，大的元素優先級高。和上一行是等同的定義。
priority_queue<int, vector<int>, greater<int>> pr_q3;    //這樣寫，小的元素優先級高，即小頂堆/最小堆。
 
//下标指派，但不建議這麼幹，畢竟是把它當隊列或棧用的
//dq2[1] = 6;    //dq2值為{9,6,2,7}
           

2、大小

一般不會用到，我們不怎麼關注隊列和棧的大小，我們隻關注它是否為空。

dq2.size()    //傳回dq2中元素的個數,即dq2的大小，應為4。
dq2.max_size()    //傳回容器所能容納的最大元素數目。這是系統或者庫所實施的限制,但是容器不一定保證能達到該大小，有可能在還未達到該大小的時候，就已經無法繼續配置設定任何的空間了。這個函數似乎沒有什麼卵用。
           

3、進棧、出棧、進隊、出隊、獲得端點值

//dequeue，雙向隊列
dq3.push_back(2);    //隊尾進隊。隊列值為{2}
dq3.push_front(5);    //隊頭進隊。隊列值為{5,2}
dq3.back();    //傳回隊尾元素值。應為2
dq3.front();    //傳回隊頭元素值。應為5
dq3.pop_back();    //隊尾出隊。隊列值為{5}
dq3.pop_front();    //隊頭出隊。隊列值為{}

//queue，單向隊列
q1.push(2);    //隊尾進隊。隊列值為{2}
q1.push(5);    //隊尾進隊。隊列值為{2,5}
q1.back();    //傳回隊尾元素。應為5
q1.front();    //傳回隊頭元素。應為2
q1.pop();    //隊頭出隊。隊列值為{5}

//stack，棧
st1.push(2);	//進棧。棧值為{2}
st1.push(5);	//進棧。棧值為{2,5}
st1.top();	//傳回棧頂元素值。應為5
st1.pop();	//出棧。棧值為{2}

//priority_queue，優先級隊列
//優先級隊列預設為最大堆，即以從大到小為優先級順序，出隊的元素為最大的元素。
pr_q1.push(2);	//進隊。隊列值為{2}
pr_q1.push(5);	//進隊。隊列值為{5,2}
pr_q1.push(3);	//進隊。隊列值為{5,3,2}
pr_q1.top();	//傳回優先級最大的元素值。應為5
pr_q1.pop();	//出隊。隊列值為{3,2}
           

4、判斷是否為空

dq2.empty();    //若為空，則傳回True，否則傳回False。以下幾個同理
q1.empty();
st1.empty();
pr_q1.empty();
           

5、priority_queue的優先級設定

當隊列中元素為int、string等可比較的元素時，可直接使用以上成員函數。

當隊列中元素為struct，class等元素時，應重載比較函數，比如小于号操作符。具體細節可參考https://blog.csdn.net/hellokandy/article/details/81458663。