C++入门第九篇---Stack和Queue模拟实现，优先级队列

前言：

我们已经掌握了string vector list三种最基本的数据容器模板，而对于数据结构的内容来说，其余的数据结构容器基本都是这三种容器的延申和扩展，在他们的基础上扩展出更多功能和用法，今天我们便来模拟实现一下C++库中的栈和队列以及优先级队列。

1.适配器：

让我们打开stack模板库的介绍界面，我们会看到这样一个东西：
在这里插入图片描述
stack的模板中的这个Container是什么呢？没错，在这里我们将其称之为适配器，它的作用是，为我们的的栈或者其他数据结构自动匹配底层的容器模板库，如下：

template<class T, class Container = deque<T>>
class stack
{
private:
	Container _con;
};
int main()
{
  hbw::stack<int,list<int>> a1;
}

你会发现，我们的私有的成员直接就是适配器类型的，这样当我们的主程序让其适配器为list类型的时候，适配器会去判断当前的stack的功能函数能否复用到list的成员函数中，倘若可以，我们就可以通过list的底层模板函数功能直接实现出stack的功能。
因此，只要我们的容器的底层容器的功能能够匹配我们当前容器的功能，适配器就可以自动适配到对应的容器中，这样的复用大大节省了效率，让我们在开发时不用再去自己构建复杂的函数和对应的容器即可实现，或许我这样说，你还没法理解，我们接下来的栈和队列的模拟实现的代码，你通过去与我C语言实现的栈和队列去对比即可明白。

deque容器:

依旧是拿出来我们的stack的模板参数，你会发现，它在适配器参数上给了个缺省值deque，根据刚才的是适配器的知识点我们知道，这里的container指代的是一个容器类型，故我们的deque也一定是一个容器类型，因此，我们可以先猜测一下，这个deque为何让它作为缺省参数呢？
根据之前的C语言栈的队列篇我曾经说到，栈和队列都是可以同时使用数组和链表来实现的，对应到C++里，也就是说vector或者list都可以作为stack的底层，因此，作为缺省值，这个deque理论上应当具备两者都有的功能，如下：
在这里插入图片描述
没错，从它的成员函数来看，它既可以和vector一样去利用[]访问下标，也可以实现list的头删头插，访问头尾的功能，因此，在这里让deque作为缺省值，确实是合适不过的，但是，它是如何同时具备两种数据结构的特点的呢？下面让我们一起来分析一下它的容器构建原理：

deque容器的介绍：

deque被称为双端队列。虽然叫它队列，但实际上它并不是队列，也就是说它不是仅仅可以尾插头删，只不过叫这个名字，这个首先要明确，别搞混。它是一种从中间向两边延申的结构，在它的模板中，我们看到了deque使用了内存池allocator来存储数据：
在这里插入图片描述
或许说到这里，我们大致猜出来deque的大体模型是怎样的了，在我看来更类似即可几个数组通过某种方式拼接，让这些数组在逻辑上是连续的，deque的具体构造如下图：
在这里插入图片描述

我们的deque支持两个容器的功能，可以说它的功能是全面的，而我们也知道它使用了内存池allocator,这个内存池的就是我们上图中的BUFF子数组，每一个BUFF数组的长度都是统一的，这样方便我们的下标访问执行。
它实现功能大致如下：
1.尾插：
则在最后一个数组之后再开辟一个新的BUFF，将尾插数据放在这个数组的第一位
2.头插：
在第一个BUFF之前再开辟一个BUFF，将头插数据放在这个数组的最后一位
我们发现，这样的处理方式是没有扩容的消耗的，也不需要挪动数据，很高效
3.之间插入：
中间插入时，我们只有两种办法：
1.BUFF进行扩容/控制数据个数
2.局部整体挪动
这两种方法都可以，但是都有各自的缺点，比如，如果我们对BUFF进行扩容，就会影响我们的[]下标访问，根据deque的结构我们可以总结出，deque下标的计算公式是：x=i/10+i%10,当然，这里是我们假设我们的BUFF都为10的情况下，因此，首先/10确定对应的元素在哪个BUFF子数列里，然后%10确定它在这个子数列的第几个，这样，我们就可以精确的锁定位置，从而让下标访问生效。所以，一旦我们去修改BUFF的长度，就会导致我们这个公式直接无效，十分影响[]访问，但倘若挪动数据，则又会消耗大量的时间，因此，两种方案各有取舍，我们可以根据库STL去看看官方是如何实现的。
我们的deque只涉及到中控数组的扩容问题。但是，由于存储的数据是指针，故只要进行浅拷贝即可，因此，它扩容的消耗并不大。
综上，虽然deque兼具vector和list的双重特点，但它却没有将自己的特性优化到极致，我们可以说deque在头插和尾插方面确实有很大的优势，但是它的下标访问和中间的增删都不如vector和list，具体的deque的实现如下：
在这里插入图片描述
它一共有四个指针去控制整个结构，其中cur用来指针的实时位置，first指向一个BUFF的头，last指向这个BUFF的尾部，而node则用来控制中控数组的指针，当cur==last的时候，node自动向下移动一位，从而实现了下标的连续访问。

2.stack模拟实现：

有了前面的知识铺垫，我们已经不需要怎样去解释实现的细节，直接按照代码理解即可

namespace hbw
{
	template<class T, class Container = deque<T>>//这里通过这个模板参数控制底层的容器是哪个类型，是谁，这个Container即为适配器，不管底层容器是谁，它都可以适配一个后进先出的栈，如果适配器不适用(比如对应的底层的容器不支持上层的功能）,则编译器会报错
	class stack//我们在这里加上了一个缺省参数，deque容器，这就符合了我们倘若不传对应的数据类型，编译器就会为我们自动适配deque容器，deque容器是一个功能很全面的容器，虽然效率上不够极致，但是泛用性强，故用在这里可以支持list和vector两者的全部功能，从而有了作为缺省值的条件
	{
	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;
	};
}

3.queue模拟实现:

namespace hbw
{
	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;
	};
}

他们两个的本质都是复用，复用底层的函数封装成自己的函数功能，这就是适配器的优点所在，不过，值得注意的是，适配器只能转换为符合当前功能的底层容器，对于不符合功能的容器，编译器是没法通过的

4.优先级队列priority_queue容器：

何为优先级队列，即是一个优先按照升序或者降序存储输出值的容器，我们可以先看一下它的一些模板功能：
在这里插入图片描述
没错，看到它的函数功能，它可以返回顶部的元素，又结合它按照顺序输出数的特性，我们不难看出，它很像我们曾经模拟实现的一个数据结构-堆。因此，它的默认底层容器为vector，也就死用数组作为默认的缺省底层容器
没错，虽然叫它优先级队列，但实际上，它的本质就是一个升序或者降序的堆，既然是堆，我们就可以复用我们之前学过的堆的各种接口，故它的模拟实现如下：
首先，我们依旧使用适配器来作为priority_ queue的底层如下：

  template<class T,class Container=vector<T>,class Comapre=Less<T>>
	private:
		Container _con;
	};

1.push函数:

	void Adjustup(int child)//向上调整
	{
		Compare com;
		int parent = (child-1)/ 2;
		while (child > 0)
		{
			if (com(_con[parent],_con[child]))
			{
				std::swap(_con[child], _con[parent]);
				child = parent;
				parent = (parent - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
void push(const T& x)
{
	_con.push_back(x);
	Adjustup(_con.size()-1);
}

push函数，我们的基本思路就是，将任意数据放入我们的底层容器后，将其向上调整到对应的位置，保证我们的堆的数据之间的关系不会乱，这里的向上调整的函数之前实现过，在这里我们可以复习一遍。

2.pop函数：

void Adjustdown(int parent)//向下调整
{
	Compare com;
	int child = 2 * parent + 1;
	while(child<_con.size())
	{
		if (child + 1 < _con.size() &&com(_con[child],_con[child+1]))
		{
			child++;
		}
		if(com(_con[parent],_con[child]))
		{
			std::swap(_con[child], _con[parent]);
			parent = child;
			child = 2 * child + 1;
		}
		else
		{
			break;
		}
	}
}
	void pop()
	{
		std::swap(_con[0],_con[_con.size()-1]);
		_con.pop_back();//尾删一个
		Adjustdown(0);
	}

对于删除来说，我们一定是删除头数据比较有价值，故我们采取的方式是，首先让头尾数据交换位置，然后将尾部数据删除，然后将头数据向下调整到正确的位置，保证堆的数据大小关系不会错误。

3.其余的接口

const T& top()
{
	return _con[0];
}

bool empty()
{
	return _con.empty();
}

size_t size()
{
	return _con.size();
}

T& operator[](size_t i)
{
	return _con[i];
}

都是一些很简单的接口，我在这里不多解释，读代码就应该能看懂。

4.仿函数(关键！！！！）：

在这里插入图片描述
在priority_queue中，我们看到了这样的一个模板参数，compare，它的默认参数值给了一个less，经过尝试，我们知道，这个less实际上就是构建大堆的意思，但是，在这里的这个Compare是什么意思呢？这就是我们要说的仿函数.
那什么是仿函数呢？我们先看一个例子：

template<class T>
class Less//仿函数less
{
public:
	bool operator()(T& x, T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater//仿函数greater
{
public:
	bool operator()(T& x, T& y)
	{
		return x > y;
	}
};

仿函数的本质就是一个只封装了一个()运算符重载的函数的类，当我们使用的时候，直接在类名后面带上括号即可调用这个函数，导致我们看到它的形式就类似一个函数调用，但本质上它依旧是一个类，所以称它为仿函数。如下：

void Adjustdown(int parent)//向下调整
{
	Compare com;
	int child = 2 * parent + 1;
	while(child<_con.size())
	{
		if (child + 1 < _con.size() &&com(_con[child],_con[child+1]))
		{
			child++;
		}
		if(com(_con[parent],_con[child]))
		{
			std::swap(_con[child], _con[parent]);
			parent = child;
			child = 2 * child + 1;
		}
		else
		{
			break;
		}
	}
}

当我们看到这个compare com时，这个com就是仿函数类，后续比较的时候，直接利用仿函数传入参数就可以直接进行比较,比如这里的com(_con[child],_con[child+1]。

仿函数的优点和用处：

有了仿函数，我们就可以像预处理那样对一些运算方法进行复用和小成本的修改，比如我们想从建立大堆变成建立小堆，就像上面一样，分别写一个大堆一个小堆两个仿函数，想使用哪个直接在模板参数里实例化即可，这样提高了效率。
但是仿函数的用处更多的在于它替换了函数指针，我们不用在写繁杂的函数指针参数去使用回调函数，不仅难写而且易错，而是利用仿函数，调用即可，其实本质上仿函数和回调函数的用处一样的，但是仿函数更加好用和简单。
一般仿函数都写成模板类，让其可以针对任意类型进行函数使用，让其运用的场景更加广泛。

5.构造函数：迭代器数据传入构造建堆

priority_queue()//写一个默认无参的构造函数，让编译器自己生成默认的构造函数构成重载
{}

template<class InputIterator>
priority_queue(InputIterator first, InputIterator end)//利用区间进行构造函数
	:_con(first,end)//首先利用vector可以区间构造的特点，先把数据放入到vector容器中
{
	int i = 0;
	for (i = (_con.size() - 2) / 2; i >= 0; i--)
	{
		Adjustdown(i);
	}
}

priority_queue支持传入迭代器区间去建堆，其构造的特点就是首先利用底层容器的vector支持迭代器区间构建数组的特点先初始化_con,然后利用向下建堆的方法，从而建立一个堆，但是写下这个构造函数之后，我们的默认构造函数就没有了，也就是说，后续的构造函数都得传区间，这个是不一定，故我们再写一个默认无参或者全缺省的构造函数，这个就是由编译器自动生成的构造函数，由此，我们就可以同时支持区间迭代器构造和默认构造了。

总结：

以上便是我们的stack queue 优先级队列的基本内容，到这里，我们基本已经掌握了STL库的基本容器模板，但我还是要强调的一点，我已经反复强调了，模拟实现模板的目的是让我们更好的去使用模板，从C语言的思维中走出来，尝试利用C++的思维去解题和分析，熟练的利用模板去简化代码和提高开发效率。同时，模拟实现的过程中我们也学到了如迭代器，迭代器自定义封装，内存池，如何忽略空格任意字符识别，如何扩容，迭代器失效，仿函数等一系列更加重要的属于C++的知识点，我认为这些才是关键，因此，我们应该要抓住我们的重点去学习，在我看来，这是最关键的。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【OpenSTL】方便好用的时空预测开源库

【OpenSTL】方便好用的时空预测开源库

OpenSTL&#xff1a;方便好用的时空预测开源库 时空预测学习是一种学习范式&#xff0c;它使得模型能够通过在无监督的情况下从给定的过去帧预测未来帧&#xff0c;从而学习空间和时间的模式。尽管近年来取得了显著的进展&#xff0c;但由于不同的设置、复杂的实现和难以复现性…
阅读更多...
Go语言的学习笔记2——Go语言源文件的结构布局

Go语言的学习笔记2——Go语言源文件的结构布局

用一个只有main函数的go文件来简单说一下Go语言的源文件结构布局&#xff0c;主要分为包名、引入的包和具体函数。下边是main.go示例代码&#xff1a; package mainimport "fmt"func main() { fmt.Println("hello, world") }package main就是表明这个文件…
阅读更多...
AlDente Pro v1.22.2(mac电池最大充电限制工具)

AlDente Pro v1.22.2(mac电池最大充电限制工具)

AlDente Pro是一款适用于Mac操作系统的小工具&#xff0c;可以帮助您限制电池充电量以延长电池寿命。通常情况下&#xff0c;电池在充满的状态下会继续接受电源充电&#xff0c;这可能会导致电池寿命缩短。使用AlDente Pro&#xff0c;您可以设置电池只充到特定的充电水平&…
阅读更多...
高清动态壁纸软件Live Wallpaper Themes 4K mac中文版功能

高清动态壁纸软件Live Wallpaper Themes 4K mac中文版功能

Live Wallpaper & Themes 4K mac是一款提供各种高清动态壁纸和主题的应用程序。该应用程序提供了大量的动态壁纸和主题&#xff0c;包括自然、动物、城市、抽象等各种类别&#xff0c;可以满足用户不同的需求。除了壁纸和主题之外&#xff0c;该应用程序还提供了许多其他功…
阅读更多...
拦截器详解

拦截器详解

一、概述 什么是拦截器&#xff1f; 是一种动态拦截方法调用的机制&#xff0c;类似于过滤器。Spring框架中提供的&#xff0c;用来动态拦截控制方法的执行。 到底是干啥用的&#xff1f; 拦截请求用的&#xff0c;在指定的方法调用前后&#xff0c;执行在拦截器中编写的程序 …
阅读更多...
苹果App加急审核

苹果App加急审核

苹果App加急审核 &#xff08;注意加急的次数&#xff0c;有的说一年能加急两次&#xff0c;有的说不止两次。遇到紧急问题了就用&#xff0c;非紧急 等一等也行&#xff09; 1.登录苹果账号 Sign In - Apple &#xff08; https://developer.apple.com/contact/app-store/?…
阅读更多...
力扣每日一道系列 --- LeetCode 206. 反转链表

力扣每日一道系列 --- LeetCode 206. 反转链表

&#x1f4f7; 江池俊&#xff1a; 个人主页 &#x1f525;个人专栏&#xff1a; ✅数据结构探索 ✅LeetCode每日一道 &#x1f305; 有航道的人&#xff0c;再渺小也不会迷途。 LeetCode 206. 反转链表 思路一&#xff1a;头插 初始化两个指针&#xff0c;cur 和 newhead。…
阅读更多...
单片机、ARM、嵌入式开发、Android 底层开发有什么关系？

单片机、ARM、嵌入式开发、Android 底层开发有什么关系？

单片机、ARM、嵌入式开发、Android 底层开发有什么关系&#xff1f; 从我目前的见识来看&#xff1a; 单片机是个系统&#xff08;比如&#xff1a;51、AVR、PLC...&#xff09;&#xff0c;其中包含了去除了输入输出之外的运算器、控制器、存储器&#xff0c;我们用程序可以非…
阅读更多...
CANdelaStudio 使用教程3 新建Service

CANdelaStudio 使用教程3 新建Service

文章目录 简述Service 的相关配置项1、Protocol Services2、Diagnostic Class Templates3、Supported Diagnostic Classes 新建 Service1、新建 Service2、新建类并添加服务3、 选择支持的服务4、Diagnostic Class Templates&#xff1a;Identification 编辑 Service1、新增服务…
阅读更多...
区块链技术将如何影响未来的数字营销？

区块链技术将如何影响未来的数字营销？

你是否听腻了区块链和数字营销等流行语&#xff0c;却不明白它们对未来意味着什么&#xff1f;那么&#xff0c;准备好系好安全带吧&#xff0c;因为区块链技术将彻底改变我们对数字营销的看法。从建立消费者信任到提高透明度和效率&#xff0c;其可能性是无限的。 让我们来探…
阅读更多...
有序表的详解

有序表的详解

目录 有序表的介绍 树的左旋和右旋操作 AVL树的详解 SB树的详解 红黑树的介绍 SkipList的详解 有序表的介绍 有序表是除具备哈希表所具备的功能外&#xff0c;有序表中的内容都是按照key有序排列的&#xff0c;并且增删改查等操作的时间复杂度都是&#xff0c;红黑树&…
阅读更多...
【超强笔记软件】Obsidian如何实现免费无限流量无套路云同步？

【超强笔记软件】Obsidian如何实现免费无限流量无套路云同步？

【超强笔记软件】Obsidian如何实现免费无限流量无套路云同步&#xff1f; 文章目录 【超强笔记软件】Obsidian如何实现免费无限流量无套路云同步&#xff1f;一、简介软件特色演示&#xff1a; 二、使用免费群晖虚拟机搭建群晖Synology Drive服务&#xff0c;实现局域网同步1 安…
阅读更多...
Educational Codeforces Round 158 (Rated for Div. 2)（A~E）（贪心，树形DP）

Educational Codeforces Round 158 (Rated for Div. 2)（A~E）（贪心，树形DP）

A - Line Trip 题意&#xff1a;有一条路&#xff0c;可以用一条数线来表示。你位于数线上的点 0 &#xff0c;你想从点 0 到点 x &#xff0c;再回到点 0。你乘汽车旅行&#xff0c;每行驶 1个单位的距离要花费 1 升汽油。当您从点 0出发时&#xff0c;汽车已加满油(油箱中的…
阅读更多...
spring boot的自动装配原理

spring boot的自动装配原理

一&#xff1a;简介 SpringBoot 这款框架几乎是现在企业级开发的标配&#xff0c;使用SpringBoot进行开发&#xff0c;能够大量减少xml配置文件的编写&#xff0c;并且能为我们提供一站式服务。SpringBoot我们只需要导入相关模块的starter&#xff0c;就可以使用相关功能&…
阅读更多...
深度学习基于Python+TensorFlow+Django的水果识别系统

深度学习基于Python+TensorFlow+Django的水果识别系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介简介技术组合系统功能使用流程 二、功能三、系统四. 总结 一项目简介 # 深度学习基于PythonTensorFlowDjango的水果识别系统介绍 简介 该水果识别系统基于…
阅读更多...
医保线上购药系统：引领医疗新潮流

医保线上购药系统：引领医疗新潮流

在科技的驱动下&#xff0c;医疗健康服务正经历一场数字化的革新。医保线上购药系统&#xff0c;不仅是一种医疗服务的新选择&#xff0c;更是技术代码为我们的健康管理带来的全新可能。本文将通过一些简单的技术代码示例&#xff0c;深入解析医保线上购药系统的工作原理和优势…
阅读更多...
C#，《小白学程序》第五课：队列（Queue）其一，排队的技术与算法

C#，《小白学程序》第五课：队列（Queue）其一，排队的技术与算法

日常生活中常见的排队&#xff0c;软件怎么体现呢&#xff1f; 排队的基本原则是&#xff1a;先到先得&#xff0c;先到先吃&#xff0c;先进先出 1 文本格式 /// <summary> /// 《小白学程序》第五课&#xff1a;队列&#xff08;Queue&#xff09; /// 日常生活中常见…
阅读更多...
uniapp IOS从打包到上架流程（详细简单） 原创

uniapp IOS从打包到上架流程（详细简单） 原创

uniapp打包好的ipa文件&#xff0c;需要上架到appstore&#xff0c;用户才能通过app store下载使用&#xff0c;因此我们需要将ipa上架到appstore. 我们这篇文章&#xff0c;将教会大家使用windows电脑将uniapp打包好的ipa文件&#xff0c;上架到appstore的方法和详细流程。 …
阅读更多...
SpectralGPT: Spectral Foundation Model 论文翻译2

SpectralGPT: Spectral Foundation Model 论文翻译2

遥感领域的通用大模型 2023.11.13在CVPR发表 原文地址&#xff1a;[2311.07113] SpectralGPT: Spectral Foundation Model (arxiv.org) 实验 ​ 在本节中&#xff0c;我们将严格评估我们的SpectralGPT模型的性能&#xff0c;并对其进行基准测试SOTA基础模型&#xff1a;ResN…
阅读更多...
C#/.NET/.NET Core推荐学习书籍（已分类）

C#/.NET/.NET Core推荐学习书籍（已分类）

前言 古人云&#xff1a;“书中自有黄金屋&#xff0c;书中自有颜如玉”&#xff0c;说明了书籍的重要性。作为程序员&#xff0c;我们需要不断学习以提升自己的核心竞争力。以下是一些优秀的C#/.NET/.NET Core相关学习书籍&#xff0c;值得.NET开发者们学习和专研。书籍已分类…
阅读更多...
最新文章

Copyright @ 2022~2023