登录以参加训练计划

一、队列的基本概念

举个例子

• ​排队打饭：队头的同学先打饭，后来的同学站队尾。
• 所有需要先到先出，后到后出的场景。排队的场景。

二、队列的种类

1. 普通队列（queue）

• ​常用方法：​：q.push();入队，q.front();读取队头，q.pop();删除队头元素，q.back();获取队尾元素，q.pop_back();删除队尾元素，q.empty();如果队列为空，返回true，q.size();获取队列中元素个数。

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

int main() {
    queue<int> q;
    for (int i = 1; i <= 5; ++i) {
        q.push(i);
    }

    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    // 输出：1 2 3 4 5
    return 0;
}

2. 优先队列（priority_queue）

优先队列是一种特殊的数据结构，它像一个​“VIP排队室”​：每次取出队列中优先级最高的元素。

​2.1 常用方法：​：

q.top();读取队头，q.pop();队头出队，q.empty();如果队列为空，返回true，q.size();获取队列中元素个数。注意：优先队列通过堆结构动态维护最值，而非全排序。​push()：O(log n) 时间插入并调整堆。top()：O(1) 时间取最值。pop()：O(log n) 时间删除最值并调整堆。

​2.2 优先队列两种类型：​：

因为优先队列的底层实现通常基于堆（Heap）​结构，而堆有两种经典形式：大顶堆（Max-Heap）​和 小顶堆（Min-Heap）​。所以优先队列有两种形式：

• 1，大顶堆优先队列：每次弹出最大值，适于的场景如：任务调度（优先处理高优先级）
• 2，小顶堆优先队列：每次弹出最小值，适用场景如：最短路径（Dijkstra算法。

2.3 c++中代码实现：​：

1. 默认大顶堆：

#include <queue>
using namespace std;

priority_queue<int> max_heap; // 默认大顶堆
max_heap.push(3);
max_heap.push(1);
max_heap.push(4);
// 输出：4 3 1（每次弹出最大值）

2. 自定义小顶堆：

priority_queue<int, vector<int>, greater<int>> min_heap; // 小顶堆
min_heap.push(3);
min_heap.push(1);
min_heap.push(4);
// 输出：1 3 4（每次弹出最小值）

3. 自定义优先级规则 可以通过模板参数指定比较函数，例如：

​降序排列​（大顶堆）：greater ​升序排列​（小顶堆）：less ​自定义类型：需定义比较运算符（如结构体或类）。

struct Node {
    int priority;
    string name;
    bool operator<(const Node& other) const {
        return priority < other.priority; // 大顶堆：优先级高的先出
    }
};

priority_queue<Node> task_queue;
task_queue.push({3, "紧急任务"});
task_queue.push({1, "普通任务"});
// 输出：3 → 1

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

int main() {
    // 大顶堆：每次取最大值
    priority_queue<int> max_heap;
    for (int i = 1; i <= 5; ++i) {
        max_heap.push(i);
    }

    cout << "大顶堆（最大值先出）：";
    while (!max_heap.empty()) {
        cout << max_heap.top() << " ";
        max_heap.pop();
    }
    // 输出：5 4 3 2 1

    // 小顶堆：每次取最小值
    priority_queue<int, vector<int>, greater<int>> min_heap;
    for (int i = 5; i >= 1; --i) {
        min_heap.push(i);
    }

    cout << "\n小顶堆（最小值先出）：";
    while (!min_heap.empty()) {
        cout << min_heap.top() << " ";
        min_heap.pop();
    }
    // 输出：1 2 3 4 5

    return 0;
}

3. 双端队列（queue）

双端队列（Double-Ended Queue，简称 deque）是一种允许在两端进行插入和删除操作的线性数据结构。双端队列就像一个可前后开合的购物车，你可以从前面装货（push_front），也可以从后面卸货（pop_back），还能随时查看最前面或最后面的商品（front()、back()）。适用于需要频繁操作两端的场景（如滑动窗口、队列反转、缓存淘汰策略）。

操作名称	​说明	代码示例	​时间复杂度
​push_back(val)	在尾部插入元素	dq.push_back(10);	O(1)
push_front(val)	在头部插入元素	dq.push_front(20);
pop_back()	删除并返回尾部元素	int x = dq.pop_back();
pop_front()	删除并返回头部元素	int x = dq.pop_front();
​front()	返回头部元素（不删除）	int x = dq.front();
back()	返回尾部元素（不删除）	int x = dq.back();
​size()	返回元素个数	int s = dq.size();
​empty()	判断是否为空	bool e = dq.empty();

双端队列应用场景： 滑动窗口最大值 题目：给定一个整数数组和一个窗口大小 k，返回每个窗口中的最大值。 解决思路：用双端队列维护当前窗口内的可能最大值索引。

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // 存储索引
    vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        // 移除队列中比当前元素小的索引（因为它们不可能成为最大值）
        while (!dq.empty() && nums[i] >= nums[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // 移除超出窗口范围的索引
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

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

int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    // 输出：[3,3,5,6,7]
    for (int x : res) cout<< x << " ";
    return 0;
}

我们在后续许多算法中，都会用到队列，如BFS，dijkstra算法。