队列

队列的原理与实现：先进先出的基础数据结构。

  • 队列
  • 数据结构

一句话算法

队列从一端进、另一端出，先进入的元素先被处理。

问题模型

我们需要维护一列等待处理的元素，并支持这些操作：

  • 在队尾加入元素。
  • 从队头删除元素。
  • 查询队头元素。
  • 查询队尾元素。
  • 判断队列是否为空。

队列的关键限制是：新元素只能排到队尾，处理元素只能从队头开始。

核心直觉

队列就是排队。

先来的人站在前面，也应该先被服务。这个限制让队列适合处理“按到达顺序逐层展开”的问题，例如 BFS、模拟排队、滑动窗口中的候选元素维护。

“队列”

队列是一种只允许在队尾插入、队头删除的线性结构，满足先进先出。

算法步骤

用数组实现队列时，维护两个指针：

  • head 指向当前队头元素。
  • tail 指向队尾元素后面的第一个空位置。
  • 当前队列区间是 [head, tail)。

基础操作：

  1. 入队：把元素写入 q[tail]，然后 tail++。
  2. 出队：直接 head++。
  3. 队头：读取 q[head]。
  4. 队尾：读取 q[tail - 1]。
  5. 空队列：判断 head == tail。

算法证明

关键不变量： 当前队列中的元素按顺序存放在数组区间 [head, tail)。

  1. 初始时 head = tail = 0，区间为空，不变量成立。
  2. 入队时，新元素写在 tail 位置，正好接在所有旧元素之后，所以它成为最后一个等待处理的元素。
  3. 出队时，删除的是 head 位置，也就是当前最早进入队列的元素。head++ 后，剩余区间仍然保持原顺序。

因此每次出队拿到的都是当前最早入队且尚未删除的元素，队列满足先进先出。

复杂度分析

  • 入队、出队、查询队头、查询队尾、判断空队列：O(1)O(1)。
  • 空间复杂度：O(n)O(n)，其中 nn 是队列容量。

代码实现

cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

        const int maxn = 100000 + 5;

template <typename T = int, int siz = maxn>
struct MyQueue {
    T q[siz + 5];
    int head = 0, tail = 0;  // 当前队列区间为 [head, tail)

    void clear() { head = tail = 0; }

    void push(const T& x) { q[tail++] = x; }

    void pop() { ++head; }

    // 竞赛中有时需要从队尾删除元素，例如单调队列。
    void pop_back() { --tail; }

    T& front() { return q[head]; }

    const T& front() const { return q[head]; }

    T& back() { return q[tail - 1]; }

    const T& back() const { return q[tail - 1]; }

    bool empty() const { return head == tail; }

    int size() const { return tail - head; }
};

测试用例

输入一组操作：

push 2
push 7
front
pop
front
back

执行过程：

操作 队列内容 输出
push 2 2
push 7 2 7
front 2 7 2
pop 7
front 7 7
back 7 7

应用分类详解

队列的本质是维护“按时间顺序等待处理的对象”。

一、逐层扩展

典型模式： 一个状态会扩展出下一批状态，并且要求先处理距离更近或步数更少的状态。

识别信号： 最短步数、层数、扩散、从起点向外扩展。

核心建模： 每个状态入队一次，队头状态先扩展，后产生的状态排到队尾。

应用场景 经典题目 核心思路
BFS 最短路 网格最短路、迷宫 队列保证先到达的层先被处理
拓扑排序 DAG 入度为零的点 入度变为零的点排队等待处理

二、模拟排队过程

典型模式： 题目直接描述排队、缓存、传递、轮流处理。

识别信号： 先进先出、轮到某人、队首出列、队尾加入。

核心建模： 按题意把对象入队和出队，队列顺序就是事件发生顺序。

应用场景 经典题目 核心思路
缓存模拟 luogu-P1540 新词进入队尾，最旧词从队头移除
卡片模拟 noiopenjudge-ch0304/2406 按队头出队和队尾入队模拟

三、窗口候选维护

典型模式： 只关心一个移动区间中的候选元素。

识别信号： 滑动窗口、固定长度区间、区间最大值或最小值。

核心建模： 普通队列维护元素顺序，单调队列进一步维护候选优劣关系。

应用场景 经典题目 核心思路
滑动窗口最值 luogu-P1886 保留窗口内可能成为答案的元素
单调队列优化 最大子段和限制长度 队头过期弹出，队尾劣者弹出

经典例题

参考