深入掌握STL Queue

STL中的queue是一個標準模板庫容器，能夠快速有效地存儲和處理數據，是日常編程開發中非常常用的數據結構之一。本篇文章將從多個方面對STL queue進行詳細的闡述。

一、基本概念

Queue是一種受限的線性結構，遵循先進先出(FIFO)原則。主要有兩個關鍵方法：push()向隊尾插入元素、pop()彈出隊頭元素。

在STL中，queue是一個模板類，包含在頭文件中。聲明一個queue對象可以使用如下方式：

queue q; //創建一個空的int類型隊列

queue默認使用deque作為底層容器進行實現，也可以通過指定另一種STL容器作為底層實現：

queue<int, vector> q; //使用vector作為底層容器實現隊列

二、基本操作與屬性

1. push()和pop()

隊列的最基本操作是push()和pop()，分別是在隊列末尾添加一個元素和彈出隊頭元素。這兩個操作都能夠在常量時間完成。

queue q;
q.push(1); //隊列中添加元素1
q.push(2); //隊列中添加元素2
q.pop(); //彈出隊列頭元素1

2. front()和back()

除了基本操作外，隊列還有兩個輔助操作。front()返回隊列的頭元素，back()返回隊列的尾元素。它們都在常量時間完成。但需要注意的是，在隊列為空的時候使用front()和back()會導致一場，因此使用之前需要先通過empty()方法判斷隊列是否為空。

queue q;
q.push(1); //在隊列末尾插入元素
q.push(2);
cout << q.front() << endl; //輸出隊列頭元素1
cout << q.back() << endl; //輸出隊列尾元素2

3. empty()和size()

empty()方法用於檢查隊列是否為空，返回true表示隊列為空，false表示隊列不為空。size()方法用於返回隊列中元素的個數。

queue q;
q.push(1);
q.push(2);
cout << q.empty() << endl; //輸出0，隊列不為空
cout << q.size() << endl; //輸出2，隊列中共有兩個元素

三、應用場景

1. BFS搜索算法

隊列在BFS搜索算法中扮演重要的角色。在BFS算法中，我們從起點開始搜索，遇到規定條件的節點就將其加入隊列中，然後依次從隊列中彈出節點，擴展其所有可到達的子節點並加入到隊列中。如此迭代直到搜索到目標節點或者隊列為空。

vector<vector> graph; //圖的鄰接矩陣，0表示不聯通
vector visited(n, false); //節點的訪問標記
queue q;
q.push(start);
visited[start] = true;
while(!q.empty()) {
    int cur = q.front();
    q.pop();
    //處理當前節點cur的操作
    for(int i = 0; i < n; i++) {
        if(graph[cur][i] == 1 && !visited[i]) {
            q.push(i);
            visited[i] = true;
        }
    }
}

2. 多線程

在多線程編程過程中，隊列可以被用於緩存數據，在多個線程之間進行數據交換和協同工作。例如，一個生產者線程將數據推入到隊列中，一個或多個消費者線程則從隊列中取出數據並進行處理。

queue q;
mutex m;
condition_variable cv;
//生產者線程
void push(int data) {
    unique_lock lock(m);
    q.push(data); //將數據壓入隊列中
    cv.notify_one(); //喚醒一個消費者線程
}
//消費者線程
void pop() {
    unique_lock lock(m);
    while(q.empty()) {
        cv.wait(lock); //等待喚醒，防止死鎖
    }
    int data = q.front(); //從隊列中取出數據
    q.pop(); //彈出隊列頭元素
    //進行對data的處理
}

3. 最近的K個元素

在某些場合，我們需要求解一個序列中最近的K個元素，這時我們可以使用隊列來維護一個大小為K的滑動窗口，每當有新的元素到來時，判斷是否可以加入隊列，如果可以就將其加入隊列尾部並彈出隊頭的元素。

vector nums; //原始數組
queue q; //維護窗口的隊列
int k = 3; //窗口大小為3
for(int i = 0; i = k) { //隊列已滿
        q.pop(); //彈出隊頭的元素
    }
    q.push(nums[i]); //將新元素壓入隊列
    if(q.size() == k) { //隊列滿足窗口大小
        //進行對q中元素的處理
    }
}

總結

本篇文章從基本概念、基本操作與屬性和應用場景三個方面介紹了STL queue的相關知識。熟練掌握STL queue，可以提高程序員編寫代碼的效率並提高代碼可讀性。