队列CSP-J

💡 核心思想

队列是一种先进先出（FIFO）的数据结构，从队尾入队、从队首出队。在竞赛中，队列是 BFS 的核心数据结构。进阶应用包括单调队列（滑动窗口最值）和双端队列。

🎯 直觉理解

队列就像排队买票——先来的人先买到（先进先出）。单调队列就像一个VIP通道——如果你后面来了一个比你强的人，你就可以走了（因为在你之前他永远是更优选择）。

📝 算法流程

1. 基本操作：push, pop, front, back
2. 单调队列：维护单调性 + 窗口范围
3. 双端队列 deque：两端都可以进出

$$\text{单调队列：每个元素最多入队出队各一次，总计} O(n)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 单调队列：滑动窗口最小值
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    deque<int> dq; // 存下标
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) cout << a[dq.front()] << " ";
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目