在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候我們會(huì)聽到這樣一個(gè)詞：隊(duì)列。
本文將介紹STL中的隊(duì)列：queue
本文僅從入門和實(shí)用角度介紹queue的用法，主要針對初學(xué)者或競賽向。如有不嚴(yán)謹(jǐn)?shù)牡胤綒g迎指正！本文長度約2000字，閱讀大約需5分鐘。
什么是隊(duì)列？
隊(duì)列是一種FIFO，即First In First Out的數(shù)據(jù)結(jié)構(gòu)，就像是小朋友排隊(duì)一樣，所有元素都只能從隊(duì)尾（rear / back）進(jìn)，隊(duì)頭（front）出，隊(duì)列內(nèi)的元素保持著入隊(duì)時(shí)的順序。
這時(shí)候有小伙伴可能會(huì)問：隊(duì)列能做的，數(shù)組都能模擬，為什么還要隊(duì)列呢？
我們要知道的是，我們學(xué)習(xí)隊(duì)列并非學(xué)習(xí)隊(duì)列這個(gè)結(jié)構(gòu)本身， 而是學(xué)習(xí)其中蘊(yùn)含的思想，用于解決復(fù)雜的問題。
知乎回答：https://www.zhihu.com/question/457210423
隊(duì)列和其他C++的標(biāo)準(zhǔn)庫容器一樣，都只能存放相同的數(shù)據(jù)類型。如果要嘗試存放任意類型，可以去了解一下<any>這個(gè)庫。
隊(duì)列的初始化
在使用queue前，需要引入頭文件。
#include <queue>
用以下的代碼初始化一個(gè)空隊(duì)列：
queue<T> q; // 其中T為數(shù)據(jù)類型
接下來的操作都針對q這個(gè)實(shí)例化對象。
插入元素
語法：q.push(x), x為q中存放的類型的變量。
q.push(1);
q.push(4);
q.push(5);
//q: 1(front) 4 5 (rear)
我們認(rèn)為隊(duì)頭的元素為front，而隊(duì)尾元素的后面一個(gè)位置是rear，符合計(jì)算機(jī)中常見的“左閉右開”的標(biāo)準(zhǔn)。
還有一種辦法，就是用q.emplace()函數(shù)進(jìn)行入隊(duì)，它和push用法相同單有略微差異但是初學(xué)者可以忽略。
此函數(shù)用于將新元素插入隊(duì)列容器，并將新元素添加到隊(duì)列的末尾。
q.emplace(1);
q.emplace(2);
q.emplace(3);
//這個(gè)q接著上一個(gè)例子
//q: 1 4 5 1 2 3
彈出元素
語法：q.pop()，將隊(duì)頭元素彈出。
//q: 1(front) 4 5 (rear)
q.pop();
//q: 4(front) 5 (rear)
q.pop();
//q: 5(front) (rear)
q.pop();
//q: (empty)
q.pop();//錯(cuò)誤！
值得注意的是，當(dāng)隊(duì)列為空的時(shí)候彈出元素會(huì)導(dǎo)致錯(cuò)誤，所以我們在每一步pop()操作的時(shí)候一定要判斷隊(duì)列是否為空，除非你有十足的把握。
本文為eriktse原創(chuàng)，未經(jīng)允許禁止轉(zhuǎn)載。
獲取隊(duì)列大小
語法：size()，返回值為一個(gè)非負(fù)整數(shù)。
cout << q.size() << '\n';
當(dāng)q.size() == 0時(shí)，隊(duì)列為空。
判斷隊(duì)列是否為空
語法：empty()，返回值為bool。
用法和vector類似，感興趣的可以看這篇文章：[C++STL教程]1.vector容器是什么？實(shí)用教程來啦！
if(q.empty())cout << "隊(duì)列為空" << '\n';
else cout << "隊(duì)列非空" << '\n';
當(dāng)然還可以通過判斷隊(duì)列的大小來判斷是否為空。
//當(dāng)q.size() > 0時(shí)，其bool值為true，隊(duì)列非空
if(q.size())cout << "隊(duì)列非空" << '\n';
else cout << "隊(duì)列為空" << '\n';
清空隊(duì)列
有時(shí)候我們需要將隊(duì)列清空，但是queue并沒有像vector那樣的clear函數(shù)，怎么做呢？
這里提供3種方法：（參考：https://blog.csdn.net/zhuiqiuzhuoyue583/article/details/82585383）
//方法一：
while(!q.empty())q.pop();
//方法二：
q = queue<int>();//直接賦值一個(gè)新的queue
//方法三：
template<class T>
void clear(queue<T> &q)
{
queue<T> empty();
swap(empty, q);
}
clear(q);
有同學(xué)可能會(huì)疑惑這三種方法的效率有沒有什么區(qū)別，我實(shí)測了一下，幾乎沒有區(qū)別。在我的電腦上清空一個(gè)大小為1e6的隊(duì)列，時(shí)間約為700ms。
判斷兩個(gè)隊(duì)列是否相同（很少用到）
語法：q1 ==== q2，返回一個(gè)bool值表示兩個(gè)隊(duì)列是否相等。
看下面這個(gè)例子：
queue<int> q, t;
q.push(1);
cout << (q ====== t) << '\n';// 0
t.emplace(1);
cout << (q ====== t) << '\n';// 1
q.pop();
cout << (q ====== t) << '\n';// 0
t.pop();
cout << (q ==== t) << '\n';// 1
隊(duì)列常用函數(shù)總結(jié)
- push() 在隊(duì)尾插入一個(gè)元素，入隊(duì)
- pop() 刪除隊(duì)列第一個(gè)元素，出隊(duì)
- size() 返回隊(duì)列中元素個(gè)數(shù)，即隊(duì)列大小
- empty() 如果隊(duì)列空則返回
true，反之則false - front() 返回隊(duì)列中的第一個(gè)元素，即隊(duì)頭元素
- back() 返回隊(duì)列中最后一個(gè)元素，即隊(duì)尾元素
用front()獲取隊(duì)頭并不會(huì)自動(dòng)把頭彈出，如果需要彈出記得加一個(gè)pop()。
本文到此結(jié)束啦，感謝大家的閱讀！
如果這篇文章對你有幫助歡迎收藏，點(diǎn)贊，關(guān)注我的賬號！
