队列queue的用法

一、queue 是什么

#include <queue>
using namespace std;

queue<int> q;

• 先进先出（FIFO） 数据结构
• 底层用 deque 实现（也可以用 list）
• 常用操作：入队、出队、访问队头/队尾

---

二、基本操作

1️⃣ 入队

q.push(10); // 队尾插入 10
q.push(20);

2️⃣ 出队

q.pop(); // 删除队头元素（不返回值）

3️⃣ 访问队头 / 队尾

cout << q.front(); // 队头元素
cout << q.back();  // 队尾元素

4️⃣ 队列大小 / 是否为空

cout << q.size();
if (q.empty()) cout << "queue is empty";

---

三、遍历队列（注意！不能直接用 range-for）

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

while (!q.empty()) {
    cout << q.front() << " ";
    q.pop();
}

输出：

1 2 3

✅ 注意：pop 会改变队列，遍历过程中会删除元素。

---

四、队列常见应用场景

1️⃣ BFS（广度优先搜索）

queue<int> q;
q.push(start);

while (!q.empty()) {
    int u = q.front();
    q.pop();
    // 处理 u
    for (int v : graph[u]) {
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

2️⃣ 滑动窗口、缓存

• queue 可以做 FIFO 缓存（先进先出）
• 可以结合 deque 做滑动窗口最大值

---

五、priority_queue（进阶）

#include <queue>
priority_queue<int> pq; // 默认大顶堆
pq.push(5);
pq.push(1);
pq.push(3);

cout << pq.top(); // 5
pq.pop();
cout << pq.top(); // 3

• 小顶堆：

priority_queue<int, vector<int>, greater<int>> pq;

---

六、总结

• queue = 先进先出，操作：push、pop、front、back
• 遍历只能通过 while(!empty()) pop
• 竞赛常用于 BFS、缓存、滑动窗口