--queue（队列）priority_queue（优先队列）dequeue(双端队列))
目录1.queue1.1创建方式以及常用操作代码示例1.2 补充queue 也可以使用 listdeque 和 list 的区别2.双端队列dequeDouble-Ended Queue2.1 deque 的主要特点2.2 常用操作3.priority_queue优先队列3.1 基本概念priority_queue 默认使用 vector3.2 自定义结构体排序方式1重载 默认是大顶堆3.3 常用函数1.queuequeue是先进先出FIFO, First In First Out的数据结构类似于现实生活中的排队系统。包含头文件#include queue1.1创建方式以及常用操作代码示例#include iostream #include queue int main() { std::queueint 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::queueint q; // 默认使用 deque 作为底层容器 //等价于 std::queueint, std::dequeint q;queue也可以使用liststd::queueint, std::listint q; // 使用 list 作为底层容器deque和list的区别容器结构特点适合queue的原因deque动态数组双端都可以高效插入删除默认使用因为它支持快速的push/pop操作并且允许随机访问list双向链表每个元素都有前后指针适用于不需要随机访问但需要高效插入删除的场景2.双端队列dequeDouble-Ended Queue双端队列deque是一种可以在两端队头和队尾都能快速插入和删除的队列。它结合了栈Stack和队列Queue的特点既可以当作栈LIFO也可以当作队列FIFO在 CSTL 中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::dequeint 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::dequeint 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_queueint默认是「大顶堆Max Heap」即优先级最高数值最大的元素排在队列顶部top()位置priority_queue默认使用vectorstd::priority_queueint pq; // 默认使用 vector 作为底层容器并且是最大堆大顶堆 //等价于 std::priority_queueint, std::vectorint, std::lessint pq;代码示例#include iostream #include queue int main() { std::priority_queueint 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 不是103.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_queuePerson 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_queuePerson, std::vectorPerson, 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 常用函数
