stack和list

前言

stack和list的使用就不讲了，讲一下模拟实现，然后讲一下deque，最后讲一下优先队列

1. stack的模拟实现

	template<class T,class container>//这个container是vector，或者list或者deque（后面会说），这就叫做适配器，//用适配器来实现stack//就免去了很多我们要实现的东西class stack{public://stack();可以不用写void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top()const{return _con.back();}size_t size()const{return _con.size();}bool empty()const{return _con.enmpty();}private:container _con;};

template<class T,class container>
这个container是vector，或者list或者deque（后面会说），这就叫做适配器，
用适配器来实现stack
就免去了很多我们要实现的东西
因为vector，list这些适配器都有pop_back，这些函数，所以不管是哪个适配器都是可以实现这个栈的

		stack<int,vector<int>> s;s.push(1);s.push(2);s.push(3);s.push(4);s.push(5);s.push(6);while (!s.empty()){cout << s.top() << endl;s.pop();}cout << endl;

在这里插入图片描述

然后这样调用，这个模版参数，模版列表，就相当于函数那样，int传给T,vector传给container，然后就可以正常操作了，因为像函数那样，所以模版参数也可以设置缺省值

template<class T,class container=deque<T>>

这里既可以设置vector为缺省值，也可以设置list，但我们一般设置deque，队列也是这样的

stack<int> s;

2. queue的模拟实现

namespace bit
{template<class T, class container = deque<T>>class queue{public://stack();可以不用写//因为有默认构造void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& top(){return _con.front();}const T& top()const{return _con.front();}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:container _con;};void test2(){queue<int> s;s.push(1);s.push(2);s.push(3);s.push(4);s.push(5);s.push(6);while (!s.empty()){cout << s.top() << endl;s.pop();}cout << endl;}
}

在这里插入图片描述
这个就没什么好说的了，和stack差不多，唯一值得说的就是，那个模版参数的缺省值不能设置vetor，第一是因为vector没有头插这个函数，第二就是vector头插效率太低了

3. deque相关讲解

deque也叫做双端列表
在这里插入图片描述

双端列表的底层大致结构就是这样的，有一个指针数组，指针数组也不是从头开始的，而是从中间某个位置开始指向一些小数组，小数组的大小一般是固定的，比如都是10个
在这里插入图片描述
如果要尾插入数据，就会在末尾的小数组后面插入数据，小数组满了，就在这个末尾小数组后面在开辟，头插入数据，就在最前面的小数组前面插入数据，满了继续开辟就是了
deque还支持随机访问，也就是[]访问，因为每个小数组长度固定，就可以通过/10和%10来快速确定位置，所以访问也很快，但是访问没有vector快
但是呢，deque的中间插入就很坑了，要大量挪动后面的小数组
所以说deque这个东西呢，头插头删，尾插尾删很方便，其余的都一般，正是因为其余的一般般，所以无法替代vector和list，因为头插头删，尾插尾删很方便，所以适合作为栈和队列的适配器
下面讲一下大致怎么实现的
在这里插入图片描述
deque最主要的内容就是迭代器了，上图的starrt和finish就是迭代器，deque就是全程依靠迭代器实现的cur指向那个小数组里的某个数据当前位置，first指向小数组的头，last指向小数组的尾，node是个二级指针，指向指针数组里的指向小数组的值，就这样就可以很快实现deque了
所以说呢，deque就相当于是vector和list的结合体
还有就是，它的头文件就是deque

4. 优先级队列priority_queue

这个的头文件就是queue，这个东西就类似堆，或者说就是堆，底层是一个数组，使用和堆一摸一样的，因为底层是一个数组，所以我们可以用vector作为适配器
讲priority_queue的实现前，我们先讲一下使用
在这里插入图片描述
priority_queue首先它没有initializer_list的构造，所以不能这样，但它支持迭代器的赋值

	int arr[] = { 1,2,34,5,7,8,9,07,6,5,5,4,3,3 };priority_queue<int> a(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!a.empty()){cout << a.top() << " ";a.pop();}

在这里插入图片描述
首先要说的就是，对于正常的数组，它的指针就是就是它的迭代器
然后因为是堆嘛，每次出数据，调整数据，那肯定是有序的，看的出来，我们这个实现的是大堆

	int arr[] = { 1,2,34,5,7,8,9,07,6,5,5,4,3,3 };priority_queue<int,vector<int>,greater<int>> a(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!a.empty()){cout << a.top() << " ";a.pop();}

如果要实现成小堆的话，就要加上greater了，其实如果是排序的话，也是一样的，我们调用的排序，默认是升序的，但是如果加上greater，那么就是降序的了，因为编译器默认的模版参数是less，less是升序的，因为greater在priority_queue中是第三个参数，所以要传greater就要先传vector，vector是第二个模版参数，而且还是默认值
下面我们开始priority_queue的模拟实现
先实现一个大堆，先不管greater怎么搞的
在此之前，先提醒一点模版中的语法错误是不会直接用红线报出来的，比如你用的中文符号就不会直接报错来

	template<class T,class container=vector<T>>class priority_queue{public:priority_queue() = default;//我们先写个迭代器区间构造template<class my_iterator>priority_queue(my_iterator first, my_iterator end){while (first != end){_con.push_back(*first);first++;}//在把这个写成堆int child = (_con[(_con.size() - 1 - 1) / 2]);//从这个位置开始向下调整while (child >= 0){Adjust_down(child);child--;}}void Adjust_down(int parent){int child = 2 * parent + 1;while (child < _con.size()){if ((child + 1) < _con.size() && _con[child + 1] > _con[child]){child++;}if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = 2 * child + 1;}else{break;}}}void Adjust_up(int child){int parent = (child - 1) / 2;while (child > 0)//child等于0，就说明已经比较完了{if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T&x){//先插入vector，然后在向上调整_con.push_back(x);Adjust_up((int)_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();Adjust_down(0);}T& top(){return _con[0];}const T& top()const{return _con[0];}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:container _con;};

		int arr[] = { 1,2,34,5,7,8,9,7,6,5,5,4,3,3 };priority_queue<int> a(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!a.empty()){cout << a.top() << " ";a.pop();}

在这里插入图片描述
我们这个建立的是大堆，如何建立小堆呢，其实只需要将大堆的函数的>改成<,<改成>就可以了
但是这样还要写一个模版吗，其实还有一个更简单的方法，就是仿函数的方法

	template<class T>class myless{bool operator()(T& t1, T& t2){return t1 < t2;}};

如上图，这就是个仿函数，所谓仿函数就是对()的重载，使类产生的对象可以像函数那样去使用

		myless<int> m;cout << m(1, 2) << endl;

在这里插入图片描述
以前的重载，比如operator<;就是这样使用的m<T,小于始终只有一个操作数，但是（）的重载，操作数就可以有很多个，而且返回值不唯一，也可以有很多

	template<class T>class myless{public:bool operator()(const T& t1,const T& t2){return t1 < t2;}};template<class T>class mygreater{public:bool operator()(const T& t1, const T& t2){return t1 > t2;}};

所以两个仿函数就这样定义

void Adjust_down(int parent){int child = 2 * parent + 1;while (child < _con.size()){if ((child + 1) < _con.size() && _con[child + 1] > _con[child]){child++;}compare a;if (a(_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent = child;child = 2 * child + 1;}else{break;}}}void Adjust_up(int child){int parent = (child - 1) / 2;while (child > 0)//child等于0，就说明已经比较完了{compare a;if (a(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

对应函数就这样写，这样的话，就实现了大于小于的切换了，只需要传入less和greater就可以了，这里我们防止与库里的less冲突，所以才这样命名

		int arr[] = { 1,2,34,5,7,8,9,7,6,5,5,4,3,3 };priority_queue<int,vector<int>,mygreater<int>> a(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!a.empty()){cout << a.top() << " ";a.pop();}

在这里插入图片描述
以后还会经常用到仿函数的

5. 练习题

5.1 最小栈

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class MinStack {
public:MinStack() {//不用写}void push(int val) {stack1.push(val);if (stack2.empty() || stack2.top() >= val)//为空，或者val就是最小数据{stack2.push(val);}}void pop() {int tmp = stack1.top();stack1.pop();if (tmp == stack2.top()){stack2.pop();}}int top() {return stack1.top();}int getMin() {return stack2.top();}
private:stack<int> stack1;stack<int> stack2;
};

5.2 栈的压入、弹出序列

在这里插入图片描述

在这里插入图片描述

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param pushV int整型vector* @param popV int整型vector* @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code here//stack<int> s1;//int i = 0;//int j = 0;//s1.push(pushV[i]);//i++;//while (i < pushV.size())//如果这样设计的话，那么最后一个元素入栈，后就直接跳出来了，还没有判断后面的是否对应//    while (i < pushV.size())//但取了等于就永远死循环了，太麻烦了//    {//        while(!s1.empty()&&popV[j] == s1.top())//因为为空无法访问//        {//            s1.pop();//            j++;//        }//        if(s1.empty()|| popV[j] != s1.top())//        {//            s1.push(pushV[i]);//            i++;//        }//    }//    if (!s1.empty())//    {//        return false;//    }//    else//    {//        return true;//    }//}stack<int> s1;int i = 0;int j = 0;while (i < pushV.size())//交换一下位置呢//先入栈在判断是否对应{if (s1.empty() || popV[j] != s1.top()){s1.push(pushV[i]);i++;}while (!s1.empty() && popV[j] == s1.top())//因为为空无法访问{s1.pop();j++;}}if (!s1.empty()){return false;}else{return true;}}
};

5.3 数组中的第K个最大元素

在这里插入图片描述

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

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

相关文章

测试用例之等价类划分、边界值法

测试用例之等价类划分、边界值法

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、测试用例/案例 1、定义&#xff1a;是在测试执行之前&#xff0c;由测试人员编写的指导测试过程的重要文档&#xff0c;主要包括&#xff1a;用例编号、测试目…
阅读更多...
Windows安装服务

Windows安装服务

&#xff08;1&#xff09;下载设置工具 https://nssm.cc/release/nssm-2.24.zip &#xff08;2&#xff09;根据自己系统选择工具32/64版本 &#xff08;3&#xff09;选择版本后进入文件夹&#xff0c;打开cmd命令窗口输入命令&#xff1a;nssm.exe install &#xff08;4&a…
阅读更多...
阿里云实时计算Flink在多行业的应用和实践

阿里云实时计算Flink在多行业的应用和实践

摘要&#xff1a;本文整理自 Flink Forward Asia 2023 中闭门会的分享。主要分享实时计算在各行业的应用实践&#xff0c;对回归实时计算的重点场景进行介绍以及企业如何使用实时计算技术&#xff0c;并且提供一些在技术架构上的参考建议。内容分为以下四个部分&#xff1a; 业…
阅读更多...
SQL Server 端口配置

SQL Server 端口配置

目录 默认端口 更改端口 示例&#xff1a;更改 TCP 端口 示例&#xff1a;验证端口设置 远程连接测试 示例&#xff1a;使用 telnet 测试连接 配置防火墙 示例&#xff1a;Windows 防火墙设置 远程连接测试 示例&#xff1a;使用 telnet 测试连接 默认端口 TCP/IP: …
阅读更多...
jmeter 重试机制

jmeter 重试机制

一、功能实现 我们在测试过程中&#xff0c;请求接口可能是因为请求超时&#xff0c;或者接口异常失败&#xff0c;导致整个测试链路验证失败&#xff0c;jmeter重试机制&#xff0c;这个时候就可以避免上述问题发生 二、配置 1、添加线程组 首先&#xff0c;确保你已经在测…
阅读更多...
ctfshow~菜狗杯 你会异或吗

ctfshow~菜狗杯 你会异或吗

下载文件附件得到一张png图片&#xff0c;用010打开看一下 全是乱码&#xff0c;结合题目提示 你会异或吗 和 神秘数字:0x50 我们试一下图片十六进制值异或十六进制0x50 打开010然后工具–>十六进制运算–>二进制异或 输入0x50 得到一张新的图片 然后到微信里的图片文字提…
阅读更多...
函数模板和类模板

函数模板和类模板

前言&#xff1a;各位老铁好&#xff0c;今天来分享函数模板和类模板的知识&#xff0c;这个算是一个小知识&#xff0c;但这个小知识非常重要&#xff0c;相信学C的各位老铁一定听过STL这个名词&#xff0c;那么STL是什么呢&#xff1f;它与我们今天分享的这个函数模板和类模板…
阅读更多...
《Milvus Cloud向量数据库指南》——图像数据：ResNet50与图像及视频搜索的深度解析

《Milvus Cloud向量数据库指南》——图像数据：ResNet50与图像及视频搜索的深度解析

图像数据：ResNet50与图像及视频搜索的深度解析 在当今信息爆炸的时代，图像和视频作为最直观、最富表现力的媒体形式之一，其搜索与检索技术显得尤为重要。无论是科研探索、艺术创作还是日常娱乐，人们越来越依赖于高效的图像和视频搜索工具来快速定位所需内容。其中，ResNet…
阅读更多...
高频JMeter软件测试面试题

高频JMeter软件测试面试题

近期&#xff0c;有很多粉丝在催更关于Jmeter的面试题&#xff0c;索性抽空整理了一波&#xff0c;以下是一些高频JMeter面试题&#xff0c;拿走不谢~ 一、JMeter的工作原理 JMeter就像一群将请求发送到目标服务器的用户一样&#xff0c;它收集来自目标服务器的响应以及其他统计…
阅读更多...
光伏气象站：绿色能源时代的守护者

光伏气象站：绿色能源时代的守护者

光伏气象站&#xff0c;顾名思义&#xff0c;是结合了光伏发电技术与气象监测功能的创新设备。 它不仅能够利用太阳能自发电&#xff0c;实现绿色能源自给自足&#xff0c;还能精准监测并记录温度、湿度、风速、风向等关键气象参数。这些数据对于评估光伏系统的发电效率、优化电…
阅读更多...
Java后端初开--＞架构师学习路线！无偿分享！让你少走弯路

Java后端初开--＞架构师学习路线！无偿分享！让你少走弯路

由于平台篇幅原因&#xff0c;很多java面试资料内容展示不了&#xff0c;需要的java面试宝典的伙伴们转发文章关注后&#xff0c;扫描下方二维码免费获取:
阅读更多...
WebSocket 协议与 HTTP 协议、定时轮询技术、长轮询技术

WebSocket 协议与 HTTP 协议、定时轮询技术、长轮询技术

目录 1 为什么需要 WebSocket&#xff1f;2 WebSocket2.1 采用 TCP 全双工2.2 建立 WebSocket 连接2.3 WebSocket 帧 3 WebSocket 解决的问题3.1 HTTP 存在的问题3.2 Ajax 轮询存在的问题3.3 长轮询存在的问题3.4 WebSocket 的改进 参考资料&#xff1a; 为什么有 h…
阅读更多...
【调试笔记-20240731-Linux-Wordpress 添加 wp-weixin 插件支持微信用户扫码注册登录】

【调试笔记-20240731-Linux-Wordpress 添加 wp-weixin 插件支持微信用户扫码注册登录】

调试笔记-系列文章目录 调试笔记-20240731-Linux-Wordpress 添加 wp-weixin 插件支持微信用户扫码注册登录 文章目录 调试笔记-系列文章目录调试笔记-20240731-Linux-Wordpress 添加 wp-weixin 插件支持微信用户扫码注册登录 前言一、调试环境操作系统&#xff1a;Windows 10 …
阅读更多...
有趣的PHP小游戏——猜数字

有趣的PHP小游戏——猜数字

猜数字 这个游戏会随机生成一个1到100之间的数字&#xff0c;然后你需要猜测这个数字是什么。每次你输入一个数字后&#xff0c;程序会告诉你这个数字是“高了”还是“低了”&#xff0c;直到你猜对为止&#xff01; 使用指南&#xff1a; 代码如下&#xff0c;保存到一个p…
阅读更多...
排序算法：快速排序，golang实现

排序算法：快速排序，golang实现

目录 前言 快速排序 代码示例 1. 算法包 2. 快速排序代码 3. 模拟程序 4. 运行程序 5. 从大到小排序 快速排序的思想 快速排序的实现逻辑 1. 选择基准值 (Pivot) 2. 分区操作 (Partition) 3. 递归排序 循环次数测试 假如 10 条数据进行排序 假如 20 条数据进行…
阅读更多...
DC-7靶机通关

DC-7靶机通关

今天咱们来学习第七个靶机&#xff01;&#xff01;&#xff01; 1实验环境 攻击机&#xff1a;kali2023.2 靶机&#xff1a;DC-7 2.1主机发现 2.2端口扫描 依旧是开了两个端口&#xff0c;一个 22 一个 80 &#xff01;&#xff01;&#xff01; 3.1查看对方网页 在这里我…
阅读更多...
2024年必备技能：小红书笔记评论自动采集，零基础也能学会的方法

2024年必备技能：小红书笔记评论自动采集，零基础也能学会的方法

摘要&#xff1a; 面对信息爆炸的2024年&#xff0c;小红书作为热门社交平台&#xff0c;其笔记评论成为市场洞察的金矿。本文将手把手教你&#xff0c;即便编程零基础&#xff0c;也能轻松学会利用Python自动化采集小红书笔记评论&#xff0c;解锁营销新策略&#xff0c;提升…
阅读更多...
redis的集群（高可用）

redis的集群（高可用）

redis集群的三种模式&#xff1a; 主从复制 奇数 三台 一主两从 哨兵模式 3 一主两从 cluster集群 六台 主从复制&#xff1a;和mysql的主从复制类似&#xff0c;主可以写&#xff0c;写入主的数据通过RDB方式把数据同步到从服务器&#xff0c;从不能更新到主&#xff0c;也…
阅读更多...
【卫星载荷之QF项目-001】Vivado 2018.3安装

【卫星载荷之QF项目-001】Vivado 2018.3安装

1.简介 Vivado 是 FPGA 厂商赛灵思公司&#xff08;Xilinx&#xff09;于 2012 年起发布的集成设计环境。Vivado2018.3 是 2018 年 Xilinx 推出的 Vivado 最后一个版本&#xff0c;相对稳定。 2.软件下载 网上自己去官网即可获取安装资源包。 3.软件安装 解压缩安装包&…
阅读更多...
通配符/泛域名https证书申请流程

通配符/泛域名https证书申请流程

通配符证书也叫泛域名证书&#xff0c;是一种SSL/TLS证书&#xff0c;用于同时保护一个域名及其所有二级子域名的安全&#xff0c;如果企业拥有众多子域名&#xff0c;那么通配符证书是一个非常合适的选择。市面上通配符证书很多&#xff0c;但是收费不一&#xff0c;从哪里申请…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023