C++ queue 容器介紹

queue 是 C++ 標準庫中的一個容器適配器，它實現了先進先出（FIFO）數據結構。即，元素按照插入的順序排隊，首先插入的元素最先出隊。queue 適用于需要排隊處理任務的場景，比如消息隊列、任務調度等。

1. queue 的基本特性

• 先進先出（FIFO）：queue 實現了先進先出的特性。第一個進入隊列的元素將會第一個被移除。
• 容器適配器：queue 不是一個獨立的容器類，而是基于其他容器（通常是 deque 或 list）進行實現的容器適配器。
• 操作簡潔：queue 提供了常見的隊列操作，比如入隊（push()）、出隊（pop()）和訪問隊頭元素（front()）。

2. queue 的常見操作

2.1 構造與初始化

queue 默認使用 deque 容器作為底層實現，你也可以選擇其他容器類型。

#include <iostream>
#include <queue>int main() {// 默認構造std::queue<int> q;// 初始化時加入元素std::queue<int> q2;q2.push(10);q2.push(20);q2.push(30);std::cout << "Queue initialized with elements: ";while (!q2.empty()) {std::cout << q2.front() << " ";q2.pop();}std::cout << std::endl;return 0;
}

2.2 入隊操作（push()）

你可以使用 push() 方法將元素加入隊列的尾部。

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);

2.3 出隊操作（pop()）

pop() 方法移除隊頭元素，但并不會返回被移除的元素。如果你想訪問出隊的元素，需要先使用 front() 獲取它。

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);// 移除隊頭元素
q.pop();
std::cout << "After pop, front element: " << q.front() << std::endl;  // 輸出 2

2.4 訪問隊頭元素（front()）

front() 返回隊頭元素的引用。

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);std::cout << "Front element: " << q.front() << std::endl;  // 輸出 1

2.5 訪問隊尾元素（back()）

back() 返回隊尾元素的引用。

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);std::cout << "Back element: " << q.back() << std::endl;  // 輸出 3

2.6 檢查隊列是否為空（empty()）

empty() 方法檢查隊列是否為空，返回一個布爾值。

std::queue<int> q;
if (q.empty()) {std::cout << "Queue is empty." << std::endl;
} else {std::cout << "Queue is not empty." << std::endl;
}

2.7 獲取隊列大小（size()）

size() 方法返回隊列中元素的數量。

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);std::cout << "Queue size: " << q.size() << std::endl;  // 輸出 3

3. queue 的底層實現

queue 是一個容器適配器，默認情況下，它使用 deque（雙端隊列）作為底層容器。deque 提供了在兩端高效插入和刪除元素的能力，因此適合用于隊列的實現。
可以通過顯式指定底層容器類型來創建 queue。例如，使用 list 作為底層容器：

#include <iostream>
#include <queue>
#include <list>int main() {std::queue<int, std::list<int>> q;q.push(1);q.push(2);q.push(3);std::cout << "Front element: " << q.front() << std::endl;  // 輸出 1return 0;
}

3.1 deque 和 list 作為底層容器的比較

• deque：允許在隊列兩端快速插入和刪除元素，且可以直接訪問任意元素。deque 的隊頭和隊尾操作非常高效，適合用于實現隊列。
• list：雙向鏈表，雖然也能在兩端進行高效的插入和刪除操作，但不允許隨機訪問任何元素，因此性能上稍遜一籌。

4. queue 和 priority_queue 的區別

• queue：實現了先進先出的原則，適用于任務按順序處理的場景。
• priority_queue：實現了優先級隊列，可以根據優先級對元素進行排序。優先級隊列中的元素不是按插入順序處理，而是根據優先級處理。

4.1 priority_queue 示例

#include <iostream>
#include <queue>int main() {std::priority_queue<int> pq;pq.push(10);pq.push(5);pq.push(20);std::cout << "Top element in priority queue: " << pq.top() << std::endl;  // 輸出 20pq.pop();std::cout << "Top element after pop: " << pq.top() << std::endl;  // 輸出 10return 0;
}

需要優先處理元素時，可以考慮使用 priority_queue。

#include <queue>
#include <iostream>int main() {std::queue<int> q;q.push(10);q.push(20);q.push(30);// 查看隊列中的元素while (!q.empty()) {std::cout << q.front() << " ";q.pop();}return 0;
}