队列(queue) 知识点讲解

🎯 先搞清楚它是什么

📌 考纲要求（NOI 大纲 · 数据结构基础 / 参考《cspNOI级大纲解读》）：考纲在“数据结构”部分将“优先队列”列为应知应会内容，队列更是 BFS、缓冲区等算法的基础。原文多处以队列实现广度搜索，例如“queue<int> q; ... q.push(st); while (!q.empty()) { q.pop(); ... q.push(v); }”的写法贯穿图论算法。本讲对齐“队列(queue)”这一考点：理解先进先出（FIFO）特性，能用手写数组或 STL queue 模拟进出队。

队列（queue） 是“先进先出（FIFO, First In First Out）”的线性结构。像现实里排队买票：新来的人站队尾，窗口永远叫队头那个人。

两个端点：

• 队尾（tail）：只能从这头入队（push）；
• 队头（head）：只能从这头出队（pop / front）。

⚠️ 一句话区分：栈是“叠盘子”（后进先出），队列是“排队”（先进先出）。看到“按到达顺序处理 / 一层一层扩散 / 缓冲区”先想队列。

🧩 关键规则与结论

手写数组队列（带 head / tail 指针）：

int q[100005], head = 0, tail = 0;
q[tail++] = x;             // 入队：放到 tail，tail++
int v = q[head++];        // 出队：取 head，head++
bool empty = (head == tail);
int front = q[head];       // 看队头不弹出

STL 写法：

#include <queue>
queue<int> q;
q.push(x);                // 入队（队尾）
int f = q.front();        // 看队头
q.pop();                  // 出队（队头，无返回值）
bool e = q.empty();

三条铁律：

1. 出队/看队头前必须判空，空队访问会 RE；

2. STL 的 pop() 没有返回值，要取值先 front()；

3. 手写数组队列 head、tail 一直往后走会“假溢出”——用循环队列（取模）复用空间。

🗺️ 知识用法地图

🔬 推演：为什么这些写法是对的（以及它们能用来干什么）

推演 1 · 为什么队列是“先进先出”

入队永远在 tail 端追加，出队永远从 head 端取。最早入队的元素留在 head 位置，自然第一个被取走；最晚入队的在 tail 端，最后才被处理。这就是 FIFO。head == tail 表示队空。

📌 用法：凡是“先来的先服务”（打印队列、任务调度、消息队列）都直接映射成队列。

推演 2 · 为什么手写队列会“假溢出”，循环队列怎么解

普通数组队列每次 head++、tail++，下标只增不减，很快 tail 越界——即使队里没几个元素（前面的空位浪费了），叫“假溢出”。循环队列把数组首尾接成环：tail 走到末尾就绕回开头：tail = (tail + 1) % N。这样前面空出来的位置能被复用。

📌 用法：空间固定、持续进出时（如缓冲区），用 (指针+1)%容量 取模实现环形复用，避免越界。

推演 3 · 为什么 BFS 必须用队列

BFS 要“先访问离起点近的点，再访问远的”。队列的 FIFO 正好保证：把起点入队，每次取出队头（当前最近层），把它未访问的邻居入队尾。这样队里的点按“距离”从小到大排列，出队顺序天然就是层序——这就是 BFS 正确的根本原因。

📌 用法：所有“求最短步数 / 连通块 / 层序”的问题，底层都是队列；DFS 才用栈（递归）。

🔧 编程题里怎么考、怎么用？

① 它在编程题里长什么样（考法总览）

② 识别信号清单：看到什么该想到队列

• “排队 / 按到达顺序 / 先来先服务” → 队列；
• “最少步数 / 最短距离 / 连通块（无权图）” → BFS（队列）；
• “最近 K 个 / 时间窗口内统计” → 滑动窗口队列；
• “一层一层 / 按层处理” → 队列分层；
• 注意和栈区分：要“两端进出不同端”用队列，只一端用栈。

判断步骤：

① 是不是“先来的先处理”？→ 队列
② 是不是“求最短距离/层数”？→ BFS 队列
③ 是不是“维护最近一段”？→ 滑动窗口队列

③ 必背模板：STL 队列 + BFS 骨架

#include <queue>
queue<int> q;
q.push(s); visited[s] = true;
while (!q.empty()) {
    int u = q.front(); q.pop();          // ⭐ 取队头并出队
    for (int v : adj[u])                 // 遍历邻居
        if (!visited[v]) { visited[v] = true; q.push(v); }   // ⭐ 未访问的入队尾
}

④ 必背模板：手写循环队列（避免假溢出）

const int N = 1005;
int q[N], head = 0, tail = 0;
void push(int x) { q[tail] = x; tail = (tail + 1) % N; }   // ⭐ 取模回绕
int pop() { int v = q[head]; head = (head + 1) % N; return v; }
bool empty() { return head == tail; }

⑤ 思路点拨：拿到题第一步想什么

1. 确认端点：一端进一端出 → 队列；只一端 → 栈；

2. 判空再出队：front()/pop() 前先 !empty()，否则 RE；

3. BFS 记得打 visited：否则重复入队、甚至死循环；

4. 滑动窗口用“队尾入、队头超时的出”；

5. 空间紧张/持续进出用循环队列取模。

📚 更多同类真题（来自真题库，点击展开）

🔍 看一个例子

例：BFS 求无权图最短路（队列骨架）。 把起点入队，每次取队头把它未访问的邻居入队，第一次到达终点时的步数就是最短步数。

#include <iostream>
#include <queue>
using namespace std;
const int N = 1005;
int adj[N][N], vis[N], dist[N], n;
void bfs(int s) {
    queue<int> q; q.push(s); vis[s] = 1; dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();               // 取队头并出队
        for (int v = 1; v <= n; v++)
            if (adj[u][v] && !vis[v]) {           // 未访问的邻居
                vis[v] = 1; dist[v] = dist[u] + 1;
                q.push(v);                         // 入队尾，保证“近的先处理”
            }
    }
}

下面对照一张图理解“先进先出”：

🪤 常见错误

1. 空队出队/取队头：head==tail 时 q[head] 越界 RE，务必先判空。

2. STL pop() 当返回值：int x = q.pop(); 错，pop 无返回值，要先 q.front() 再 q.pop()。

3. 手写队列假溢出：head/tail 一直 + 不回绕，很快越界；用循环队列取模。

4. BFS 忘打 visited：同一点反复入队，TLE 甚至死循环。

5. 队列和栈混用：求最短距离用队列（BFS），不是栈（那是 DFS）。

6. 下标顺序写反：入队 q[tail++]=x（先放后加），出队 x=q[head++]（先取后加），反了会丢数据。

✅ 自测

1. 队列和栈最核心的区别是什么？各举一个生活例子。

2. 手写队列时 head 和 tail 分别指向什么？队空怎么判断？

3. 什么是“假溢出”？循环队列怎么用取模解决？

4. 为什么 BFS 必须用队列而不是栈？

5. 用 STL queue 取值，为什么不能写 int x = q.pop();？

6. BFS 里 visited 数组的作用是什么？不写会怎样？

7. 滑动窗口统计“最近 K 秒”为什么用队列？

这个模型讲什么

队列的核心性质是“先进先出（FIFO）”：队尾进、队头出。底层可用数组（head/tail 指针）或 STL queue。

// 手写数组队列
int q[100005], head = 0, tail = 0;
q[tail++] = x;          // 入队：放到 tail，tail++
int v = q[head++];     // 出队：取 head，head++
bool empty = (head == tail);
int f = q[head];       // 看队头不弹出

// STL 队列
#include <queue>
queue<int> q;
q.push(x);             // 入队（队尾）
int f = q.front();     // 看队头
q.pop();               // 出队（无返回值！）

做题时怎么用

关键概念：

• 队头 / 队尾：两个端点分开，入队在尾、出队在头；
• 判空：front()/pop() 前先 !empty()，否则 RE；
• 假溢出：head/tail 只增不减会越界，固定容量用循环队列 (指针+1)%N 回绕。

易错：STL pop() 不返回值，先 front() 再 pop()；手写队列下标顺序写反会丢数据。

练这几道（从易到难）

P3156 询问学号（队列入门）→ P1540 机器翻译（队列作缓冲区）→ P1996 约瑟夫问题（环形模拟）。

这个模型讲什么

队列最大的价值是“按到达顺序 / 一层一层”处理，三大应用场景：

① BFS 广度优先搜索（队列的终极用途）：起点入队，取队头把它未访问的邻居入队尾，出队顺序天然按“距离”从小到大——这就是最短步数/连通块的底层。

queue<int> q; q.push(s); vis[s] = 1;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u])
        if (!vis[v]) { vis[v] = 1; q.push(v); }
}

② 滑动窗口 / 时间窗口：队尾不断入新元素，队头超出窗口范围的就出队。例：统计“最近 K 秒”内的事件数。

③ 缓冲区：容量固定时，满了就“队头出、队尾进”（如机器翻译的内存单词表）。

关键提醒

• BFS 必须打 visited，否则同点反复入队会死循环；
• 队列是 BFS，栈（递归）是 DFS，别混；
• 滑动窗口“队头超时出队”用时间戳或序号判断。

练这几道（从易到难）

P2058 海港（时间窗 + 队列）→ P1160 队列安排（位置插入模拟）→ P1540 机器翻译（队列缓冲）。