✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客
文章目录
前言一.容器stack1.介绍2.成员函数3.模拟实现4.注意事项 二.容器queue1.介绍2.成员函数3.模拟实现4.注意事项 三.容器priority_queue1.介绍2.使用3.模拟实现基本框架成员函数 4.测试
前言
在编程的世界里，数据结构是构建高效程序的基石。而在C++等编程语言中，容器则是对数据结构的一种方便的实现与封装。其中，stack（栈）、queue（队列）和priority_queue（优先队列）是非常重要且基本的容器类型。Stack以其独特的后进先出（LIFO）的操作模式，为解决一些特定顺序相关的问题提供了简洁的方法，例如函数调用栈。Queue遵循先进先出（FIFO）的原则，如同现实生活中的排队场景，在任务调度等场景有着广泛的应用。而priority_queue则允许按照用户定义的优先级来取出元素，给具有不同重要性元素的操作提供了高效的实现。本博客旨在深入探讨这三种容器，包括它们的特性、操作方式以及各自适用的应用场景等，希望能够帮助读者更好地理解和运用这些在编程中至关重要的工具。
一.容器stack
1.介绍
在之前的数据结构学习中我们知道Stack（栈）是一种特殊的线性数据结构，其特点在于元素的插入和删除操作都只能在容器的一端进行，这一端通常被称为栈顶。Stack遵循后进先出LIFO, Last In First Out的原则，即最后插入的元素会是第一个被删除的元素。
在C++中，Stack是作为容器适配器实现的，这意味着它封装了某个具体的容器类（如vector、deque或list）作为其底层存储结构，并提供了一套特定的成员函数来访问这些元素。如果没有为Stack指定特定的底层容器，默认情况下，Stack会使用deque作为其底层容器，因为deque提供了在两端高效插入和删除元素的能力，非常适合Stack的需求。
2.成员函数
Stack提供的主要成员函数包括：
push(x)函数
将元素x压入栈顶。pop()：
弹出栈顶元素，即删除栈顶元素。注意：这个函数没有返回值，只是简单地移除了栈顶元素。top()：
返回栈顶元素的引用，但不删除它。这允许我们访问栈顶元素的值，注意：如果不小心修改了引用的值，将会改变栈顶元素的值。empty()：
检查栈是否为空。如果栈为空，则返回true；否则返回false。size()：
返回栈中元素的个数。3.模拟实现
以下是一个容器Stack的简单模拟实现：
代码实现：#include<iostream>#include<vector>#include<list>using namespace std;namespace Mystack{ template<class T,class container=vector<T>> class stack{ public: //构造函数 stack() {} void push(const T& x){ //入栈调用尾插函数 _con.push_back(x); } void pop(){ //出栈调用尾删函数 _con.pop_back(); } T& top(){ //取栈顶元素返回最后一个元素即可 return _con[_con.size()-1]; } const T& top()const { return _con[_con.size()-1]; } size_t size()const { //获取大小调用size()函数 return _con.size(); } bool empty()const { //判断为空调用empty()函数 return _con.empty(); } private: container _con; };}实现原理：
模版参数T表示存储的数据类型，container表示适配器的类型，默认为vector<T>成员变量_con是适配器的实例化对象构造函数为空即可，成员变量会调用对应容器的构造函数完成初始化top()函数分为普通对象使用的类型和const对象使用的类型，返回是引用返回 测试用例：
void test1(){ Mystack::stack<string> st; st.push("ab"); st.push("cd"); st.push("ef"); st.push("gh"); while(!st.empty()){ cout<<st.top()<<" "; st.pop(); } cout<<endl;}
4.注意事项
Stack不支持随机访问，即不能通过下标访问元素。Stack内的元素是无法直接遍历的，但可以通过while循环和pop()/top()的组合来遍历（但这种方法会改变Stack的状态，因为每读取一个元素就需要弹出这个元素）。在使用pop()函数之前，需要确保栈不为空，否则会导致未定义行为。二.容器queue
1.介绍
Queue（队列）是一种先进先出FIFO, First In First Out的数据结构，它有两个主要操作：入队（enqueue）和出队（dequeue）。入队操作将元素添加到队列的尾部，而出队操作则移除队列头部的元素。Queue在多种场景中都有广泛的应用，如任务调度、消息传递、广度优先搜索等。
在C++中，Queue是作为容器适配器（Container Adapter）实现的，它依赖于某个具体的容器类（如deque、list）作为其底层存储结构。默认情况下，C++标准库中的Queue使用deque作为其底层容器，但也可以通过模板参数指定其他支持双端操作的容器，如list。
2.成员函数
Queue提供的主要成员函数包括：
push(x)：
将元素x添加到队列的尾部。pop()：
移除队列头部的元素。注意，这个函数没有返回值，只是简单地移除了队列头部的元素。front()：
返回队列头部元素的引用，但不删除它。这允许我们访问队列头部元素的值。back()：
返回队列尾部元素的引用，但不删除它。这允许我们访问队列尾部元素的值。empty()：
检查队列是否为空。如果队列为空，则返回true；否则返回false。size()：
返回队列中元素的个数。3.模拟实现
以下是一个容器Queue的简单模拟实现(注意，c++标准库中使用的是deque做默认适配器，这里为了方便直接使用list做默认适配器：
#include<iostream>#include<vector>#include<list>using namespace std;namespace Myqueue{ template<class T,class container=list<T>> class queue{ public: //构造函数 queue() {} //入队调用尾插函数 void push(const T& x){ _con.push_back(x); } //出队调用头删函数 void pop(){ _con.pop_front(); } //取队头元素返回迭代器begin()位置的元素 T& front(){ return *(_con.begin()); } const T& front()const { return *(_con.begin()); } //取队尾元素返回迭代器end()位置的元素 T& back(){ return *(_con.end()--); } const T& back()const { return *(_con.end()--); } //获取队长调用size()函数 size_t size()const { return _con.size(); } //判断为空调用empty()函数 bool empty()const { return _con.empty(); } private: container _con; };}实现原理：
模版参数T表示存储的数据类型，container表示适配器的类型，默认为list<T>成员变量_con是适配器的实例化对象构造函数为空即可，成员变量会调用对应容器的构造函数完成初始化back()和front函数分为普通对象使用的类型和const对象使用的类型，返回是引用返回 测试用例：
void test2(){ Myqueue::queue<string> q; q.push("ab"); q.push("cd"); q.push("ef"); q.push("gh"); while(!q.empty()){ cout<<q.front()<<" "; q.pop(); } cout<<endl;}
4.注意事项
Queue不支持随机访问，即不能通过下标访问元素。在使用pop()函数之前，需要确保队列不为空，否则会导致未定义行为。同样地，在使用front()或back()函数之前，也需要确保队列不为空。Queue的底层容器默认是deque，但也可以通过模板参数指定为其他支持双端操作的容器，如list。然而，由于vector只支持在尾部进行高效的插入和删除操作，因此它不能作为Queue的底层容器。 通过本文的介绍，相信你已经对C++中的Queue容器有了基本的了解，并掌握了其使用方法。希望这些信息能对你有所帮助！
三.容器priority_queue
容器priority_queue（优先级队列）是C++标准库中的一个容器适配器，它根据严格的弱排序标准为元素提供排序，使得队列的第一个元素总是当前元素中优先级最高的（默认是大堆，即最大元素位于堆顶）。
1.介绍
基本概念：
优先队列类似于堆，可以随时插入元素，并且只能检索最大堆元素（即队首元素）。优先队列被实现为容器适配器，将特定的容器类封装作为其底层容器。底层容器：
底层容器可以是任何标准容器类模板，如vector和deque，这些容器应该可以通过随机访问迭代器访问。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector作为底层容器。 比较函数：
优先队列使用比较函数来确定元素的优先级。默认情况下，使用std::less作为比较函数，创建最大堆。若要使用最小堆，可以指定std::greater作为比较函数。 2.使用
包含头文件：
在使用priority_queue之前，需要包含<queue>头文件。
定义优先队列：
priority_queue<int> pq; // 默认最大堆priority_queue<int, vector<int>, greater<int>> pq_min; // 最小堆成员函数：
push(x)：在优先队列中插入元素x。pop()：删除优先队列中最大（或最小）元素。top()：返回优先队列中最大（或最小）元素。empty()：检测优先队列是否为空。size()：返回优先队列中有效元素的个数。 3.模拟实现
基本框架
代码实现：
#include<iostream>#include<vector>#include<algorithm>using namespace std;namespace Mypriority_queue{ //仿函数/函数对象 //这个类可以像函数一样使用 //用来控制建大堆 template<class T> class less{ public: bool operator()(const T& x,const T& y){ return x<y; } }; //用来控制建小堆 template<class T> class greater{ public: bool operator()(const T& x,const T& y){ return x>y; } }; //类模版 template<class T,class container=vector<T>,class comapre=less<T>> class priority_queue{ private: //向上调整建堆 //向下调整建堆 public: //....其他成员函数 private: //成员变量 container _con; };}实现原理：
定义两个类，这两个可以像函数一样使用，也叫做仿函数，用来控制建大堆还是建小堆priority_queue类中，模版参数T表示存储的数据类型，模版参数container表示适配器，默认适配器为vector<int>，模版参数comapre表示用来控制建堆 成员函数
向下调整建堆代码实现：
void AdjustDown(size_t parents){ comapre com; //向下调整，由父节点找子节点，父节点乘2再加1 size_t child=parents*2+1; if(child+1<_con.size()&&com(_con[child],_con[child+1])){ child++; } while(child<_con.size()){ if(com(_con[parents],_con[child])){ swap(_con[parents],_con[child]); parents=child; child=parents*2+1; } else{ break; } }}实现原理：
由传过来的父节点找子节点，子节点是父节点的下标乘以2再加1创建com对象，这个对象可以像使用函数一样用来比较大小向下调整建堆代码实现：
void AdjustUp(size_t child){ comapre com; //向上调整，由子节点找父节点，子节点先-1再除2 size_t parents=(child-1)/2; while(child>0){ if(com(_con[parents],_con[child])){ swap(_con[parents],_con[child]); child=parents; parents=(child-1)/2; } else{ break; } }}实现原理：
由传过来的子节点找父节点，父节点下标是子节点下标先减1再除以2创建com对象，这个对象可以像使用函数一样用来比较大小构造函数代码实现：
template<class InputIterator>priority_queue(InputIterator first,InputIterator last){ while(first!=last){ _con.push_back(*first); first++; } //向下调整建堆 //注意，for循环中，i最好不要用size_t,如果出现i小于0时，会死循环 for(int i=(_con.size()-1-1)/2;i>=0;i--){ AdjustDown(i); }}实现原理：
构造函数是模版函数，将区间中的数据依次插入到优先队列中插入完数据后循环调用向下调整建堆其他成员函数代码实现：
void pop(){ swap(_con[0],_con[_con.size()k-1]); _con.pop_back(); AdjustDown(0);}void push(const T& x){ _con.push_back(x); AdjustUp(_con.size()-1);}T& top(){ return _con[0];}const T& top()const { return _con[0];}size_t size()const { return _con.size();}bool empty()const { return _con.empty();}实现原理：
pop()函数先交换第一个和最后一个元素，在删除最后一个元素相当于删除堆顶的元素，再调用向下调整push()函数将需要插入的数据插入到最后位置，再调用向上调整top()函数相当于获取堆顶也就是第一个元素获取大小调用对应的size()函数判断为空调用对应的empty()函数 4.测试
测试代码：
void test1(){ vector<int> v={3,2,6,1,8,7,0}; Mypriority_queue::priority_queue<int> q(v.begin(),v.end()); q.push(4); q.push(5); while(!q.empty()){ cout<<q.top()<<" "; q.pop(); } cout<<endl;}int main(){ test1(); return 0;}测试结果：
以上就是关于容器stack,queue,priority_queue的基本使用和模拟实现的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
