队列、双端队列与单调队列（Queue, Deque & Monotonic Queue）

作者： 作者的头像   huolong , 时间：2026-08-21 11:49:39 , 所有人可见, 阅读  42

队列、双端队列与单调队列

一、 队列（Queue）的基本概念

1.1 定义与特性：先进先出 (FIFO)

队列是一种遵循先进先出（First-In, First-Out，简称 FIFO）原则的线性数据结构。

这完全符合我们日常生活中排队的经验： * 入队 (Enqueue)：新来的人总是自觉站到队尾（Rear/Back）。 * 出队 (Dequeue)：办理完业务的人，总是排在队首（Front）的人先离开并接受服务。

最先进入队列的元素，最先被移出。 在队列结构中，允许插入（入队）的一端称为队尾，允许删除（出队）的一端称为队首。

          Front ──> [ Alice ]  <-- 队首元素（最先出队）
                    [  Bob  ]
           Rear ──> [ Carol ]  <-- 队尾元素（最后入队）

1.2 核心操作

队列的操作集虽然与栈类似，但其行为体现了严格的 FIFO 特性： * push(x)：将元素 $x$ 加入队尾。 * pop()：移除/弹出队首元素。 * front()：查询并返回队首元素的值。 * back()：查询并返回队尾元素的值。 * empty()：判断队列是否为空。 * size()：返回队列中当前的有效元素数量。

1.3 C++ 标准库实现：std::queue

在 C++ 中，标准模板库（STL）提供了 std::queue。它同样是一个容器适配器（默认基于 std::deque 封装），限制了中部操作，只开放符合 FIFO 原则的接口。

⚠️ WARNING（安全防护） 对一个空队列执行 front()、back() 或 pop() 操作属于未定义行为（Undefined Behavior, UB），会导致程序运行崩溃。在执行操作前，必须先通过 !q.empty() 进行安全检查。

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    queue<string> q; // 声明一个存放 string 元素的队列

    q.push("Alice");  // 入队, 队列（首->尾）: ["Alice"]
    q.push("Bob");    // 入队, 队列（首->尾）: ["Alice", "Bob"]
    q.push("Carol");  // 入队, 队列（首->尾）: ["Alice", "Bob", "Carol"]

    cout << "队列中元素数量: " << q.size() << "\n"; // 输出: 3
    cout << "当前的队首元素: " << q.front() << "\n"; // 输出: Alice
    cout << "当前的队尾元素: " << q.back() << "\n";  // 输出: Carol

    q.pop(); // Alice 出队, 队列: ["Bob", "Carol"]
    cout << "出队一次后的队首: " << q.front() << "\n"; // 输出: Bob

    q.pop(); // Bob 出队, 队列: ["Carol"]
    cout << "再次出队后的队首: " << q.front() << "\n"; // 输出: Carol

    // 安全防御示范
    if (!q.empty()) {
        q.pop();
    }

    return 0;
}
  • 时空复杂度：对于 std::queue，其所有基本操作（push, pop, front, back, empty, size）的时间复杂度均为 $O(1)$。空间复杂度为 $O(N)$（$N$ 为队列中实际存储的元素数量）。

1.4 典型应用与经典笔试题

队列的 FIFO 特性使其成为实现“按顺序处理”和“逐层拓扑扩展”等算法的核心工具，最典型的应用就是图论和搜索中的广度优先搜索 (BFS)。

1.4.1 笔试模拟：状态追踪判定

  • 问题： 一个初始为空的队列，依次将元素 A, B, C, D 压入队列，然后执行两次 pop 操作，再将元素 E 压入队列，最后再执行一次 pop 操作。此时的队首元素是 C。(判断对错)

  • 状态分析追踪：

  • push(A), push(B), push(C), push(D)：队列状态（首 $\to$ 尾）：[A, B, C, D]。
  • pop()：队首 A 出队。队列状态：[B, C, D]。
  • pop()：队首 B 出队。队列状态：[C, D]。
  • push(E)：E 从队尾入队。队列状态：[C, D, E]。
  • pop()：队首 C 出队。队列状态：[D, E]。
  • 结论：在最后一次 pop 之后，队列的队首元素实际上是 D，而不是 C（C 已经在最后一次 pop 操作中被移除）。因此，原命题错误。

1.4.2 树形分层：二叉树的层序遍历

  • 题意概括： 给定一棵二叉树，返回其节点值的层序遍历（即逐层地、从左到右访问所有节点）。

  • 核心分析： 二叉树层序遍历是队列 FIFO 特性的绝佳展现：

  • 将根节点放入队列。
  • 当队列不为空时，执行循环：
    • 获取当前队列的元素数量 $n$（这正是当前这一整层节点的数量）。
    • 循环 $n$ 次：从队首弹出一个节点，记录其数值；若该节点含有左/右子节点，将其依次加入队尾。
  • 依靠先进先出的性质，上一层节点出队完的同时，其子节点（下一层）刚好在队尾整齐排列，从而实现分层访问。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 二叉树节点定义
struct Node {
    int val;
    Node *l, *r;
    Node(int v) : val(v), l(nullptr), r(nullptr) {}
};

// 分层遍历
vector<vector<int>> levelOrder(Node* root) {
    vector<vector<int>> ans;
    if (!root) return ans;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int n = q.size(); // 当前层的节点数
        vector<int> cur;  // 存放当前层结果

        for (int i = 0; i < n; ++i) {
            Node* node = q.front();
            q.pop();
            cur.push_back(node->val);
            if (node->l) q.push(node->l);
            if (node->r) q.push(node->r);
        }
        ans.push_back(cur);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // 构建一个简单的二叉树:
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    Node* root = new Node(3);
    root->l = new Node(9);
    root->r = new Node(20);
    root->r->l = new Node(15);
    root->r->r = new Node(7);

    vector<vector<int>> res = levelOrder(root);
    for (const auto& level : res) {
        for (int val : level) cout << val << " ";
        cout << "\n";
    }
    return 0;
}
  • 时空复杂度分析：每个节点被入队和出队恰好一次，时间复杂度为 $O(N)$（$N$ 为树中节点的总数）。空间复杂度为 $O(W)$（$W$ 为树的最大宽度），因为队列在最坏情况下同时承载一整层的所有节点。

二、 双端队列（Deque）与栈/队列对比

2.1 双端队列 (Deque)

std::deque (Double-ended Queue，双端队列) 是一种更强大的序列容器。它允许在队首和队尾两端都进行 $O(1)$ 时间复杂度的插入和删除操作。

我们可以把它形象地想象成一列火车，两头都可以挂接或摘除车厢。 * 常用接口：push_front, pop_front, push_back, pop_back 以及支持随机索引访问的操作符 []。 * 应用抉择：若遇到需要在序列两端高频进行追加和移除操作的场景，std::deque 是相比于 std::vector（其头部操作为 $O(N)$ 级）更高效的底层容器。

2.2 栈与队列的本质区别

特征维度 栈 (Stack) 队列 (Queue)
核心原则 LIFO (后进先出 / Last-In First-Out) FIFO (先进先出 / First-In First-Out)
操作端点 仅能在栈顶 (Top)一端进行增删 在队尾 (Back)添加，在队首 (Front)删除
数据流动 $A, B, C \to$ 进栈 $\to C, B, A \to$ 出栈 $A, B, C \to$ 进队 $\to A, B, C \to$ 出队
时序效果 颠倒输入顺序 保持输入顺序
典型场景 括号匹配、表达式求值、DFS 的递归模拟 广度优先搜索 (BFS)、网络缓冲区、任务调度
  • 选型思路：
  • 当问题具有“撤销”、“返回”、“对称”或“深层嵌套”意味时，优先考虑栈。
  • 当问题强调“按顺序处理”、“公平排队”、“分层剥离扩展”时，优先考虑队列。

三、 单调队列 (Monotonic Queue)

3.1 定义与核心特性

单调队列一般基于双端队列 std::deque 实现。类似于单调栈，它要求队列内部元素从头到尾严格保持单调递增（或单调递减）。 但由于其“双端”开放的物理特性，单调队列额外支持从队首弹出陈旧元素，这使其成为了解决“滑动窗口最值问题”的黄金工具。

  • 滑动窗口最大值场景下的模拟逻辑： 为了维护当前窗口内的最大值，我们应当维护一个严格单调递减的队列（队列中通常存储的是元素的索引下标，以便于判定区间越界）：
  • 入队 (队尾)：当新元素 $v[i]$ 到来时，我们自队尾向内扫描，将所有小于或等于 $v[i]$ 的队尾元素下标全部弹出 (pop_back)。因为 $v[i]$ 诞生最晚且数值更大，在它生命周期内，前面那些较小的旧元素绝对不可能再成为窗口的最大值。随后将下标 $i$ 从队尾加入。
  • 出队 (队首)：随着窗口不断向右滑动，我们需要检查处于队首的那个下标是否已经“过期”（即下标是否超出了当前窗口的左边界：$q.front() \le i - k$）。若是，则将其从队首弹出 (pop_front)。
  • 获取答案：经过这两步维护，单调队列的队首元素 q.front() 所对应的数值始终是当前滑动窗口内的最大值。

3.2 典型应用：滑动窗口最大值 (Sliding Window Maximum)

  • 题意概括： 给定一个大小为 $N$ 的数组 $v$ 以及一个固定窗口大小 $k$。一个大小为 $k$ 的滑动窗口自左向右依次移动。每次只能看见窗口内的 $k$ 个数字，求窗口移动期间，每个时刻窗口内的最大值。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// v: 原始数组, k: 滑动窗口的大小
vector<int> maxSlidingWindow(const vector<int>& v, int k) {
    int n = v.size();
    if (n < k || k == 0) return {};

    vector<int> ans;
    deque<int> q; // 双端队列，存储数组的索引，保持其对应的数组数值单调递减

    for (int i = 0; i < n; ++i) {
        // 1. 移出队首已经失效（超出左侧边界）的陈旧索引
        if (!q.empty() && q.front() <= i - k) {
            q.pop_front();
        }

        // 2. 自队尾移出所有小于或等于当前新元素 v[i] 的元素下标，维护单调性
        while (!q.empty() && v[q.back()] <= v[i]) {
            q.pop_back();
        }

        // 3. 将当前新元素索引压入队尾
        q.push_back(i);

        // 4. 当滑动窗口已经完整形成（即扫描到第 k-1 个元素及之后），开始记录队首最大值
        if (i >= k - 1) {
            ans.push_back(v[q.front()]);
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> v = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> res = maxSlidingWindow(v, k);
    for (int x : res) {
        cout << x << " ";
    }
    cout << "\n"; // 输出: 3 3 5 5 6 7
    return 0;
}
  • 时空复杂度分析： 虽然循环中嵌套了 while 结构，但数组中每一个下标对应的元素最多只会执行一次入队与一次出队。因此总时间复杂度为严格的 $O(N)$（$N$ 为数组长度），空间复杂度为 $O(k)$（双端队列中最多同时存放 $k$ 个窗口下标）。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com