一、stack的介绍和使用1.stack的介绍栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵循后进先出LIFOLast In First Out的原则。Stack的文档介绍2.stack的使用函数声明接口说明stack()构造空的栈empty()检测stack是否为空是返回true否则返回falsesize()返回stack中有效元素的个数top()返回栈顶元素的引用push()将元素val压入栈中pop()将stack中尾部的元素弹出stack相关OJ1最小栈本题可以使用两个栈第一个栈存储元素第二个栈存储最小元素在每次入栈操作时检查入站元素是否小于第二个栈的栈顶元素如果小于或等于就将入栈元素同时压入第二个栈中出栈时同样检查当出栈元素等于第二个栈的栈顶元素时即出站元素即为当前最小元素两个栈同时出栈否则只有第一个栈出栈。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::stackint_elem;std::stackint_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(vectorintpushV,vectorintpopV){// write code herestackintst;for(autoe:pushV){st.push(e);while(!st.empty()st.top()popV[0]){st.pop();popV.erase(popV.begin());}}returnst.empty();}};二、queue的介绍和使用1.queue的介绍queue的文档介绍队列是一种容器适配器专门用于在FIFO上下文先进先出中操作其中从容器一端插入元素另一端提取元素队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从队尾入队列从队头出队列底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作empty检测队列是否为空size返回队列中有效元素个数front返回队头元素的引用back返回队尾元素的引用push_back在队列尾部入队列pop_front在队列头部出队列标准容器类deque和list满足了这些要求默认情况下如果没有为queue实例化指定容器类则使用标准容器deque2.queue的使用函数声明接口说明queue()构造空的队列empty()检测queue是否为空是返回true否则返回falsesize()返回queue中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将对头元素出队列三、priority_queue的介绍和使用1.priority_queue的介绍priority_queue的文档介绍优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素优先队列中位于顶部的元素。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素特定容器的“尾部”弹出其称为优先队列的顶部底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作empty检测容器是否为空size返回容器中有效元素个数front返回容器中第一个元素的引用push_back在容器尾部插入元素pop_back删除容器尾部元素标准容器类vector和deque满足了这些要求默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作2.priority_queue的使用函数声明接口说明priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty()检测优先级队列是否为空是返回true否则返回falsetop()返回优先级队列中最大最小元素即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大最小元素即堆顶元素【注意】默认情况下priority_queue是大堆#includeiostream#includevector#includequeue#includefunctional// greater算法的头文件usingnamespacestd;intmain(){// 默认情况下创建的是大堆其底层按照小于号比较vectorintv{3,2,7,6,0,4,1,9,8,5};priority_queueintq1;for(autoe:v){q1.push(e);}coutq1.top()endl;// 如果要创建小堆将第三个参数换成greater比较方式priority_queueint,vectorint,greaterintq2(v.begin(),v.end());coutq2.top()endl;return0;}如果在priority_queue中放自定义类型的数据用户需要在自定义类型中提供或者的重载#includequeue#includeiostreamusingnamespacestd;classDate{public:Date(intyear1900,intmonth1,intday1):_year(year),_month(month),_day(day){}booloperator(constDated)const{return(_yeard._year)(_monthd._month)(_dayd._day);}booloperator(constDated)const{return(_yeard._year)||(_yeard._year_monthd._month)||(_yeard._year_monthd._month_dayd._day);}booloperator(constDated)const{return(_yeard._year)||(_yeard._year_monthd._month)||(_yeard._year_monthd._month_dayd._day);}friendostreamoperator(ostream_cout,constDated);private:int_year;int_month;int_day;};ostreamoperator(ostream_cout,constDated){_coutd._year-d._month-d._day;return_cout;}intmain(){// 大堆需要用户在自定义类型中提供的重载priority_queueDateq1;q1.push(Date(2026,1,29));q1.push(Date(2026,1,28));q1.push(Date(2026,1,30));coutq1.top()endl;// 如果要创建小堆需要用户提供的重载priority_queueDate,vectorDate,greaterDateq2;q2.push(Date(2026,1,29));q2.push(Date(2026,1,28));q2.push(Date(2026,1,30));coutq2.top()endl;return0;}3.priority_queue在OJ中的使用数组中的第K个最大元素将vector中的数据全部拷贝到priority_queue中将前k-1和数据删除剩余元素中堆顶元素即为第k大的元素classSolution{public:intfindKthLargest(vectorintnums,intk){priority_queueintpq(nums.begin(),nums.end());for(inti0;ik-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比较空间利用率比较高dequedeque不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组deque的缺陷与vector比较deque的优势是头部插入和删除时不需要搬移元素效率很高而且在扩容时也不需要搬移大量元素因此其效率是比vector高的与list比较其底层是连续空间空间利用率高不需要存储额外字段但是deque有一个致命缺陷不适合遍历。因为在遍历时deque的迭代器要频繁检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能要经常遍历因此在实际中需要线性结构时大多情况下会优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是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作为其底层容器主要是因为stack和queue不需要遍历因此stack和queue没有迭代器只需要在固定的一段或者两段进行操作在stack中元素增长时deque比vector的效率高扩容时不需要搬移大量数据queue中的元素增长时deque不仅效率高而且内存使用率高结合了deque的优点完美避开了其缺陷4.stack、queue、priority_queue模拟实现1stack#pragmaonce#includedeque// 类模板实例化时按需实例化使用哪些成员函数就实例化哪些成员函数namespacezsy{// 容器适配器// Container适配转换出stacktemplateclassT,classContainervectorTclassstack{public:// 构造函数不需要写_con是自定义类型会调用自己的默认构造voidpush(constTx){// 将尾当做栈顶尾插即为入栈_con.push_back(x);}voidpop(){_con.pop_back();}constTtop()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}2queue#pragmaonce#includedequenamespacezsy{// 容器适配器// Container适配转换出queuetemplateclassT,classContainerlistTclassqueue{public:// 构造函数不需要写_con是自定义类型会调用自己的默认构造voidpush(constTx){// 尾插即为入队_con.push_back(x);}voidpop(){_con.pop_front();}constTfront()const{return_con.front();}constTback()const{return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};}3priority_queue#pragmaonce#includevector// 仿函数本质是一个类内部重载了operator()它的对象可以像函数一样使用templateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};namespacezsy{// 默认是大堆Compare传LesstemplateclassT,classContainervectorT,classCompareLessTclasspriority_queue{public:voidAdjustUp(intchild){Compare com;intparent(child-1)/2;while(child0){if(com(_con[parent],_con[child])){swap(_con[child],_con[parent]);childparent;parent(child-1)/2;}else{break;}}}// 认为插入数据之前_con中已有数据已经是堆voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}voidAdjustDown(intparent){Compare com;// 假设法假设左孩子小size_t childparent*21;// 当child_con.size()时说明已经调整到位while(child_con.size()){// 找出实际上更小的孩子if(child1_con.size()com(_con[child],_con[child1])){child;}if(com(_con[parent],_con[child])){swap(_con[child],_con[parent]);parentchild;childparent*21;}else{break;}}}voidpop(){// 交换首尾数据swap(_con[0],_con[_con.size()-1]);// 此时最大的数据在最后一个元素位置删除最后一个数据_con.pop_back();AdjustDown(0);}constTtop(){return_con[0];}size_tsize(){return_con.size();}boolempty(){return_con.empty();}private:Container _con;};}