C++(STL)--queue（队列）priority_queue（优先队列）dequeue(双端队列)

1.queue

queue 是 先进先出（FIFO, First In First Out） 的数据结构，类似于现实生活中的排队系统。

包含头文件： 

#include <queue>

1.1创建方式以及常用操作（代码示例）：

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);

    std::cout << "队头: " << q.front() << std::endl; // 10
    std::cout << "队尾: " << q.back() << std::endl;  // 30

    q.pop(); // 删除 10

    std::cout << "新队头: " << q.front() << std::endl; // 20

    return 0;
}

1.2 补充：

默认情况下，queue 的底层容器是 deque（双端队列），但你可以手动更改为 list。

std::queue<int> q; // 默认使用 deque 作为底层容器
//等价于
std::queue<int, std::deque<int>> q;

queue 也可以使用 list

std::queue<int, std::list<int>> q; // 使用 list 作为底层容器

deque 和 list 的区别

 2.双端队列（deque，Double-Ended Queue）

双端队列（deque） 是一种可以在两端（队头和队尾）都能快速插入和删除的队列。它结合了栈（Stack）和队列（Queue）的特点，既可以当作栈（LIFO），也可以当作队列（FIFO），在 C++ STL 中，std::deque 是 一个动态数组，支持两端高效操作，但在中间插入删除的性能较 list 差。

2.1 deque 的主要特点

• 可以在两端插入和删除元素，效率高（push_front() 和 push_back()）。
• 支持随机访问（像 vector 一样，使用 operator[] 或 at()）

at() 是 C++ STL 容器（如 vector、deque）提供的边界检查访问方法，与 operator[] 类似，但 at() 在访问越界时会抛出异常 std::out_of_range，避免程序崩溃。

什么时候用 at()？

如果你确定索引不会越界，用 operator[] 性能更好（不会有异常处理的额外开销）,如果索引可能越界，建议用 at() 以防止程序崩溃。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq = {10, 20, 30, 40};

    std::cout << "索引 2 的元素: " << dq.at(2) << std::endl; // 输出 30

    try {
        std::cout << "尝试访问越界元素: " << dq.at(10) << std::endl;
    } catch (const std::out_of_range& e) {
        std::cerr << "异常: " << e.what() << std::endl;
    }

    return 0;
}

• 底层实现是动态分段数组（不像 vector 需要连续内存）。
• 不支持 list 的 splice() 操作（因为 deque 不是链表）。

2.2 常用操作

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;

    // 在两端插入元素
    dq.push_back(10);  // 末尾插入
    dq.push_front(20); // 头部插入
    dq.push_back(30);

    std::cout << "队头: " << dq.front() << std::endl; // 20
    std::cout << "队尾: " << dq.back() << std::endl;  // 30

    // 访问元素
    std::cout << "第一个元素: " << dq[0] << std::endl; // 20

    // 删除元素
    dq.pop_front(); // 移除队头 20
    dq.pop_back();  // 移除队尾 30

    std::cout << "剩余元素: " << dq.front() << std::endl; // 10

    return 0;
}

3.priority_queue（优先队列） 

3.1 基本概念

std::priority_queue<int> 默认是 「大顶堆（Max Heap）」，即优先级最高（数值最大）的元素排在队列顶部（top() 位置）

priority_queue 默认使用 vector

std::priority_queue<int> pq; // 默认使用 vector 作为底层容器，并且是最大堆（大顶堆）
//等价于
std::priority_queue<int, std::vector<int>, std::less<int>> pq;

代码示例： 

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq; // 默认是大顶堆

    pq.push(10);
    pq.push(50);
    pq.push(20);

    std::cout << "队列顶部: " << pq.top() << std::endl; // 50（最大值）

    pq.pop(); // 移除 50

    std::cout << "新队列顶部: " << pq.top() << std::endl; // 20

    return 0;
} 为什么移除的是50 不是10

3.2 自定义结构体排序

如果存储的是自定义类型（如 struct），需要提供自定义比较函数。

方式1：重载 <（默认是大顶堆）

#include <iostream>
#include <queue>
#include <vector>

struct Person {
    std::string name;
    int age;

    // 定义 < 运算符，使 age 较大的元素优先级高
    bool operator<(const Person& other) const {
        return age < other.age; // 年龄越大，优先级越高
    }
};

int main() {
    std::priority_queue<Person> pq;

    pq.push({"Alice", 30});
    pq.push({"Bob", 25});
    pq.push({"Charlie", 35});

    std::cout << "年龄最大的人: " << pq.top().name << std::endl; // Charlie

    return 0;
}

方式2：使用 struct 作为比较器

#include <iostream>
#include <queue>
#include <vector>

struct Person {
    std::string name;
    int age;
};

struct Compare {
    bool operator()(const Person& a, const Person& b) {
        return a.age > b.age; // 年龄小的优先
    }
};

int main() {
    std::priority_queue<Person, std::vector<Person>, Compare> pq;

    pq.push({"Alice", 30});
    pq.push({"Bob", 25});
    pq.push({"Charlie", 35});

    std::cout << "年龄最小的人: " << pq.top().name << std::endl; // Bob

    return 0;
}

3.3 常用函数