【C++】Queue与Priority Queue

目录1. 简介容器适配器2. 核心接口与基本使用2.1 Queue 的基本使用2.2 Priority Queue 的基本使用3. Priority Queue 的仿函数与自定义类型3.1 切换为小根堆3.2 自定义类型的比较4. 经典算法实战4.1 Queue 实战4.2 Priority Queue 实战5. 为什么 Queue 默认 Deque而 Priority Queue 默认 Vector附录适配器的模拟实现 (封装)Queue 的封装Priority Queue 的封装1. 简介容器适配器在 C STL 中Queue队列和 Priority Queue优先队列都被归类为容器适配器而非标准容器。所谓适配器模式就是将特定容器类封装作为其底层容器类并提供一组特定的成员函数来访问其元素。Queue队列专门用于 FIFO先进先出上下文元素的流动规则是“队尾入队头出”。Priority Queue优先队列底层类似堆Heap结构。它并不遵循先进先出而是根据严格的弱排序标准保证每次出队的元素都是当前队列中最大或最小的元素。2. 核心接口与基本使用2.1 Queue 的基本使用Queue 的底层容器应至少支持empty、size、front、back、push_back、pop_front。默认情况下使用deque。接口名称功能说明push(val)/pop()队尾入队 / 队头出队front()/back()返回队头元素的引用 / 返回队尾元素的引用empty()/size()检测队列是否为空 / 返回有效元素个数2.2 Priority Queue 的基本使用Priority Queue 的底层容器必须支持随机访问迭代器如empty、size、front、push_back、pop_back因为它需要借助堆算法make_heap,push_heap,pop_heap来维护结构。默认情况下使用vector作为底层容器且默认是大根堆Max-Heap。接口名称功能说明push(val)在优先队列中插入元素并自动调整堆结构pop()删除优先队列中最大或最小的堆顶元素top()返回堆顶元素最大或最小元素empty()/size()检测是否为空 / 返回元素个数#includeiostream#includequeueusingnamespacestd;voidtest_priority_queue(){// 默认是大堆输出9 8 7 6 ...priority_queueintmax_pq;max_pq.push(3);max_pq.push(9);max_pq.push(1);coutMax Heap Top: max_pq.top()endl;// 输出 9}3. Priority Queue 的仿函数与自定义类型在使用优先队列时我们常常需要改变默认的大根堆行为或者存储自定义的数据类型。3.1 切换为小根堆要创建小根堆需要引入functional头文件并将第三个模板参数替换为greaterT。#includequeue#includefunctional// greater 算法的头文件// 创建小根堆底层按照大于号比较std::priority_queueint,std::vectorint,std::greaterintmin_pq;3.2 自定义类型的比较如果优先队列中存放自定义类型用户需要在自定义类型中提供或者的重载或者传入自定义的仿函数Functor。classDate{public:Date(intyear,intmonth,intday):_year(year),_month(month),_day(day){}// 大根堆需要重载 booloperator(constDated)const{if(_year!d._year)return_yeard._year;if(_month!d._month)return_monthd._month;return_dayd._day;}private:int_year,_month,_day;};voidtest_custom_type(){std::priority_queueDateq;q.push(Date(2023,10,1));q.push(Date(2023,11,11));// 这个会成为堆顶}4. 经典算法实战4.1 Queue 实战用队列实现栈思路使用两个队列q1,q2模拟栈。入栈直接进非空队列出栈时将非空队列前n-1个元素倒入空队列弹出最后剩下的那个元素即可。classMyStack{public:voidpush(intx){q1.empty()?q2.push(x):q1.push(x);}intpop(){std::queueintemptyQq1.empty()?q1:q2;std::queueintnonEmptyQq1.empty()?q2:q1;while(nonEmptyQ.size()1){emptyQ.push(nonEmptyQ.front());nonEmptyQ.pop();}inttopElementnonEmptyQ.front();nonEmptyQ.pop();returntopElement;}// top() 和 empty() 逻辑省略...private:std::queueintq1,q2;};4.2 Priority Queue 实战数组中的第K个最大元素思路将数组元素全部放入大根堆优先队列中然后执行k-1次pop()此时的堆顶元素就是第 K 大的元素。classSolution{public:intfindKthLargest(vectorintnums,intk){// 将数组中的元素先放入优先级队列中 (O(N) 建堆)std::priority_queueintp(nums.begin(),nums.end());// 将前 k-1 个最大的元素删除for(inti0;ik-1;i){p.pop();}returnp.top();}};5. 为什么 Queue 默认 Deque而 Priority Queue 默认 VectorQueue 为什么默认 Deque 而不支持 Vectorqueue强依赖头删pop_front和尾插push_back。deque在头部删除和尾部插入时效率极高时间复杂度为 O(1)。若用vector封装每次头删都需要挪动后续所有数据时间复杂度骤降为 O(N)。Priority Queue 为什么默认 Vector优先队列本质是一个堆完全二叉树的数组实现。堆的维护依赖大量的随机访问例如通过父节点索引i访问左右孩子2i1,2i2。vector提供了极致的随机访问性能和极高的空间缓存命中率因此是优先队列的最佳拍档。附录适配器的模拟实现 (封装)Queue 的封装#pragmaonce#includedequenamespacebit{templateclassT,classContainerstd::dequeTclassqueue{public:voidpush(constTx){_con.push_back(x);}voidpop(){_con.pop_front();}constTback(){return_con.back();}constTfront(){return_con.front();}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}private:Container _con;};}Priority Queue 的封装借用 STL 的堆算法push_heap,pop_heap即可极其优雅地实现优先队列适配器。#pragmaonce#includevector#includealgorithm// 包含堆算法#includefunctionalnamespacebit{templateclassT,classContainerstd::vectorT,classComparestd::lessTclasspriority_queue{public:priority_queue(){}templateclassInputIteratorpriority_queue(InputIterator first,InputIterator last):_con(first,last){// 建堆std::make_heap(_con.begin(),_con.end(),comp);}voidpush(constTx){_con.push_back(x);std::push_heap(_con.begin(),_con.end(),comp);// 向上调整}voidpop(){std::pop_heap(_con.begin(),_con.end(),comp);// 将堆顶移到末尾向下调整_con.pop_back();// 真正删除}constTtop()const{return_con.front();}boolempty()const{return_con.empty();}size_tsize()const{return_con.size();}private:Container _con;Compare comp;// 比较器对象};}