C++栈、队列、优先级队列模拟+仿函数

 

目录

一、栈的模拟和deque容器

1.deque

1.1deque结构

1.2deque优缺点

2.stack模拟

二、队列的模拟

三、priority_queue优先级队列

1.优先级队列模拟

2.添加仿函数


一、栈的模拟和deque容器

在之前,我们学过了C语言版本的栈,可以看这篇文章 栈和队列。

但是C语言没有模板,我们只能固定一个类型去写,在C++中引入了模板的概念,我们只需要写一份,在调用中给到类型,编译器会自动去帮我们推导是栈里面元素的类型,会非常方便。

1.deque

我们可以看到,库函数里面的栈调用的是一个deque容器。

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。

1.1deque结构

首先deque有一个中控数组,这个数据是指针数组,存放的内容是指针,每个指针都指向的一块空间的起始地址。

他的迭代器有  cur(当前数据当前位置)  fisrt(数据起始位置)last(数据结尾位置) node(指向数据的指针)。

头插就去找到最前面的那个有效指针进行头插,尾插就找最后面那个有效指针尾插,遍历就通过迭代器每一个空间块从头遍历到位,就换下一个空间块。

 

1.2deque优缺点

deque实际上是一个缝合怪,他结合了vector和list的内容,将他们糅合在了一起。

优点

与vector比较,deque的优势是 :头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。

与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。

 但是他也有缺点

deque容器不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list。

那么为何他能在栈和队列中使用,并成为默认容器呢?

因为栈和队列需要尾插,尾删,队列需要尾插,头删deque容器完全可以适配这些需求,因为不需要遍历,并且deque扩容时不需要挪动数据,这也是的deque的效率变高。

2.stack模拟

stack的模拟非常简单,调用模板Container容器的函数就可以了,也不需要迭代器(不用遍历),也不需要构造函数析构函数什么的,因为Container容器是自定义类型,会自动调用的相关构造析构拷贝函数。

#pragma once
#include<deque>
namespace kky
{template<class T, class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

二、队列的模拟

队列模拟跟stack差不都,多了一个back接口,出数据的时候要调用pop_front()

#pragma once
#include<deque>
namespace kky
{template<class T, class Container = deque<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();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

三、priority_queue优先级队列

优先级队列出数据的时候,会先出优先级高的数据。

如何来判断优先级的高低呢?

这跟你传的数据类型有关,先举个例子

我们插入了   1,10,8,5,6   但出数据的时候缺省按照数据的大小顺序来出的,在这里使用数据的大小来看段他们优先级的高低。

优先级队列出数据时会帮我们做好排序,他的本质就是堆,通过堆的向上向下调整来处理优先级问题。具体堆排序的过程可以看选择排序中的堆排序。

1.优先级队列模拟

优先级队列的模拟实现就是要建堆,每一次插入数据都要进行向上调整,保证是大堆或者小堆。

出数据的时候将第一个数据和最后一个数据互换,再进行尾删,因为第一个数据是我们想要出的数据,将他和最后一个数据交换再尾删,就可以提取出这个数据了,同时现在只有第一个元素不符合小堆或者大堆的情况,其他元素都符合,因此进行一次从索引为0位置的向下调整即可。

namespace kky
{template<class T,class Container = vector<T>>class priority_queue{public:void adjust_up(size_t child){while(child>0){size_t parent = (child - 1) / 2;if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;}else{break;}}}void adjust_down(size_t parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child++;}if (_con[child] > _con[parent]){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);}T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

刚刚的代码构建了一个大堆,但是我们如果想要构建小堆,难不成又要重写一份代码吗?  那必定不是可能的。 

2.添加仿函数

在C语言中,我们可以通过函数指针来处理顺序的问题,但是函数指针类型很繁琐,并且不容易理解,C++推出了仿函数来帮助我们处理这类问题。

写一个类,仅仅重载了operator(),返回类型为bool,在后面进行判断的时候,我们就可以调用这个类对象的(),类似于函数一样,就可以处理了,

template<class T>
class Less
{
public:bool operator()(const T& x1, const T& x2){return x1 < x2;}
};

第一个方式太丑陋了,一般使用第二种方式去调用。

那之前,我们代码中的判断语句,都可以通过调用仿函数更改了 

给模板参数再添加一个类

template<class T, class Container = vector<T>,class Compare = Less<T>>

现在就可以开始更改了 

只需要注意顺序即可,需要这样判断的都可以更改,参考如下代码

namespace kky
{template<class T, class Container = vector<T>,class Compare = Less<T>>class priority_queue{public:void adjust_up(size_t child){Compare com;while (child > 0){size_t parent = (child - 1) / 2;if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;}else{break;}}}void adjust_down(size_t parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){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);}T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

 这是我们写的Less仿函数,如果你想让优先级队列建小堆,就可以写再写一个仿函数

template<class T>
class Greater
{
public:bool operator()(const T& x1, const T& x2){return x1 > x2;}
};

需要的时候调用一下即可 

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

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

相关文章

java智慧工地云平台源码,以物联网、移动互联网技术为基础,结合大数据、云计算等,实现工程管理绿色化、数字化、精细化、智能化的效果

智慧工地将更多人工智能、传感技术、虚拟现实等高科技技术植入到建筑、机械、人员穿戴设施、场地进出关口等各类物体中&#xff0c;围绕人、机、料、法、环等各方面关键因素&#xff0c;彻底改变传统建筑施工现场参建各方现场管理的交互方式、工作方式和管理模式&#xff0c;智…

香飘飘的想象空间:全面创新驱动外延与内涵双增长,未来可期

面对时常会发生代际更替的消费者主力群体&#xff0c;创新已经成为一种商业上的必须。 日前&#xff0c;香飘飘发布了三季报&#xff0c;数据显示&#xff0c;第三季度&#xff0c;香飘飘营业收入8.08亿元&#xff0c;同比增长20.41%。前三季度&#xff0c;香飘飘营收19.79亿元…

视频号视频提取小程序,快速下载视频号视频

​视频号提取小程序可以帮助用户方便地从视频号视频平台获取到自己喜欢的视频号内容。通过这个小程序&#xff0c;你可以快速搜索并提取出视频号&#xff0c;并进行相关的操作。 据悉视频下载bot小程序目前已经更名为【提取下载小助手】 使用视频号提取小程序有以下几个步骤&…

Kubernetes 通过 Deployment 部署Jupyterlab

概要 在Kubernetes上部署jupyterlab服务&#xff0c;链接Kubernetes集群内的MySQL&#xff0c;实现简单的数据开发功能。 前置条件 镜像准备&#xff1a;自定义Docker镜像--Jupyterlab-CSDN博客 MySQL-Statefulset准备&#xff1a;StatefulSet 简单实践 Kubernetes-CSDN博客…

学习vue3

一、入门 1.引入外部库 ①直接将所有的js都通过script标签引入到html文件中&#xff0c;所有的js资源在web页面中都能通用。 ②使用js引用js&#xff08;ES6&#xff09;&#xff0c;模块导入与导出 2.模块是只读引用 这段话是在解释 Vue.js 中的概念和用法。在 Vue.js 中&a…

从实时数据库转战时序数据库,他陪伴 TDengine 从 1.0 走到 3.0

关于采访嘉宾 在关胜亮的学生时代&#xff0c;“神童”这个称号如影随形&#xff0c;很多人初听时会觉得这个称谓略显夸张&#xff0c;有些人还会认为这是不是就是一种调侃&#xff0c;但是如果你听说过他的经历&#xff0c;就会理解这一称号的意义所在了。 受到教师母亲的影…

React之render

一、原理 首先&#xff0c;render函数在react中有两种形式&#xff1a; 在类组件中&#xff0c;指的是render方法&#xff1a; class Foo extends React.Component {render() {return <h1> Foo </h1>;} }在函数组件中&#xff0c;指的是函数组件本身&#xff1a…

【Linux进阶之路】进程(中)—— 进程地址空间

文章目录 一、 进程地址空间1.概念引入2.基本概念3.深入概念3.1 初识信息交互3.2 区域划分3.3 进程地址空间3.4 再识页表缺页中断进程挂起 总结 一、 进程地址空间 1.概念引入 指针指向的地址是内存中的地址吗&#xff1f;下面我们用一个实验来证明一下。 先来写程序看一下程…

C# Onnx Yolov8 Detect 戴安全帽检测

效果 项目 代码 using Microsoft.ML.OnnxRuntime; using Microsoft.ML.OnnxRuntime.Tensors; using OpenCvSharp; using System; using System.Collections.Generic; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;namespace Onnx…

pd19虚拟机软件 Parallels Desktop 19 mac中文停用功能

Parallels Desktop 19 mac是一款功能强大的虚拟机软件&#xff0c;它允许用户在Mac电脑上同时运行Windows、Linux和其他操作系统。Parallels Desktop提供了直观易用的界面&#xff0c;使用户可以轻松创建、配置和管理虚拟机。 Parallels Desktop 19 for Mac停用功能 从Paralle…

python+unittest+requests+HTMLRunner编写接口自动化测试集

问题描述&#xff1a; 搭建接口测试框架&#xff0c;执行用例请求多个不同请求方式的接口 实现步骤&#xff1a; ① 创建配置文件config.ini&#xff0c;写入部分公用参数&#xff0c;如接口的基本url、测试报告文件路径、测试数据文件路径等配置项 1 [DATABASE] 2 data_addre…

xcode15一直显示正在连接iOS17真机问题解决

前言 更新xcode15之后&#xff0c;出现了各种报错问题&#xff0c;可谓是一路打怪啊&#xff0c;解决一个报错问题又来一个。没想到到了最后还能出现一个一直显示正在连接iOS17真机的问题 一直显示正在连接iOS17真机的问题 问题截图如下&#xff1a; 解决方法 1. 打开De…

使用canvas做了一个最简单的网页版画板,5分钟学会

画板实现的效果&#xff1a;可以切换画笔的粗细&#xff0c;颜色&#xff0c;还可以使用橡皮擦&#xff0c;还可以清除画布&#xff0c;然后将画的内容保存下载成一张图片&#xff1a; 具体用到的canvas功能有&#xff1a;画笔的粗细调整lineWidth&#xff0c;开始一个新的画笔…

紫光同创FPGA实现HSSTLP高速接口通信,8b/10b编解码数据回环,提供PDS工程源码和技术支持

目录 1、前言免责声明 2、我这里已有的 GT 高速接口解决方案3、设计思路框架HSSTLP详解HSSTLP基本了解HSSTLP之时钟HSSTLP之PCSHSSTLP之PMAHSSTLP之接口说明 硬件设计HSSTLP IP调用和配置 4、PDS工程详解5、上板调试验证并演示6、福利&#xff1a;工程代码的获取 紫光同创FPGA实…

js实现在报表参数界面获取body中控件的值

要在报表参数界面获取body中控件的值&#xff0c;你可以使用JavaScript来实现。下面是一个详细的介绍&#xff1a; 1. DOM&#xff08;文档对象模型&#xff09;&#xff1a; - DOM是用于操作HTML文档的API&#xff0c;它允许你通过JavaScript访问和操作文档中的元素。 - 在报…

网络通信和tcp协议

一、计算机网络架构模型 1、OSI七层模型 2、TCP/IP模型 3、TCP/IP协议族 无论是什么网络模型&#xff0c;都是为上一层提供服务&#xff0c;抽象层建立在低一层提供的服务上&#xff0c;每层都对应不同的协议 4、地址和端口号 1&#xff09;MAC地址 MAC 地址共 48 位&#…

ARM映像文件组成

引言 ARM编译器将各种源文件&#xff08;汇编文件、C语言程序文件、C语言程序文件&#xff09;编译生成ELF格式的目标文件&#xff08;后缀为.o文件&#xff0c;以下将目标文件简称为.o文件&#xff09;&#xff0c;.o文件经过连接器&#xff0c;和C/C运行时库一起编译生成ELF格…

visual studio Qt 开发环境中手动添加 Q_OBJECT 导致编译时出错的问题

问题简述 创建项目的时候&#xff0c;已经添加了类文件&#xff0c;前期认为不需要信号槽&#xff0c;就没有添加宏Q_OBJECT,后面项目需要&#xff0c;又加入了宏Q_OBJECT&#xff0c;但是发现只是添加了一个宏Q_OBJECT&#xff0c;除此之外没有改动其它的代码&#xff0c;原本…

十四天学会C++之第八天:文件操作

1. 文件的打开和关闭 文件操作的基本概念。打开文件&#xff1a;使用fstream库打开文件以供读写。关闭文件&#xff1a;确保文件在使用完毕后正确关闭。 文件的打开和关闭&#xff1a;C 文件操作入门 在C编程中&#xff0c;文件操作是一项重要的任务&#xff0c;可以读取和写…

51单片机KeyWard

eg1&#xff1a; 单片机键盘的分类 键盘分为编码键盘和非编码键盘&#xff0c;键盘上闭合键的识别由专用的硬件编码器实现&#xff0c;并产生键编码号或键值得称为编码键盘&#xff0c;如计算机键盘&#xff0c;而靠软件来识别的称为非编码键盘&#xff0c;在单片机组成的各种…