Cstack、queue、priority_queue高效复习笔记一、容器适配器概念必理解1.1 什么是容器适配器适配器是一种设计模式将一个类的接口转换成用户希望的另一个接口。stack、queue、priority_queue本身不是容器而是对已有容器的接口进行包装称为容器适配器。1.2 STL 中默认底层容器容器适配器默认底层容器为什么stackdeque只需push_backpop_backqueuedeque只需push_backpop_frontpriority_queuevector需要随机访问堆算法1.3 stack/queue 没有迭代器stack 和 queue不需要遍历只在固定端点操作因此不提供迭代器。二、stack栈—— 后进先出 LIFO2.1 核心接口接口说明empty()判空size()元素个数top()返回栈顶元素引用不弹出push(x)压栈pop()弹栈无返回值2.2 模拟实现templateclassT,classCondequeTclassstack{public:voidpush(constTx){_c.push_back(x);}voidpop(){_c.pop_back();}Ttop(){return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};本质stack 只包装了底层容器的push_back、pop_back、back禁止其他操作。三、queue队列—— 先进先出 FIFO3.1 核心接口接口说明empty()判空size()元素个数front()返回队头元素引用back()返回队尾元素引用push(x)队尾入队pop()队头出队无返回值3.2 模拟实现templateclassT,classCondequeTclassqueue{public:voidpush(constTx){_c.push_back(x);}voidpop(){_c.pop_front();}Tfront(){return_c.front();}Tback(){return_c.back();}size_tsize()const{return_c.size();}boolempty()const{return_c.empty();}private:Con _c;};3.3 为什么 queue 不用 vectorqueue 需要pop_front()vector 头删是 O(n) 需要搬移全部元素效率太低。list 和 deque 头删都是 O(1)。四、priority_queue优先级队列—— 堆4.1 本质priority_queue就是堆。默认使用vector作为底层容器在 vector 上调用堆算法make_heap、push_heap、pop_heap维护堆结构。4.2 核心接口接口说明empty()判空size()元素个数top()返回堆顶元素最大值/最小值不弹出push(x)插入元素执行向上调整pop()删除堆顶元素执行向下调整注意没有front()/back()只有top()4.3 默认大堆 vs 小堆// 默认大堆最大元素在堆顶priority_queueintq1;// 等价于 priority_queueint, vectorint, lessint// 小堆最小元素在堆顶priority_queueint,vectorint,greaterintq2;// 从数组直接初始化intarr[]{3,2,7,6,0,4,1,9,8,5};priority_queueintq3(arr,arrsizeof(arr)/sizeof(arr[0]));// 大堆4.4 自定义类型的堆classDate{int_year,_month,_day;public:// 大堆需要 operatorbooloperator(constDated)const{if(_year!d._year)return_yeard._year;if(_month!d._month)return_monthd._month;return_dayd._day;}// 小堆需要 operatorbooloperator(constDated)const{if(_year!d._year)return_yeard._year;if(_month!d._month)return_monthd._month;return_dayd._day;}};priority_queueDateq1;// 大堆priority_queueDate,vectorDate,greaterDateq2;// 小堆五、经典 OJ 题解重点掌握5.1 最小栈问题设计一个栈支持push、pop、top、getMinO(1) 获取最小值。核心思路两个栈。一个栈_elem存所有元素另一个栈_min存当前最小值序列。classMinStack{public:voidpush(intx){_elem.push(x);if(_min.empty()||x_min.top())// 注意 保证相等最小值也能压栈_min.push(x);}voidpop(){if(_min.top()_elem.top())_min.pop();// 最小元素被弹出同步删除_elem.pop();}inttop(){return_elem.top();}intgetMin(){return_min.top();}private:stackint_elem;stackint_min;};关键点push用而不是否则如果有多个相同最小值pop后会丢失。5.2 栈的压入弹出序列问题给定压栈序列pushV和弹出序列popV判断popV是否合法的出栈顺序。boolIsPopOrder(vectorintpushV,vectorintpopV){if(pushV.size()!popV.size())returnfalse;stackints;intinIdx0,outIdx0;while(outIdxpopV.size()){// 栈空或栈顶不等于当前出栈元素 → 继续压栈while(s.empty()||s.top()!popV[outIdx]){if(inIdxpushV.size())s.push(pushV[inIdx]);elsereturnfalse;// 全部压完还匹配不上}// 栈顶等于当前出栈元素 → 弹出s.pop();outIdx;}returntrue;}5.3 逆波兰表达式求值问题计算后缀表达式操作数在前操作符在后。intevalRPN(vectorstringtokens){stackints;for(autostr:tokens){if(str||str-||str*||str/){intrights.top();s.pop();// 注意先出的是右操作数intlefts.top();s.pop();// 后出的是左操作数switch(str[0]){case:s.push(leftright);break;case-:s.push(left-right);break;case*:s.push(left*right);break;case/:s.push(left/right);break;}}else{s.push(stoi(str));}}returns.top();}5.4 数组中第 K 个最大元素intfindKthLargest(vectorintnums,intk){priority_queueintp(nums.begin(),nums.end());// 大堆for(inti0;ik-1;i)p.pop();// 弹出前 k-1 个最大returnp.top();// 堆顶即第 k 大}也可用小堆优化空间维护大小为 k 的小堆堆顶就是第 k 大。六、deque双端队列—— 了解级别6.1 底层结构deque 是一段假象的连续空间实际由多段连续小空间拼接而成类似动态二维数组。迭代器负责屏蔽不连续性维护整体连续的假象。6.2 优劣对比优势劣势vs vector头插/头删 O(1)扩容不搬移大量元素遍历效率低需频繁检测边界迭代器复杂vs list空间利用率高无需存额外指针不如 list 灵活6.3 为什么 stack/queue 默认用 dequestack/queue不需要遍历无迭代器恰好规避 deque 的致命缺陷stack 扩容时 deque 比 vector 效率高不需搬移大量数据queue 中 deque 既能头删 O(1) 又内存利用率高一句话stack/queue 结合了 deque 的优点完美避开了其缺陷。七、复习自测问答Q1stack、queue、priority_queue 是容器吗答不是。它们是容器适配器对已有容器的接口进行包装不直接管理数据。Q2stack 默认底层容器是什么queue 呢答都默认使用deque。queue 不能用 vectorpop_front效率低。Q3priority_queue 默认底层容器是什么为什么答默认用vector。priority_queue 就是堆需要随机访问迭代器进行堆调整。Q4priority_queue 默认是大堆还是小堆答大堆最大元素在堆顶。第三个模板参数传入greaterT变为小堆。Q5stack/queue 有迭代器吗为什么答没有。它们不需要遍历只在固定端点操作。迭代器会破坏其语义约束如允许访问栈中间元素。Q6自定义类型放进 priority_queue需要提供什么答大堆需要operator小堆需要operator。或者通过仿函数/函数对象指定比较规则。Q7最小栈问题的关键注意点是什么答push时判断x _min.top()必须用不是。否则有多个相同最小值时弹出一个就会导致_min提前删除getMin出错。Q8为什么 deque 在实际中用得不多答deque 的遍历效率低迭代器要频繁检测是否到达小段空间边界。大多数线性结构场景 vector 和 list 已够用deque 只有作为 stack/queue 底层时才用到。Q9如何用两个栈实现队列答一个栈in用于入队一个栈out用于出队。出队时若out为空把in全部倒入out再popout的栈顶。每个元素最多转移一次均摊 O(1)。Q10如何用两个队列实现栈答两个队列交替使用。压栈时压入非空队列弹栈时把非空队列的元素留最后一个全部转移到空队列最后弹出留下的那个元素。Q11逆波兰表达式计算时操作数的顺序是怎样的答先弹出的是右操作数后弹出的是左操作数这对减法和除法至关重要。复习重点容器适配器概念含 deque 选型原因、三个适配器的接口差异top/front/back/pop 各自对应什么、最小栈 OJ、priority_queue 大堆/小堆模板参数。第四、五、六章是核心。