隊(duì)列（Queue）
什么是隊(duì)列
隊(duì)列就是一種線性的數(shù)據(jù)結(jié)構(gòu)，它與日常生活中排隊(duì)的隊(duì)列相似，即先進(jìn)先出（LIFO, First In First Out)，這點(diǎn)也是它與棧（Stack）的最大不同之處。它的結(jié)構(gòu)類似于下面的容器：
如上圖所示，隊(duì)列的結(jié)構(gòu)就像一個(gè)兩端都是開口的容器，一端只負(fù)責(zé)小球（對應(yīng)隊(duì)列中的元素）進(jìn)入，一個(gè)端只負(fù)責(zé)小球彈出，容器內(nèi)部的小球無法跳過前面的小球提前彈出。我們將隊(duì)列的出口端（即隊(duì)列的頭部）叫做隊(duì)頭（front），入口端（即隊(duì)列的末尾）稱為隊(duì)尾（rear）。
與棧類似，隊(duì)列的底層數(shù)據(jù)結(jié)構(gòu)也可以使用數(shù)組和鏈表來實(shí)現(xiàn)，具體如下圖所示：
隊(duì)列的基本操作和應(yīng)用
隊(duì)列的基本操作與棧類似，主要是分為入隊(duì)（enqueue）和出隊(duì)（dequeue），我們以數(shù)組為例，簡單描述一下具體過程。
1. 入隊(duì)
入隊(duì)就是把新元素放入隊(duì)列中去，由于隊(duì)列的數(shù)據(jù)結(jié)構(gòu)的限制，只允許將新入隊(duì)元素放入隊(duì)尾的位置，然后更新隊(duì)尾的位置，具體過程如下圖所示。
2. 出隊(duì)
出隊(duì)就是把隊(duì)列中的元素移出來，同樣的，隊(duì)列只允許在隊(duì)列的隊(duì)頭這一側(cè)移出元素，即每次移出的元素就是隊(duì)頭對應(yīng)的元素，元素移出后，原對頭元素的后面一個(gè)元素變?yōu)樾碌年?duì)頭，具體過程如下所示：
3. 入隊(duì)出隊(duì)的復(fù)雜度和應(yīng)用
與棧類似，隊(duì)列的入隊(duì)與出隊(duì)只與隊(duì)頭和隊(duì)尾的元素相關(guān)，不涉及其他元素的移動，因此隊(duì)列的入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度都是。
隊(duì)列先進(jìn)先出的特性使得其常用于一下場景中：
- 消息隊(duì)列：在分布式系統(tǒng)或異步任務(wù)處理場景中，消息隊(duì)列可以用于解耦任務(wù)的發(fā)布與消費(fèi)，確保任務(wù)能夠穩(wěn)定地進(jìn)行下去。
- 程序調(diào)度：操作系統(tǒng)、多線程程序、并發(fā)網(wǎng)絡(luò)程序等需要協(xié)調(diào)多個(gè)任務(wù)的程序中，通常會使用隊(duì)列來維護(hù)任務(wù)的執(zhí)行順序，以保證每個(gè)任務(wù)都能夠得到執(zhí)行。
- 廣度優(yōu)先搜索：在圖論、路徑查找等問題中，廣度優(yōu)先搜索算法通常會使用隊(duì)列來存儲待搜索的節(jié)點(diǎn)，以確保每一層的所有節(jié)點(diǎn)都可以被訪問到。
- 緩存：在許多應(yīng)用中，緩存通常使用隊(duì)列來管理緩存項(xiàng)的過期時(shí)間和更替策略，使得緩存可以高效地使用有限的內(nèi)存資源。
類模板std::queue
std::queue類是C++提供的容器適配器，它提供了特定的函數(shù)集合，實(shí)現(xiàn)了隊(duì)列的基本功能：FIFO的數(shù)據(jù)結(jié)構(gòu)，即在容器的尾端推入元素，在首段彈出元素。std::queue類在頭文件<queue>中定義，其函數(shù)聲明如下：
template<
class T,
class Container = std::deque<T>
> class queue;
形參T和Container
- T：存儲的元素類型。
- Container：用于存儲元素的底層容器。容器類型必須是序列容器，同時(shí)，該容器類型需提供通常語義下的back()、front()、push_back()和pop_front()函數(shù)，滿足該要求的標(biāo)準(zhǔn)容器有std::deque和std::list，其中默認(rèn)使用的容器是std::deque。
成員函數(shù)
1. 元素訪問
-
front：訪問隊(duì)列第一個(gè)元素。其函數(shù)聲明如下：
reference front(); const_reference front() const;該函數(shù)返回隊(duì)列中首個(gè)元素的引用，實(shí)際上該函數(shù)等效的調(diào)用的就是存儲元素的底層容器（Container）的front()函數(shù)。
-
back：訪問隊(duì)列最后一個(gè)元素。其函數(shù)聲明如下：
reference back(); const_reference back() const;該函數(shù)返回的是隊(duì)列末尾元素的引用，實(shí)際上該函數(shù)等效的調(diào)用的就是Container的back()函數(shù)。
2. 容量
-
empty：檢查隊(duì)列是否為空。其函數(shù)聲明如下：
bool empty() const; // C++20 前 [[nodiscard]] bool empty() const; //C++20 起其本質(zhì)上就是檢查Container是否為空，即Container的empty()。如果為空返回true，否則為false。
-
size：返回隊(duì)列中的元素個(gè)數(shù)。其函數(shù)聲明如如下：
size_type size() const;同樣的，其本質(zhì)還是返回的是Container的元素個(gè)數(shù)，即Container的size()。
3. 隊(duì)列的修改
-
push：向隊(duì)列的尾部插入元素，對應(yīng)的就是入隊(duì)操作。其函數(shù)聲明如下：
void push( const value_type& value ); void push( value_type&& value ); //C++11 起 -
emplace：在隊(duì)列的尾部構(gòu)造元素，對應(yīng)的也是入隊(duì)的操作。其函數(shù)聲明如下：
template< class... Args > void emplace( Args&&... args );// C++11 起 C++17 前 template< class... Args > decltype(auto) emplace( Args&&... args );// C++17 起該函數(shù)就是將新元素推到隊(duì)列的尾部，其與push不同的是：該函數(shù)是原地構(gòu)造元素，即不進(jìn)行移動或復(fù)制操作，使用參數(shù)直接原地調(diào)用元素的構(gòu)造函數(shù)，使得其效率高于push。
-
pop：刪除隊(duì)列首個(gè)元素，對應(yīng)的就是出隊(duì)操作。其函數(shù)聲明如下：
void pop();該函數(shù)移除隊(duì)列前端的元素，等效的調(diào)用了Container的pop_front()函數(shù)。
-
swap：交換兩個(gè)容器的內(nèi)容。其函數(shù)聲明如下：
void swap( queue& other ) noexcept(); //C++11 起其本質(zhì)上是交換兩個(gè)Container中的內(nèi)容。
用法示例
#include <iostream>
#include <queue>
using namespace std;
void showQueue(string queueName, queue<int>& q) {
cout << "隊(duì)列" << queueName << "中元素的數(shù)量, 即size() = " << q.size()
<< endl;
if (!q.empty()) {
cout << "此時(shí), 隊(duì)列" << queueName << "不為空,即empty() = false" << endl;
cout << "隊(duì)列首位元素，即front() = " << q.front() << endl;
cout << "隊(duì)列首位元素，即back() = " << q.back() << endl;
} else {
cout << "此時(shí), 隊(duì)列" << queueName << "為空,即empty() = true" << endl;
}
}
int main() {
queue<int> q;
// push()
q.push(1);
q.push(2);
q.push(3);
cout << "---按順push元素1、2、3后:\n" << endl;
showQueue("q", q);
q.pop(); // 彈出隊(duì)頭元素
cout << "\n---彈出隊(duì)頭元素3, 即pop()后:\n" << endl;
showQueue("q", q);
q.pop();
cout << "\n---彈出隊(duì)頭元素2, 即pop()后:\n" << endl;
showQueue("q", q);
q.pop();
cout << "\n---彈出隊(duì)頭元素1, 即pop()后:\n" << endl;
showQueue("q", q);
queue<int> q1;
q1.emplace(1);
q1.emplace(2);
q1.emplace(3);
cout << "\n-----------隊(duì)列q和q1交換前----------" << endl;
cout << "\nq的狀態(tài): " << endl;
showQueue("q", q);
cout << "\nq1的狀態(tài): " << endl;
showQueue("q1", q1);
q1.swap(q); // s和s1進(jìn)行交換
cout << "\n-----------隊(duì)列q和q1交換后----------\n" << endl;
showQueue("q", q);
cout << "\nq1的狀態(tài): " << endl;
showQueue("q1", q1);
return 0;
}
輸出結(jié)果：
---按順push元素1、2、3后:
隊(duì)列q中元素的數(shù)量, 即size() = 3
此時(shí), 隊(duì)列q不為空,即empty() = false
隊(duì)列首位元素，即front() = 1
隊(duì)列首位元素，即back() = 3
---彈出隊(duì)頭元素3, 即pop()后:
隊(duì)列q中元素的數(shù)量, 即size() = 2
此時(shí), 隊(duì)列q不為空,即empty() = false
隊(duì)列首位元素，即front() = 2
隊(duì)列首位元素，即back() = 3
---彈出隊(duì)頭元素2, 即pop()后:
隊(duì)列q中元素的數(shù)量, 即size() = 1
此時(shí), 隊(duì)列q不為空,即empty() = false
隊(duì)列首位元素，即front() = 3
隊(duì)列首位元素，即back() = 3
---彈出隊(duì)頭元素1, 即pop()后:
隊(duì)列q中元素的數(shù)量, 即size() = 0
此時(shí), 隊(duì)列q為空,即empty() = true
-----------隊(duì)列q和q1交換前----------
q的狀態(tài):
隊(duì)列q中元素的數(shù)量, 即size() = 0
此時(shí), 隊(duì)列q為空,即empty() = true
q1的狀態(tài):
隊(duì)列q1中元素的數(shù)量, 即size() = 3
此時(shí), 隊(duì)列q1不為空,即empty() = false
隊(duì)列首位元素，即front() = 1
隊(duì)列首位元素，即back() = 3
-----------隊(duì)列q和q1交換后----------
隊(duì)列q中元素的數(shù)量, 即size() = 3
此時(shí), 隊(duì)列q不為空,即empty() = false
隊(duì)列首位元素，即front() = 1
隊(duì)列首位元素，即back() = 3
q1的狀態(tài):
隊(duì)列q1中元素的數(shù)量, 即size() = 0
此時(shí), 隊(duì)列q1為空,即empty() = true
原文來自：iDoitnow
