隊列與C++中的queue詳解

隊列（Queue）

什么是隊列

隊列就是一種線性的數(shù)據(jù)結(jié)構(gòu)，它與日常生活中排隊的隊列相似，即先進(jìn)先出（LIFO, First In First Out)，這點也是它與棧Stack的最大不同之處。它的結(jié)構(gòu)類似于下面的容器：

如上圖所示，隊列的結(jié)構(gòu)就像一個兩端都是開口的容器，一端只負(fù)責(zé)小球（對應(yīng)隊列中的元素）進(jìn)入，一個端只負(fù)責(zé)小球彈出，容器內(nèi)部的小球無法跳過前面的小球提前彈出。我們將隊列的出口端（即隊列的頭部）叫做隊頭（front），入口端（即隊列的末尾）稱為隊尾（rear）。

與棧類似，隊列的底層數(shù)據(jù)結(jié)構(gòu)也可以使用數(shù)組和鏈表來實現(xiàn)，具體如下圖所示：

隊列的基本操作和應(yīng)用

隊列的基本操作與棧類似，主要是分為入隊（enqueue）和出隊（dequeue），我們以數(shù)組為例，簡單描述一下具體過程。

1. 入隊

入隊就是把新元素放入隊列中去，由于隊列的數(shù)據(jù)結(jié)構(gòu)的限制，只允許將新入隊元素放入隊尾的位置，然后更新隊尾的位置，具體過程如下圖所示。

2. 出隊

出隊就是把隊列中的元素移出來，同樣的，隊列只允許在隊列的隊頭這一側(cè)移出元素，即每次移出的元素就是隊頭對應(yīng)的元素，元素移出后，原對頭元素的后面一個元素變?yōu)樾碌年狀^，具體過程如下所示：

3. 入隊出隊的復(fù)雜度和應(yīng)用

與棧類似，隊列的入隊與出隊只與隊頭和隊尾的元素相關(guān)，不涉及其他元素的移動，因此隊列的入隊和出隊的時間復(fù)雜度都是。

隊列先進(jìn)先出的特性使得其常用于一下場景中：

• 消息隊列：在分布式系統(tǒng)或異步任務(wù)處理場景中，消息隊列可以用于解耦任務(wù)的發(fā)布與消費(fèi)，確保任務(wù)能夠穩(wěn)定地進(jìn)行下去。
• 程序調(diào)度：操作系統(tǒng)、多線程程序、并發(fā)網(wǎng)絡(luò)程序等需要協(xié)調(diào)多個任務(wù)的程序中，通常會使用隊列來維護(hù)任務(wù)的執(zhí)行順序，以保證每個任務(wù)都能夠得到執(zhí)行。
• 廣度優(yōu)先搜索：在圖論、路徑查找等問題中，廣度優(yōu)先搜索算法通常會使用隊列來存儲待搜索的節(jié)點，以確保每一層的所有節(jié)點都可以被訪問到。
• 緩存：在許多應(yīng)用中，緩存通常使用隊列來管理緩存項的過期時間和更替策略，使得緩存可以高效地使用有限的內(nèi)存資源。

類模板std::queue

std::queue類是C++提供的容器適配器，它提供了特定的函數(shù)集合，實現(xiàn)了隊列的基本功能：FIFO的數(shù)據(jù)結(jié)構(gòu)，即在容器的尾端推入元素，在首段彈出元素。std::queue類在頭文件中定義，其函數(shù)聲明如下：

template<
    class T,
    class Container = std::deque< T >
> class queue;

形參T和Container

• T ：存儲的元素類型。
• Container ：用于存儲元素的底層容器。容器類型必須是序列容器，同時，該容器類型需提供通常語義下的back()、front()、push_back()和pop_front()函數(shù)，滿足該要求的標(biāo)準(zhǔn)容器有std::deque和std::list，其中默認(rèn)使用的容器是std::deque。

成員函數(shù)

1. 元素訪問

• front ：訪問隊列第一個元素。其函數(shù)聲明如下：

reference front();
const_reference front() const;

該函數(shù)返回隊列中首個元素的引用，實際上該函數(shù)等效的調(diào)用的就是存儲元素的底層容器（Container）的front()函數(shù)。

• back ：訪問隊列最后一個元素。其函數(shù)聲明如下：

reference back();
const_reference back() const;

該函數(shù)返回的是隊列末尾元素的引用，實際上該函數(shù)等效的調(diào)用的就是Container的back()函數(shù)。

2. 容量

• empty ：檢查隊列是否為空。其函數(shù)聲明如下：

bool empty() const; // C++20 前
[[nodiscard]] bool empty() const; //C++20 起

其本質(zhì)上就是檢查Container是否為空，即Container的empty()。如果為空返回true，否則為false。

• size ：返回隊列中的元素個數(shù)。其函數(shù)聲明如如下：

size_type size() const;

同樣的，其本質(zhì)還是返回的是Container的元素個數(shù)，即Container的size()。

3. 隊列的修改

• push ：向隊列的尾部插入元素，對應(yīng)的就是入隊操作。其函數(shù)聲明如下：

void push( const value_type& value );
void push( value_type&& value ); //C++11 起

• emplace ：在隊列的尾部構(gòu)造元素，對應(yīng)的也是入隊的操作。其函數(shù)聲明如下：

template< class... Args >
void emplace( Args&&... args );// C++11 起  C++17 前
template< class... Args >
decltype(auto) emplace( Args&&... args );// C++17 起

該函數(shù)就是將新元素推到隊列的尾部，其與push不同的是：該函數(shù)是原地構(gòu)造元素，即不進(jìn)行移動或復(fù)制操作，使用參數(shù)直接原地調(diào)用元素的構(gòu)造函數(shù)，使得其效率高于push。

• pop ：刪除隊列首個元素，對應(yīng)的就是出隊操作。其函數(shù)聲明如下：

void pop();

該函數(shù)移除隊列前端的元素，等效的調(diào)用了Container的pop_front()函數(shù)。

• swap ：交換兩個容器的內(nèi)容。其函數(shù)聲明如下：

void swap( queue& other ) noexcept(); //C++11 起

其本質(zhì)上是交換兩個Container中的內(nèi)容。

用法示例

#include < iostream >
#include < queue >
using namespace std;

void showQueue(string queueName, queue< int >& q) {
    cout < < "隊列" < < queueName < < "中元素的數(shù)量, 即size() = " < < q.size()
        < < endl;
    if (!q.empty()) {
        cout < < "此時, 隊列" < < queueName < < "不為空,即empty() = false" < < endl;
        cout < < "隊列首位元素，即front() =  " < < q.front() < < endl;
        cout < < "隊列首位元素，即back() =  " < < q.back() < < endl;
    } else {
        cout < < "此時, 隊列" < < 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();  // 彈出隊頭元素
    cout < < "n---彈出隊頭元素3, 即pop()后:n" < < endl;
    showQueue("q", q);

    q.pop();
    cout < < "n---彈出隊頭元素2, 即pop()后:n" < < endl;
    showQueue("q", q);

    q.pop();
    cout < < "n---彈出隊頭元素1, 即pop()后:n" < < endl;
    showQueue("q", q);

    queue< int > q1;
    q1.emplace(1);
    q1.emplace(2);
    q1.emplace(3);

    cout < < "n-----------隊列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-----------隊列q和q1交換后----------n" < < endl;
    showQueue("q", q);

    cout < < "nq1的狀態(tài): " < < endl;
    showQueue("q1", q1);

    return 0;
}

輸出結(jié)果：

---按順push元素1、2、3后:

隊列q中元素的數(shù)量, 即size() = 3
此時, 隊列q不為空,即empty() = false
隊列首位元素，即front() =  1
隊列首位元素，即back() =  3

---彈出隊頭元素3, 即pop()后:

隊列q中元素的數(shù)量, 即size() = 2
此時, 隊列q不為空,即empty() = false
隊列首位元素，即front() =  2
隊列首位元素，即back() =  3

---彈出隊頭元素2, 即pop()后:

隊列q中元素的數(shù)量, 即size() = 1
此時, 隊列q不為空,即empty() = false
隊列首位元素，即front() =  3
隊列首位元素，即back() =  3

---彈出隊頭元素1, 即pop()后:

隊列q中元素的數(shù)量, 即size() = 0
此時, 隊列q為空,即empty() = true

-----------隊列q和q1交換前----------

q的狀態(tài): 
隊列q中元素的數(shù)量, 即size() = 0
此時, 隊列q為空,即empty() = true

q1的狀態(tài): 
隊列q1中元素的數(shù)量, 即size() = 3
此時, 隊列q1不為空,即empty() = false
隊列首位元素，即front() =  1
隊列首位元素，即back() =  3

-----------隊列q和q1交換后----------

隊列q中元素的數(shù)量, 即size() = 3
此時, 隊列q不為空,即empty() = false
隊列首位元素，即front() =  1
隊列首位元素，即back() =  3

q1的狀態(tài): 
隊列q1中元素的數(shù)量, 即size() = 0
此時, 隊列q1為空,即empty() = true