竞极 Ace

3 队列

GESP C++ 六级：队列精讲

核心目标：理解队列的先进先出（FIFO）特性，掌握队列的数组模拟（含循环队列）与 STL queue 的使用，熟悉双端队列 deque 和优先队列 priority_queue 的基本操作，能运用队列解决 BFS、模拟、滑动窗口等经典问题。
队列是“两头开口”的容器——先进先出（FIFO）；队尾入队，队头出队；数组模拟要处理假溢出，循环队列用取模；STL 用 push/pop/front/back/empty/size；BFS、模拟、单调队列是三大高频应用。

一、考纲定位

根据 CCF 官方考纲，GESP 六级数据结构部分明确要求掌握栈和队列的基本概念与操作，以及它们在算法问题中的应用。

队列在六级考试中的考查分布：

考点 重要程度 典型考法
队列的基本概念（FIFO） ★★★★★ 选择题高频
队列的数组模拟实现 代码填空、程序阅读
循环队列（取模） 选择题、代码填空
STL queue 的使用 ★★★★☆ 编程题
双端队列 deque 编程题、选择题
优先队列 priority_queue
BFS 广度优先搜索 ★★★★★ 编程题高频
滑动窗口最大值（单调队列） ★★★★☆ 编程题
队列与栈的区别 ★★★★★ 选择题

二、队列的基本概念

2.1 什么是队列

队列（Queue）是一种只能在一端插入、另一端删除的线性数据结构。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。

队列的核心特性是先进先出（First In First Out，FIFO）：最先入队的元素最先出队。

直观比喻：队列就像排队买票，先来的人先买到票，后来的人排在队尾。

2.2 队列的基本操作

操作 英文 含义
入队 push / enqueue 在队尾插入一个元素
出队 pop / dequeue 删除队头元素
取队头 front 读取队头元素（不删除）
取队尾 back 读取队尾元素（不删除）
判空 empty 判断队列是否为空
求大小 size 返回队列中元素个数

2.3 队列 vs 栈

对比项 队列 栈
操作端 队尾入队，队头出队 只在栈顶操作
特性 先进先出（FIFO） 后进先出（LIFO）
插入 push（队尾） push（栈顶）
删除 pop（队头） pop（栈顶）
典型应用 BFS、任务调度、缓冲区 括号匹配、表达式求值、递归

三、队列的数组模拟实现

3.1 普通数组模拟（存在假溢出）

用数组 q[] 存储元素，front 指向队头，rear 指向队尾的下一个位置。

const int N = 100005;
int q[N];
int front = 0, rear = 0;   // 初始为空

// 入队
void push(int x) {
    q[rear++] = x;
}

// 出队
void pop() {
    front++;
}

// 取队头
int getFront() {
    return q[front];
}

// 判空
bool empty() {
    return front == rear;
}

// 大小
int size() {
    return rear - front;
}

问题：随着入队和出队，front 和 rear 不断增大，最终 rear 会超出数组范围，但数组前面可能还有空闲空间。这就是假溢出。

3.2 循环队列（解决假溢出）

循环队列通过取模运算让 front 和 rear 在数组范围内循环移动。

const int N = 100005;
int q[N];
int front = 0, rear = 0;   // 初始为空

// 入队
bool push(int x) {
    if ((rear + 1) % N == front) return false;   // 队满
    q[rear] = x;
    rear = (rear + 1) % N;
    return true;
}

// 出队
bool pop() {
    if (front == rear) return false;   // 队空
    front = (front + 1) % N;
    return true;
}

// 取队头
int getFront() {
    return q[front];
}

// 判空
bool empty() {
    return front == rear;
}

// 大小
int size() {
    return (rear - front + N) % N;
}

关键点：

  • 循环队列通常牺牲一个存储单元来区分队空和队满。
  • 队空：front == rear。
  • 队满：(rear + 1) % N == front。
  • 入队：q[rear] = x; rear = (rear + 1) % N;
  • 出队：front = (front + 1) % N;

3.3 真题示例（代码填空）

循环队列中，判断队满的条件是（ ）。
A. front == rear
B. (rear + 1) % N == front
C. rear == N - 1
D. front == 0
答案：B

四、STL queue 的使用

C++ 标准库提供了 queue 容器，使用前需要包含头文件 <queue>。

4.1 基本用法

#include <queue>
using namespace std;

queue<int> q;        // 创建一个存储 int 的队列

q.push(10);          // 入队
q.push(20);
q.push(30);

cout << q.front() << endl;   // 输出 10（队头）
cout << q.back() << endl;    // 输出 30（队尾）
q.pop();                      // 弹出队头
cout << q.front() << endl;   // 输出 20

cout << q.size() << endl;    // 输出 2
cout << q.empty() << endl;   // 输出 0（false，不为空）

4.2 常用函数

函数 作用 示例
push(x) 入队 q.push(10);
pop() 出队（无返回值） q.pop();
front() 取队头 int x = q.front();
back() 取队尾 int x = q.back();
empty() 判空 if (q.empty())
size() 求大小 int n = q.size();

重要注意：pop() 只删除队头元素，不返回被删除的值。如果需要获取队头值，必须先 front() 再 pop()。

int x = q.front();   // 先取
q.pop();             // 再删

4.3 使用前必须判空

if (!q.empty()) {
    int x = q.front();
    q.pop();
}

直接对空队列调用 front() 或 pop() 是未定义行为，可能导致程序崩溃。

五、双端队列 deque

deque（double-ended queue）是双端队列，允许在两端进行插入和删除操作。

5.1 基本用法

#include <deque>
using namespace std;

deque<int> dq;

dq.push_back(10);    // 队尾入队
dq.push_front(20);   // 队头入队

cout << dq.front() << endl;   // 20
cout << dq.back() << endl;    // 10

dq.pop_back();       // 队尾出队
dq.pop_front();      // 队头出队

5.2 常用函数

函数 作用
push_back(x) 队尾插入
push_front(x) 队头插入
pop_back() 队尾删除
pop_front() 队头删除
front() 取队头
back() 取队尾
empty() 判空
size() 求大小

5.3 与 queue 的区别

对比项 queue deque
插入端 只能队尾 队头、队尾都可以
删除端 只能队头
访问队尾 back()
访问队头 front()
适用场景 普通队列 滑动窗口、双端操作

六、优先队列 priority_queue

priority_queue 是优先队列，每次出队的都是优先级最高的元素。默认是大根堆（最大值先出）。

6.1 基本用法

#include <queue>
using namespace std;

priority_queue<int> pq;   // 默认大根堆

pq.push(3);
pq.push(1);
pq.push(4);

cout << pq.top() << endl;   // 4（最大值）
pq.pop();
cout << pq.top() << endl;   // 3

6.2 小根堆

priority_queue<int, vector<int>, greater<int>> pq;   // 小根堆

6.3 常用函数

函数 作用
push(x) 插入元素
pop() 删除堆顶
top() 取堆顶（优先级最高）
empty() 判空
size() 求大小

6.4 应用场景

  • 任务调度：每次处理优先级最高的任务。
  • 求第 k 大/小元素。
  • Dijkstra 最短路算法。

七、经典应用一：BFS 广度优先搜索

7.1 问题描述

给定一个迷宫（二维网格），求从起点到终点的最短步数。

7.2 解题思路

BFS 使用队列逐层扩展，保证第一次到达终点时步数最少。

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int x, y, step;
};

int n, m;
char maze[105][105];
bool visited[105][105];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int bfs(int sx, int sy, int ex, int ey) {
    queue<Node> q;
    q.push({sx, sy, 0});
    visited[sx][sy] = true;

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        if (cur.x == ex && cur.y == ey) {
            return cur.step;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                !visited[nx][ny] && maze[nx][ny] != '#') {
                visited[nx][ny] = true;
                q.push({nx, ny, cur.step + 1});
            }
        }
    }
    return -1;   // 无法到达
}

7.3 复杂度

时间 O(n × m)，空间 O(n × m)。

7.4 真题示例

用 BFS 求迷宫最短路径，队列中存储的是（ ）。
答案：当前节点的坐标和步数。

八、经典应用二：模拟排队

8.1 问题描述

模拟银行叫号系统：有 n 个顾客，每个顾客有到达时间和办理业务所需时间，求平均等待时间。

8.2 解题思路

用队列存储等待的顾客，按到达时间依次处理。

struct Customer {
    int arrive, need;
};

queue<Customer> q;
int currentTime = 0;
int totalWait = 0;

while (!q.empty() || 还有顾客未到达) {
    // 将已到达的顾客加入队列
    while (还有顾客未到达 && 顾客到达时间 <= currentTime) {
        q.push(该顾客);
    }

    if (q.empty()) {
        currentTime = 下一个顾客的到达时间;   // 空闲等待
        continue;
    }

    Customer c = q.front();
    q.pop();

    totalWait += currentTime - c.arrive;   // 等待时间
    currentTime += c.need;                  // 办理业务
}

8.3 关键点

  • 队列保证先到先服务。
  • 处理空闲时间：如果队列为空，时间跳到下一个顾客到达时间。

九、经典应用三：滑动窗口最大值（单调队列）

9.1 问题描述

给定一个数组和窗口大小 k，求每个窗口中的最大值。

9.2 解题思路

用双端队列维护一个单调递减的队列，队头始终是当前窗口的最大值。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;   // 存下标
    vector<int> res;

    for (int i = 0; i < nums.size(); i++) {
        // 移除超出窗口的元素
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        // 维护单调递减
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // 窗口形成后记录最大值
        if (i >= k - 1) {
            res.push_back(nums[dq.front()]);
        }
    }
    return res;
}

9.3 复杂度

每个元素最多入队一次、出队一次，时间复杂度 O(n)。

9.4 关键点

  • 队列中存下标，方便判断是否超出窗口。
  • 队头是当前窗口最大值的下标。
  • 保持队列单调递减：新元素入队前，弹出所有比它小的队尾元素。

十、GESP 六级队列真题精讲

真题1：队列的基本操作（选择题）

以下关于队列的说法，正确的是（ ）。
A. 队列是后进先出的数据结构
B. 队列只能在队头进行插入和删除
C. 队列的插入操作在队尾进行，删除操作在队头进行
D. 队列可以随机访问任意元素
答案：C

真题2：循环队列判空判满（选择题）

循环队列中，判断队空的条件是（ ）。
A. front == rear
B. (rear + 1) % N == front
C. front == 0
D. rear == N - 1
答案：A

真题3：BFS 求最短路径（编程题）

给定一个 n×m 的迷宫，# 表示墙，. 表示通路，求从起点 S 到终点 E 的最短步数。

#include <iostream>
#include <queue>
using namespace std;

struct Node { int x, y, step; };
int n, m;
char maze[105][105];
bool vis[105][105];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int main() {
    cin >> n >> m;
    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
            if (maze[i][j] == 'S') { sx = i; sy = j; }
            if (maze[i][j] == 'E') { ex = i; ey = j; }
        }
    }

    queue<Node> q;
    q.push({sx, sy, 0});
    vis[sx][sy] = true;

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        if (cur.x == ex && cur.y == ey) {
            cout << cur.step << endl;
            return 0;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                !vis[nx][ny] && maze[nx][ny] != '#') {
                vis[nx][ny] = true;
                q.push({nx, ny, cur.step + 1});
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

真题4：滑动窗口最大值（代码填空）

下面代码用单调队列求滑动窗口最大值，横线处应填入（ ）。

while (!dq.empty() && nums[dq.back()] <= nums[i]) {
 ______;
}

答案：dq.pop_back()

十一、易错点汇总

  1. 空队列调用 front/pop：必须先 empty() 判断。
  2. STL pop 不返回值：pop() 只删除，不返回，需要先 front()。
  3. 循环队列判空判满混淆：队空 front == rear，队满 (rear + 1) % N == front。
  4. 循环队列取模方向错误：入队 rear = (rear + 1) % N，出队 front = (front + 1) % N。
  5. BFS 忘记标记 visited：入队时就要标记，否则会重复入队导致死循环。
  6. BFS 步数更新错误：步数在入队时更新，cur.step + 1。
  7. 单调队列存值还是存下标：通常存下标，方便判断是否超出窗口。
  8. 单调队列维护方向错误：求最大值维护单调递减，求最小值维护单调递增。
  9. 优先队列小根堆写法：priority_queue<int, vector<int>, greater<int>>。
  10. deque 与 queue 混淆：deque 两端都可以操作，queue 只能队尾入队头出。
  11. 数组模拟队列大小不足：数组要开足够大，防止溢出。
  12. 模拟排队空闲处理：队列为空时，时间跳到下一个顾客到达时间。

十二、速查表

需求 数组模拟 STL queue STL deque priority_queue
定义 int q[N]; int front=0, rear=0; queue<int> q; deque<int> dq; priority_queue<int> pq;
入队 q[rear++] = x; q.push(x); push_back(x) / push_front(x) pq.push(x);
出队 front++; q.pop(); pop_front() / pop_back() pq.pop();
取队头 q[front] q.front(); dq.front(); pq.top();
取队尾 q[rear-1] q.back(); dq.back(); 无
判空 front == rear q.empty(); dq.empty(); pq.empty();
大小 rear - front q.size(); dq.size(); pq.size();
头文件 无 <queue> <deque> <queue>
循环队列 (rear+1)%N == front 判满 — — —
BFS 用队列逐层扩展 q.push() / q.pop()
滑动窗口 用双端队列维护单调 — deque 实现
优先队列 用堆实现 — 默认大根堆，greater<int> 小根堆

十三、总结

队列是 GESP 六级数据结构模块的核心内容。

  1. 队列是先进先出（FIFO）的线性结构，队尾入队，队头出队。
  2. 数组模拟队列：front 和 rear 记录队头和队尾，注意假溢出。
  3. 循环队列用取模解决假溢出：队空 front == rear，队满 (rear+1)%N == front。
  4. STL queue：push 入队、pop 出队、front 取队头、back 取队尾、empty 判空、size 求大小。
  5. pop() 不返回被删除的值，需要先 front() 再 pop()。
  6. deque 是双端队列，两端都可以插入和删除。
  7. priority_queue 是优先队列，默认大根堆，每次出队优先级最高的元素。
  8. BFS 用队列逐层扩展，保证第一次到达终点时步数最少。
  9. 滑动窗口最大值用单调队列（双端队列）维护，时间复杂度 O(n)。
  10. 模拟排队用队列保证先到先服务，注意处理空闲时间。

复习建议：先把数组模拟队列和 STL queue 的基本操作写熟；再重点攻克循环队列的判空判满和取模操作；然后理解 deque 和 priority_queue 的用法；最后练习 BFS 和滑动窗口两个经典应用。考试中先判断题目考的是基本操作、循环队列、BFS 还是单调队列，再套用对应模板作答。