【C++打怪之路Lv11】-- stack、queue和优先级队列
🌈 个人主页：白子寰
🔥 分类专栏：重生之我在学Linux，C++打怪之路，python从入门到精通，数据结构，C语言，C语言题集👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~）
目录
C++为什么要学习stack、queue和优先级队列
stack类
stack类的介绍
stack的基本操作
stack的模拟实现
queue类
queue类的介绍
queue的基本操作
queue的模拟实现
优先级队列
优先级队列的介绍
仿函数
什么是仿函数
为什么要有仿函数
优先级队列的使用
成员函数
排序准则
优先级队列的模拟实现
关于容器适配器
C++为什么要学习stack、queue和优先级队列
学习C++中的栈（stack）、队列（queue）和优先级队列（priority queue）对开发者来说非常重要，因为它们是常用的数据结构，在解决各种编程问题时提供了高效的方法。
以下是它们的核心作用和特点：
1. 栈（Stack）：
特点：后进先出（LIFO），即最后入栈的元素最先出栈。
应用：适用于函数调用、表达式求值、撤销操作等场景。例如，程序在执行递归调用时会用栈来存储函数状态。2. 队列（Queue）：
特点：先进先出（FIFO），即最先进入队列的元素最先被处理。
应用：适用于任务调度、消息处理、广度优先搜索等需要按顺序处理数据的场景。3. 优先级队列（Priority Queue）：
特点：元素按优先级排序，每次取出的是优先级最高的元素，而不是按插入顺序。
应用：适用于任务管理（例如操作系统中的任务调度）、最短路径算法（如Dijkstra算法）、数据流中找出Top K元素等场景。这些数据结构在C++中有标准库支持（如`<stack>`、`<queue>`和`<priority_queue>`），可以帮助开发者更高效地处理特定类型的问题，提高程序的可读性和性能。
stack类
stack类的介绍
stack是 C++ 标准模板库（STL）中的一个容器适配器，用于实现后进先出（LIFO）数据结构。它基于其他序列容器（如
deque、vector或list）构建，默认使用deque作为底层容器stack<int, vector<int>> st;注：
1、定义了一个名为 st 的栈（stack）
其中包含 int 类型的元素，并使用 vector<int> 作为其底层容器
2、
stack默认使用deque作为底层容器，但可以通过这种方式替换成其他容器3、特点 & 好处
- 该栈
st仍然保持stack的 后进先出 特性。- 使用
vector作为底层容器意味着栈的元素实际上存储在一个vector中，但只能通过stack提供的接口（如push()、pop()、top()等）访问。这样做的优势在于，如果对底层容器的特性（如内存管理或其他特定操作）有特殊需求，可以灵活选择适合的容器
stack的基本操作
push()：将元素压入栈顶。pop()：移除栈顶元素。top()：返回栈顶元素的引用。只能访问栈顶元素（通过top()），无法直接访问其他位置的元素empty()：判断栈是否为空。size()：返回栈中元素的个数
stack的模拟实现
namespace sky
{template<class T, class Container = vector<int>>class Stack{public:void push(const T& val){_con.push_back(val); // 压栈插入数据}void pop(){_con.pop_back(); // 删除用尾删}const T& top(){return _con.back(); // 后进先出}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}int main()
{sky::Stack<int,vector<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout << st.size() << endl;while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;return 0;
}queue类
queue类的介绍
1、queue是标准库容器适配器，用于实现先进先出（FIFO）队列。它基于底层容器（如
deque或list）进行封装2、默认使用
deque作为存储容器，也可以指定其他符合双端操作要求的容器。
queue适用于需要按顺序处理数据的场景，如任务调度或广度优先搜索等
queue的基本操作
push()：向队尾添加元素。pop()：移除队头元素。front()：返回队头元素的引用。back()：返回队尾元素的引用。empty()：检查队列是否为空。size()：返回队列中元素的数量
queue的模拟实现
namespace sky
{template<class T, class Container = list<int>>class Queue{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}T& front(){return _con.front();}T& back(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}int main()
{sky::Queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << q.back() << endl;cout << q.size() << endl;while (!q.empty()){cout << q.front() << " ";q.pop();} return 0;
}优先级队列
优先级队列的介绍
priority_queue是标准库容器适配器，用于实现优先级队列，其元素根据优先级自动排序。默认情况下，它使用最大堆结构，使得队头元素总是优先级最高的元素
priority_queue适用于需要动态维护最大（或最小）元素的场景，如任务调度、路径规划等注：需要包头文件<queue>
仿函数
什么是仿函数
priority_queue的函数原型比queue和stack多了一个参数，用于指定比较函数，这个参数决定了元素在priority_queue中的排序方式。比较函数（仿函数）：
priority_queue需要一个比较函数（通常是仿函数）来定义元素之间的优先级顺序。默认情况下，它使用std::less<T>，这意味着它将按照从小到大的顺序排列，形成一个最大堆这是
priority_queue与queue和stack最显著的区别，因为priority_queue需要根据元素的优先级来组织数据，而queue和stack仅需要遵循基本的先进先出或后进先出原则
为什么要有仿函数
- 自定义比较逻辑：优先级队列默认情况下是一个最大堆，即最大的元素具有最高的优先级。但有时我们可能需要根据不同的标准来排序元素，比如最小堆或者基于对象的某个成员函数。通过使用仿函数，我们可以自定义比较逻辑，使得优先级队列能够按照我们期望的顺序排列元素。
- 状态保持：仿函数可以保持状态，这意味着它们可以在调用之间保留信息，这在某些复杂的比较逻辑中非常有用。
- 类型安全：使用仿函数可以保证类型安全，因为编译器会在编译时检查传递给仿函数的参数类型是否正确。
优先级队列的使用
成员函数
push()：插入元素，并自动调整位置。pop()：移除优先级最高的元素（队头）。top()：访问优先级最高的元素。empty()：检查队列是否为空。size()：返回元素的数量
排序准则
默认使用 std::less（大顶堆），可以通过自定义比较函数来实现小顶堆或其他排序
优先级队列的模拟实现
namespace sky
{template<class T>class less{public:bool operator()(const T& x, const T& y){// 在构建堆时，x < y 的意思是：如果 x 比 y 小，// 那么 x 的优先级低于 y，所以 y 应该排在 x 前面return x < y;}};template<class T>class greater{public:// 当使用 greater 作为比较器时，较小的元素会排在前面，因此可以创建一个"最小优先队列"bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = vector<int>, class Compare = less<T>>class priority_queue{public:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){// 如果父节点的值比子节点的值小，则交换（基于比较器的定义）if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){// 如果有右子节点且右子节点比左子节点大，则选择右子节点if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}// 如果父节点比选定的子节点小，则交换if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}// 插入元素并调整堆void push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1);}// 删除堆顶元素并调整堆void pop(){if (!_con.empty()){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}int main()
{sky::priority_queue<int> pq;pq.push(3);pq.push(1);pq.push(5);pq.push(4);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}
关于容器适配器
***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:“把自己活出一道光”。
我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！
好了划走吧。