一、stack的介绍和使用

1.stack的介绍

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵循后进先出LIFO（Last In First Out）的原则。
Stack的文档介绍

2.stack的使用

stack相关OJ

（1）最小栈

本题可以使用两个栈，第一个栈存储元素，第二个栈存储最小元素，在每次入栈操作时检查入站元素是否小于第二个栈的栈顶元素，如果小于或等于，就将入栈元素同时压入第二个栈中，出栈时同样检查，当出栈元素等于第二个栈的栈顶元素时，即出站元素即为当前最小元素，两个栈同时出栈，否则只有第一个栈出栈。

classMinStack{public:MinStack(){}voidpush(intval){_elem.push(val);if(_min.empty()||val<=_min.top()){_min.push(val);}}voidpop(){if(_min.top()==_elem.top()){_min.pop();}_elem.pop();}inttop(){return_elem.top();}intgetMin(){return_min.top();}private:std::stack<int>_elem;std::stack<int>_min;};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */

（2）栈的压入、弹出序列

本题模拟入栈顺序，每次入栈检查，当入栈元素与出栈序列相等时出栈。最后所有元素入栈完毕后，若stack为空即为合法，返回true，否则返回false。

classSolution{public:/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */boolIsPopOrder(vector<int>&pushV,vector<int>&popV){// write code herestack<int>st;for(auto&e:pushV){st.push(e);while(!st.empty()&&st.top()==popV[0]){st.pop();popV.erase(popV.begin());}}returnst.empty();}};

二、queue的介绍和使用

1.queue的介绍

queue的文档介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文（先进先出）中操作，其中从容器一端插入元素，另一端提取元素
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：
   • empty：检测队列是否为空
   • size：返回队列中有效元素个数
   • front：返回队头元素的引用
   • back：返回队尾元素的引用
   • push_back：在队列尾部入队列
   • pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求，默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque

2.queue的使用

三、priority_queue的介绍和使用

1.priority_queue的介绍

priority_queue的文档介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中位于顶部的元素）。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素特定容器的“尾部”弹出，其称为优先队列的顶部
4. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：
   • empty：检测容器是否为空
   • size：返回容器中有效元素个数
   • front：返回容器中第一个元素的引用
   • push_back：在容器尾部插入元素
   • pop_back：删除容器尾部元素
5. 标准容器类vector和deque满足了这些要求，默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作

2.priority_queue的使用

【注意】

1. 默认情况下，priority_queue是大堆

#include<iostream>#include<vector>#include<queue>#include<functional>// greater算法的头文件usingnamespacestd;intmain(){// 默认情况下，创建的是大堆，其底层按照小于号比较vector<int>v{3,2,7,6,0,4,1,9,8,5};priority_queue<int>q1;for(auto&e:v){q1.push(e);}cout<<q1.top()<<endl;// 如果要创建小堆，将第三个参数换成greater比较方式priority_queue<int,vector<int>,greater<int>>q2(v.begin(),v.end());cout<<q2.top()<<endl;return0;}

2. 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供>或者<的重载

#include<queue>#include<iostream>usingnamespacestd;classDate{public:Date(intyear=1900,intmonth=1,intday=1):_year(year),_month(month),_day(day){}booloperator==(constDate&d)const{return(_year==d._year)&&(_month==d._month)&&(_day==d._day);}booloperator<(constDate&d)const{return(_year<d._year)||(_year==d._year&&_month<d._month)||(_year==d._year&&_month==d._month&&_day<d._day);}booloperator>(constDate&d)const{return(_year>d._year)||(_year==d._year&&_month>d._month)||(_year==d._year&&_month==d._month&&_day>d._day);}friendostream&operator<<(ostream&_cout,constDate&d);private:int_year;int_month;int_day;};ostream&operator<<(ostream&_cout,constDate&d){_cout<<d._year<<"-"<<d._month<<"-"<<d._day;return_cout;}intmain(){// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date>q1;q1.push(Date(2026,1,29));q1.push(Date(2026,1,28));q1.push(Date(2026,1,30));cout<<q1.top()<<endl;// 如果要创建小堆，需要用户提供>的重载priority_queue<Date,vector<Date>,greater<Date>>q2;q2.push(Date(2026,1,29));q2.push(Date(2026,1,28));q2.push(Date(2026,1,30));cout<<q2.top()<<endl;return0;}

3.priority_queue在OJ中的使用

数组中的第K个最大元素

将vector中的数据全部拷贝到priority_queue中，将前k-1和数据删除，剩余元素中堆顶元素即为第k大的元素

classSolution{public:intfindKthLargest(vector<int>&nums,intk){priority_queue<int>pq(nums.begin(),nums.end());for(inti=0;i<k-1;i++){{pq.pop();}}returnpq.top();}};

四、容器适配器

1.什么是适配器

适配器是一种设计模式（设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结），该种模式是将一个类的接口转换成客户希望的另一种接口。

2.STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但STL没有将其划分在容器中，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。

3.deque的简单介绍

• deque（双端队列）：是一种双向开口的“连续”空间的数据结构。
• 双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)；与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高
  deque
• deque不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组

deque的缺陷

• 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率很高，而且在扩容时也不需要搬移大量元素，因此其效率是比vector高的
• 与list比较，其底层是连续空间，空间利用率高，不需要存储额外字段
• 但是，deque有一个致命缺陷：不适合遍历。因为在遍历时，deque的迭代器要频繁检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能要经常遍历，因此在实际中，需要线性结构时大多情况下会优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

选择deque作为stack和queue的底层默认容器的原因

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要有push_back()和pop_front()操作的线性结构都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历（因此stack和queue没有迭代器），只需要在固定的一段或者两段进行操作
2. 在stack中元素增长时，deque比vector的效率高（扩容时不需要搬移大量数据）；queue中的元素增长时，deque不仅效率高，而且内存使用率高
   结合了deque的优点，完美避开了其缺陷

4.stack、queue、priority_queue模拟实现

（1）stack

#pragmaonce#include<deque>// 类模板实例化时按需实例化，使用哪些成员函数就实例化哪些成员函数namespacezsy{// 容器适配器// Container适配转换出stacktemplate<classT,classContainer=vector<T>>classstack{public:// 构造函数不需要写，_con是自定义类型，会调用自己的默认构造voidpush(constT&x){// 将尾当做栈顶，尾插即为入栈_con.push_back(x);}voidpop(){_con.pop_back();}constT&top()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}

（2）queue

#pragmaonce#include<deque>namespacezsy{// 容器适配器// Container适配转换出queuetemplate<classT,classContainer=list<T>>classqueue{public:// 构造函数不需要写，_con是自定义类型，会调用自己的默认构造voidpush(constT&x){// 尾插即为入队_con.push_back(x);}voidpop(){_con.pop_front();}constT&front()const{return_con.front();}constT&back()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}

（3）priority_queue

#pragmaonce#include<vector>// 仿函数：本质是一个类，内部重载了operator()，它的对象可以像函数一样使用template<classT>classLess{public:booloperator()(constT&x,constT&y){returnx<y;}};template<classT>classGreater{public:booloperator()(constT&x,constT&y){returnx>y;}};namespacezsy{// 默认是大堆，Compare传Lesstemplate<classT,classContainer=vector<T>,classCompare=Less<T>>classpriority_queue{public:voidAdjustUp(intchild){Compare com;intparent=(child-1)/2;while(child>0){if(com(_con[parent],_con[child])){swap(_con[child],_con[parent]);child=parent;parent=(child-1)/2;}else{break;}}}// 认为插入数据之前，_con中已有数据已经是堆voidpush(constT&x){_con.push_back(x);AdjustUp(_con.size()-1);}voidAdjustDown(intparent){Compare com;// 假设法：假设左孩子小size_t child=parent*2+1;// 当child>=_con.size()时说明已经调整到位while(child<_con.size()){// 找出实际上更小的孩子if(child+1<_con.size()&&com(_con[child],_con[child+1])){++child;}if(com(_con[parent],_con[child])){swap(_con[child],_con[parent]);parent=child;child=parent*2+1;}else{break;}}}voidpop(){// 交换首尾数据swap(_con[0],_con[_con.size()-1]);// 此时最大的数据在最后一个元素位置，删除最后一个数据_con.pop_back();AdjustDown(0);}constT&top(){return_con[0];}size_tsize(){return_con.size();}boolempty(){return_con.empty();}private:Container _con;};}