Queue – 隊列

一、隊列的概述

隊列(queue)是一種常見的, 先進先出 (FIFO, First-In-First-Out)的數據結構, 在隊尾插入元素，在隊頭刪除元素。

隊列可以應用於: 線程任務調度、廣度優先搜索、消息隊列等場景，是一種非常重要的數據結構。

二、隊列的實現

隊列的實現可以基於鏈表(linked list)或數組(array)來實現，鏈表實現隊列更加靈活方便，數組實現的隊列有著更好的性能表現。

三、隊列的操作

1、隊列的初始化

    
        #include
        #include

        using namespace std;

        int main(){
            queue q; // 初始化一個空隊列
            return 0;
        }
    

2、隊列的插入操作

1) push()

在隊列的末尾插入一個元素，時間複雜度為O(1)。

    
        queue q;
        q.push(1);    // 像隊尾插入元素
        q.push(2);
        q.push(3);
    

2) emplace()

emplace()函數根據傳入的參數構造一個新元素，將其插入隊列的末尾。但emplace()與push()不同的是，emplace()避免了額外的構造函數和複製操作。

    
        struct Person{
            string name;
            int age;

            Person(string n, int a):name(n),age(a){}
        };

        queue q;
        q.emplace("Tom", 18);    // 在隊列末尾插入一個Person類型的對象
    

3、隊列的刪除操作

1) pop()

隊列的頭部元素出隊，時間複雜度為O(1)。

    
        queue q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.pop();    // 彈出隊頭元素
    

4、隊列的查詢操作

1) front()

獲取隊列的頭部元素，時間複雜度為O(1)。

    
        queue q;
        q.push(1);
        q.push(2);
        q.push(3);
        int x = q.front();    // 獲取隊頭元素
    

2) empty()

判斷隊列是否為空，時間複雜度為O(1)。

    
        queue q;
        if(q.empty()){    // 判斷隊列是否為空
            cout << "Queue is empty." << endl;
        }
    

3) size()

返回隊列中元素的個數，時間複雜度為O(1)。

    
        queue q;
        q.push(1);
        q.push(2);
        q.push(3);
        int n = q.size();    // 獲取隊列中元素個數
    

四、隊列的應用場景

1、線程任務調度

在多線程編程中，通過隊列來存儲任務，從而實現任務的先進先出調度。

2、廣度優先搜索

在圖論演算法中，廣度優先搜索(Breadth First Search, BFS)就是通過隊列實現的。

3、消息隊列

在計算機網路中，消息隊列(Message Queue)是一種非同步通信機制，通過隊列將消息從一個應用傳遞到另一個應用。