C++ queue

目录

一、介绍

二、queue使用

三、模拟实现

四、优先级队列

五、priority_queue使用

OJ题:215. 数组中的第K个最大元素

快速排序

优先级队列

TOPK

六、模拟实现priority_queue

1、仿函数

2、优先级队列类

3、测试函数


一、介绍

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

二、queue使用

#include <iostream>
#include <queue>int main() {std::queue<int> myQueue;// 检测队列是否为空if (myQueue.empty()) {std::cout << "队列为空" << std::endl;}else {std::cout << "队列不为空" << std::endl;}// 入队列myQueue.push(10);myQueue.push(20);myQueue.push(30);// 返回队列中有效元素的个数std::cout << "队列中的元素个数:" << myQueue.size() << std::endl;// 返回队头元素的引用std::cout << "队头元素:" << myQueue.front() << std::endl;// 返回队尾元素的引用std::cout << "队尾元素:" << myQueue.back() << std::endl;// 出队列myQueue.pop();// 返回队头元素的引用std::cout << "出队后的队头元素:" << myQueue.front() << std::endl;return 0;
}

三、模拟实现

namespace byte
{template<class T, class Container = list<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue(){queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;}
}

四、优先级队列

1、优先级队列是一种容器适配器,根据一些严格的弱排序标准,经过专门设计,其第一个元素始终是它所包含的最大元素。

2、此上下文类似于堆,其中元素可以随时插入,并且只能检索最大堆元素(优先级队列中顶部的元素)。

3、优先级队列作为容器适配器实现,容器适配器是使用特定容器类的封装对象作为其基础容器的类,提供一组特定的成员函数来访问其元素。元素从特定容器的“背面”弹出,这称为优先级队列的顶部。

4、基础容器可以是任何标准容器类模板,也可以是一些其他专门设计的容器类。容器应可通过随机访问迭代器访问,并支持以下操作:
  • empty():检测容器是否为空
  • size():返回容器中有效元素个数
  • front():返回容器中第一个元素的引用
  • push_back():在容器尾部插入元素
  • pop_back():删除容器尾部元素
5、标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。

6、需要支持随机访问迭代器,以便始终在内部保持堆结构。这是由容器适配器通过自动调用算法函数rmake_heap  push_heap   pop_heap来自动完成此操作。

五、priority_queue使用

  • priority_queue()/priority_queue(first, last) 构造一个空的优先级队列

  • empty( ) 检测优先级队列是否为空,是返回true,否则返回 false

  • top( ) 返回优先级队列中最大(最小元素),即堆顶元素

  • push(x) 在优先级队列中插入元素x
  • pop() 删除优先级队列中最大(最小)元素,即堆顶元素
#include <iostream>
#include <queue>
#include <vector>using namespace std;int main() {// 构造一个空的优先级队列priority_queue<int> pq;// 检测优先级队列是否为空if (pq.empty()) {cout << "优先级队列为空" << endl;} else {cout << "优先级队列不为空" << endl;}// 使用迭代器范围构造优先级队列vector<int> nums = {3, 1, 4, 1, 5, 9};priority_queue<int> pq2(nums.begin(), nums.end());// 输出堆顶元素cout << "堆顶元素为: " << pq2.top() << endl;// 在优先级队列中插入元素pq2.push(2);pq2.push(7);// 输出堆顶元素cout << "堆顶元素为: " << pq2.top() << endl;// 删除堆顶元素pq2.pop();// 输出堆顶元素cout << "堆顶元素为: " << pq2.top() << endl;return 0;
}


OJ题:215. 数组中的第K个最大元素

快速排序

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(),nums.end());return nums[nums.size()-k];}
};

这个解法使用了 C++ 的标准库函数 sort 对数组进行排序,然后返回倒数第 k 个元素。通过将数组排序,我们可以确保最大的元素位于数组的末尾,倒数第二大的元素位于倒数第二个位置,以此类推。因此,返回 nums[nums.size() - k] 即可得到第 k 大的元素。这种方法的时间复杂度为 O(nlogn),其中 n 是数组的长度。

优先级队列

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq(nums.begin(),nums.end());while(--k){pq.pop();}return pq.top();}
};

这个解法使用了优先队列(priority_queue),它是一个基于堆实现的数据结构,可以自动维护最大(或最小)元素位于队列的顶部。首先,将整个数组构建成一个优先队列 pq,其中元素按照从大到小的顺序排列。然后,通过多次调用 pq.pop() 将队列中的前 k-1 个元素弹出,最后返回队列顶部的元素,即第 k 大的元素。这种方法的时间复杂度为 O(nlogn),空间复杂度为 O(n),其中 n 是数组的长度。

TOPK

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);for(size_t i=k;i<nums.size();i++){if(nums[i]>pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}
};
这个解法也使用了优先队列,但是与解法二不同的是,这里构建的是一个最小堆。首先,将数组的前 k 个元素构建成一个最小堆 pq。然后,从第 k+1 个元素开始遍历数组,如果当前元素大于最小堆的堆顶元素(即当前第 k 大的元素),则将堆顶元素弹出,将当前元素插入堆中。最后,返回最小堆的堆顶元素,即第 k 大的元素。这种方法的时间复杂度为 O(nlogk),空间复杂度为 O(k),其中 n 是数组的长度,k为最小堆的大小。

六、模拟实现priority_queue

1、仿函数

 在C++中,仿函数(Functor)是一种重载了函数调用操作符 operator() 的对象。它实际上是一个类或者结构体,通过重载 operator(),使得该对象可以像函数一样被调用。仿函数可以像函数一样接受参数,并返回结果,同时可以包含状态信息,因此它们在C++中被广泛用于实现函数对象,作为算法的参数传递,或者用于定义自定义的操作。

#pragma once
#include <vector>
using namespace std;namespace hhh
{template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};

使用仿函数的好处是可以将特定的操作封装为一个对象,使得代码更加灵活和可扩展。通过重载函数调用操作符,可以将对象当作函数来使用,这样可以方便地在算法或数据结构中使用。在这个实现中,less 和 greater 结构体被用作仿函数,用于定义元素的比较方式。less 结构体表示小的元素优先级高,greater 结构体表示大的元素优先级高。

2、优先级队列类

	template<class T, class Container = vector<T>,class Compare=less<T>>class priority_queue {private:Container _con;public:void adjust_up(int child){Compare com;int parent = (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;}}}void adjust_down(int parent){size_t child = parent * 2 + 1;while (child < _con.size()) {Compare com;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;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}};
}
  1. priority_queue 类:这是一个模板类,可以用于任何类型的元素。它有三个模板参数,T 是元素的类型,Container 是用于存储元素的容器类型,默认是 vectorCompare 是元素的比较方式,默认是 less

  2. adjust_up 函数:这个函数用于调整堆的结构,使得父节点的值大于或小于所有子节点的值。它的参数是一个子节点的索引,它会不断地将这个节点和它的父节点进行比较,如果父节点的值小于子节点的值,就交换这两个节点。

  3. adjust_down 函数:这个函数也是用于调整堆的结构,它的参数是一个父节点的索引,它会不断地将这个节点和它的子节点进行比较,如果父节点的值小于任何一个子节点的值,就交换这两个节点。

  4. push 函数:这个函数用于向优先级队列中添加一个元素。它首先将元素添加到向量的末尾,然后调用 adjust_up 函数来调整堆的结构。

  5. pop 函数:这个函数用于从优先级队列中删除最大或最小的元素。它首先交换向量的第一个元素和最后一个元素,然后删除最后一个元素,最后调用 adjust_down 函数来调整堆的结构。

  6. top 函数:这个函数用于获取优先级队列中最大或最小的元素。

  7. size 和 empty 函数:这两个函数用于获取优先级队列中元素的数量和判断优先级队列是否为空。

3、测试函数

void test_priority_queue()
{// 默认是大堆priority_queue<int> pq;// 小堆//priority_queue<int, vector<int>, greater<int>> pq;pq.push(1);pq.push(0);pq.push(5);pq.push(2);pq.push(1);pq.push(7);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;
}

大堆:


小堆:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/234741.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【手搓深度学习算法】用线性回归预测波士顿房价

线性回归 线性回归是一种监督学习方法&#xff0c;用于建立因变量与一个或多个自变量之间的关系。线性回归的目标是找到一条直线&#xff0c;使得所有数据点到这条直线的距离之和最小。 线性回归的基本形式如下&#xff1a; y β 0 β 1 x 1 β 2 x 2 . . . β n x n ϵ…

mysql基础-常用函数汇总

目录 1. 查询技巧 2. 时间函数 2.1 now() 2.2 current_date() 2.3 时间差timestampdiff&#xff08;&#xff09;与datediff&#xff08;&#xff09; 2.4 其他时间函数 3. 字符函数 3.1 截取函数 3.2 分割函数 3.3 left与right函数 3.4 其他函数 4. 数字函数 5. …

自定义HBase负载均衡器MyCustomBalancer实现步骤与代码解析

目录 1.HBase默认负载均衡策略 1.1 负载均衡总体流程 1.2 不能触发负载均衡的情况 1.3 负载均衡算法 2.自定义的 HBase 负载均衡器的步骤 3.MyCustomBalancer的代码细节 3.1 balanceCluster 方法的作用 3.2balanceCluster 对数据的影响 3.3监控HBase的性能指标 3.3.…

在国内 PMP 有多少含金量?

在我国大陆&#xff0c;有好多证书被商业化得太重了&#xff0c;甚至演变成了个人或一些公司摇钱的工具。所以有些证书受人吹捧它崛起的快&#xff0c;但是活不长&#xff0c;甚至“夭折”&#xff0c;比如以前微软系列的证书&#xff1b; 而PMP认证从国外引进大陆这么多年了&…

PMP认证考试详细备考攻略,全是干货!

要明白&#xff0c;虽然PMP备考考试只是一时的过程&#xff0c;但通过PMP获得的证书和能力是永久的。 这不仅仅是因为我拿到了PMP培训结业证书和PMP认证证书这两个证明&#xff0c;更重要的是在参加PMP认证考试的整个过程中&#xff0c;我学到了很多关于项目管理的知识&#x…

Python基础入门第九课笔记(文件和文件夹)

1&#xff0c;新建文本并且写内容 a open(1.text,w) a.write("""aaa bbb ccc""") a.close() 2,seek( )移动文件指针 文件对象.seek(偏移量&#xff0c;起始位置) # 起始位置&#xff1a;0开头&#xff0c;1当前位置&#xff0c;2文件结尾…

获取深层次字段报错TypeError: Cannot read properties of undefined (reading ‘title‘)

动态生成菜单时报错,不能多层获取路由meta下面的title字段 <template><p>{{ meneList }}</p><template v-for"item in meneList" :key"item.path"><el-menu-item v-if"!item.children"><template #title>{…

一键了解获取网页requests方式

目录 一、爬虫原理&#xff1a; 二、安装&#xff1a; 测试&#xff1a; 三、文件的操作 方式一 方式二: 方式三 四、认识User-Agent 4.1、为什么用User-Agent&#xff1a; 步骤&#xff1a; 五、请求方式 5.1、get 5.2、post 六、爬出有中国关键字页面案例 一、爬…

小型图书借阅管理系统

springbootmybatismysqlthymeleafjquery构建的小型图书借阅管理系统后端 1.springboot 2.mybatis数据库 1.mysql前端 1.jquery 2.jquery-validate 3.htmlcss

【性能测试入门】:压力测试概念!

压力测试可以验证软件应用程序的稳定性和可靠性。压力测试的目标是评估软件在极端负载条件下的鲁棒性和错误处理能力&#xff0c;并确保软件在紧急情况下不会崩溃。它甚至可以进行超出软件正常工作条件的测试&#xff0c;并评估软件在极端条件下的工作方式。 在软件工程中&…

Linux 上 Nginx 配置访问 web 服务器及配置 https 访问配置过程记录

目录 一、前言说明二、配置思路三、开始修改配置四、结尾 一、前言说明 最近自己搭建了个 Blog 网站&#xff0c;想把网站部署到服务器上面&#xff0c;本文记录一下搭建过程中 Nginx 配置请求转发的过程。 二、配置思路 web项目已经在服务器上面运行起来了&#xff0c;运行的端…

WPS使用技巧——默认粘贴无格式文本

从网页或者其他文档内复制的文本往往带有原本的格式&#xff0c;粘贴到自己的word文档里面&#xff0c;要么先粘贴后统一格式&#xff0c;要么右键选择“只粘贴文本”&#xff0c;非常不便。 今天分享一个可以将粘贴方式默认为“只粘贴文本”的无格式粘贴方法&#xff0c;这样…

pycharm的使用技巧

1.新建文件时,自动生成代码 settings->editor->file and code templates,选择python script ${NAME} 文件名 ${DATE} 日期 2.自动补齐自定义段落 settings->editor->live templates,在右侧点击+号,添加自定义的内容 完成之后,在下方勾选python 3.修改注释的…

(23)Linux的软硬连接

前言&#xff1a;上一章我们讲解了 inode&#xff0c;为文件系统收了尾&#xff0c;这几章我们充分地讲解完了文件系统的知识点&#xff0c;现在我们开始开始学习软硬链接了。 软硬链接 1、Linux 下的快捷方式&#xff1a;软链接 上一章我们介绍完了 inode &#xff0c;我们…

【C语言】Linux实现高并发处理的过程

一、实现高并发的几种策略 C语言本身并没有内建的多线程支持&#xff08;新版C语言支持&#xff0c;但用得不多&#xff09;&#xff0c;但是在多数操作系统中&#xff0c;可以使用库来实现多线程编程。例如&#xff0c;在POSIX兼容系统上&#xff0c;可以使用 pthreads 库来创…

FindMy技术用于键盘

键盘是我们生活中不可或缺的输入工具&#xff0c;是人与计算机之间沟通的桥梁&#xff0c;无论是编写文档、浏览网页、玩游戏、或是进行复杂的数据分析&#xff0c;键盘都在其中发挥着关键的作用。此外&#xff0c;键盘还是各种软件的快捷键操作的关键。通过熟练地运用快捷键&a…

vue-vben-admin 与.net core 结合实例 【自学与教学 小白教程】---第3节

ue-vben-admin 与.net core 结合实例 这里计划使用.net core 作为后端 。目标&#xff1a;打造好看 易用 开箱即用 的netcore一体化框架。Vue Vben Admin For NetCore 取命 hcrain-vvadmin 我不是前端人员 但有时开发还是要写一些界面。 之前使用layui是时候 狠心升级下了。 …

Linux网络的命令和配置

目录 一、网络配置命令 1、配置和管理网络接口 1.1 ifconfig 1.2 ip 1.2.1 ip link 1.2.2 ip addr 1.3 修改网络接口名 1.3.1 临时修改网络接口名 1.3.2 永久修改网络接口名 1.4 永久配置单网卡 1.5 永久配置双网卡 1.6 ethtool 2、查看和设置主机中路由表信息…

“第四个中国人民警察节”细语

今&#xff08;2024年1月10日&#xff09;天&#xff0c;是第四个中国人民警察节&#xff0c;本“人民体验官”推广人民日报官方微博文化产品《一起致敬人民警察&#xff01;》。 图&#xff1a;来源“人民体验官”推广平台 笔者认同“平安的密码叫110”这个洽当比喻。因为人民…

开源了,免费使用GPT4(Windows/Linux/Mac 一键启动脚本)

开源了&#xff0c;免费使用GPT4&#xff08;Windows一键启动脚本&#xff09; 大家好&#xff0c;我打算每日花1小时来写一篇文章&#xff0c;这一小时包括文章主题思考和实现&#xff0c;连续日更几天&#xff0c;看看能不能被官方推荐。&#xff08;帮我点点赞哦&#xff5…