【C++进阶】STL容器--stack和queue深度剖析优先队列适配器原理

目录

前言

 1. 容器的使用

1.1 stack

1.2 queue

 2. 什么是适配器

3. stack&&queue底层实现

4. deque的简单介绍

4.1 deque的缺陷

5. priority_queue

 思考

 6. priority_queue的实现


前言

        栈和队列在C语言中大家都有所了解,C语言的栈和队列都是我们手动去实现,而C++中的栈和队列不同,它们的内部并不是自己实现的,而是适配器模式,它们都是容器适配器;本文将会围绕栈和队列来介绍适配器的原理;

在这里插入图片描述

 1. 容器的使用

         在深入了解STL容器之前,我们先来看看stack和queue库里边提供了哪些接口;

1.1 stack

栈的功能接口及简介

1.2 queue

队列的功能接口及简介

 从这些接口及功能上我们发现,栈和队列它们都不支持遍历;在刷题时,栈的应用相较来说也比较多;

下边是一些练习题目,可以练习一下:

 最小栈(力扣)

 栈的压入和弹出序列(牛客)

 逆波兰表达式求值(力扣)

 二叉树的层序遍历(力扣)

 二叉树的层序遍历使用队列解决

 2. 什么是适配器

        适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口

 它的核心其实就是复用,举个日常生活中的例子,充电器的适配器:

3. stack&&queue底层实现

         开始时提到stack和queue都是容器适配器,那到底什么是容器适配器?我们先来看看它的底层声明或许就会明白了:

stack:

 queue:

         它们用到了两个模板参数,一个是存储的数据类型,一个就是底层实现的容器;它们默认使用的都是deque(双端队列);

 那到底什么是容器适配器?容器适配器即将特定容器类封装作为其底层容器类

 了解完这些我们可以上手来实现一下:

我们可以复用其他容器的接口来实现封装,为了和库里尽量保持一致,我们也使用双模板参数:

实现代码如下:

template<class T, class container = deque<T>>
class stack
{
public:
	void push(const T& x)
	{
		return _con.push_back(x);
	}

	void pop()
	{
		return _con.pop_back();
	}

	T& top()
	{
		return _con.back();
	}

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

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

private:
	container _con;
};

队列

template<class T, class container = deque<T>>
class queue
{
public:
	void push(const T& x)
	{
		return _con.push_back(x);
	}

	void pop()
	{
		return _con.pop_front();
	}

	T& front()
	{
		return _con.front();
	}

	T& black()
	{
		return _con.black();
	}

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

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

private:
	container _con;
};

 在调用时我们也可以控制它底层使用的容器

queue<int, list<int>> q1;
stack<int, vector<int>> st;

我们在用STL库里的stack和queue时也没有传参啊?

这是因为库里边给Container(容器)一个缺省参数,默认使用的是deque(双端队列)

4. deque的简单介绍

双端队列名字中带有队列,但它其实并不是队列;

队列要求尾进头出,而双端队列可以双向进出;

 简介

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

         双端队列同时具体它们的优点,在功能上deque可以算的上是list和vector的结合版;

 它的使用和list、vector的使用方法基本一致,但它的底层相较于它们却非常复杂;

 deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成,实际deque类似于一个动态的二维数组;

 数组里边存的是指针,指针指向的是一个个的buff数组,这个存放指针的数组也叫作中控数组

 中控满了进行扩容时,会直接开一块新空间,将内容拷贝过去(拷贝指针代价较小)

4.1 deque的缺陷

         与vector相比,deque的优势是:头插和头删时,不需要挪动数据,效率很高,扩容时也不需要大量的挪动数据(只需要挪作指针即可);

         与list相比,其底层是连续空间,空间利用率比较高;

         它的各个属性都还可以可谓是 “ 六边形战士 ”,但是它的各个属性都不是最顶尖的;它的遍历效率没有vector高,中间插入删除操作没有list效率高;所以它主要作为stack和queue的底层容器;

主要原因有两个:

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作;
  2. 在stack中需要扩容时,deque比vector的效率高(扩容时不需要搬移大量数据),在queue中空间利用率较高,不需要频繁开空间;

5. priority_queue

         优先队列它也是一种容器适配器,默认情况下priority_queue类实例化时使用的是vector;

 那优先队列到底是什么?本质是其实就是堆,在默认情况下是大堆,通过我们所传的模板参数进行控制;

 如果要创建小堆,将第三个模板参数换成greater比较方式

vector<int> v = { 3,1,5,6,4,0 };
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());

 思考

 实现优先队列之前思考一个问题,优先队列需不需要实现:构造函数、拷贝构造、析构函数 ?

         不需要,优先队列是一种容器适配器,它是通过其他容器封装来的,使用时生成默认的构造函数、拷贝构造、析构函数;它们又会去调用底层容器的构造函数、拷贝构造、析构函数;

 6. priority_queue的实现

         堆的相关内容前边已经介绍过了,详细介绍可见:二叉树的顺序存储(堆)

   priority_queue基本框架如下:

template<class T, class container = vector<T>>
class priority_queue
{
public:

	
private:
	container _con;
};

堆的核心内容就在于向上调整和向下调整(默认大堆),实现代码如下:

 向上调整:

void adjust_up(int child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_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())
	{
		if (child + 1 < _con.size() && _con[child] < _con[child + 1])
		{
			child++;
		}
		if (_con[parent] < _con[child])
		{
			swap(_con[parent], _con[child]);
			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);
}

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

T& top()
{
	return _con[0];
}
size_t size()
{
	return _con.size();
}

         以上便是priority_queue的基本实现;细心的朋友可能会发现,我们实现的与库里的有些不同,在调整大堆小堆时也不能通过传参控制,对于当前实现的priority_queue我们还需要做进一步的封装,达到这些需求需要了解模板相关的其他内容;下期我将会再次深入探讨模板——模板进阶;

 以上便是本文的全部内容,希望可以对你有所帮助,感谢阅读!

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

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

相关文章

2024最新版本Teamviewer安装和使用

事情背景 今年元宵节刚好是周末&#xff0c;就回趟家&#xff0c;整个项目几百人都解决不了的问题&#xff0c;眼巴巴要看着要我分析。我就只能远程看看&#xff0c;结果向日葵卡得不行&#xff0c;同事推荐用Teamviewer&#xff0c;诶&#xff0c;真香。 由于现在Teamviewer…

神经网络系列---权重初始化方法

文章目录 权重初始化方法Xavier初始化&#xff08;Xavier initialization&#xff09;Kaiming初始化&#xff0c;也称为He初始化LeCun 初始化正态分布与均匀分布Orthogonal InitializationSparse Initializationn_in和n_out代码实现 权重初始化方法 Xavier初始化&#xff08;X…

ETL数据仓库的使用方式

一、ETL的过程 在 ETL 过程中&#xff0c;数据从源系统中抽取&#xff08;Extract&#xff09;&#xff0c;经过各种转换&#xff08;Transform&#xff09;操作&#xff0c;最后加载&#xff08;Load&#xff09;到目标数据仓库中。以下是 ETL 数仓流程的基本步骤&#xff1a…

工作中常见问题总结

工作中常见错误清单 1、springboot实现无数据库启动 问题 springboot往往是作为b/s系统的server端的架子来使用&#xff0c;但是有些时候&#xff0c;是作为静默的server&#xff0c;并没有界面和数据库&#xff0c;但是springboot默认是链接数据库的&#xff0c;如何解决这个…

sql-labs第46关 order by盲注

sql-labs第46关 order by盲注 来到了第46关进入关卡发现让我们输入的参数为sort&#xff0c;我们输入?sort1尝试&#xff1a; 输入?sort2,3,发现表格按照顺序进行排列输出&#xff0c;明显是使用了order by相关的函数。 我们将参数变成1进行尝试&#xff0c;就会报错&…

C++基础学习——哈希表的封装

目录 ​编辑 一&#xff0c;实现一个可封装的哈希表 1&#xff0c;哈希表的节点 2&#xff0c;哈希表的成员 3&#xff0c;哈希表成员方法的实现 4&#xff0c;迭代器的实现 5&#xff0c;在哈希表中加入迭代器 二&#xff0c;封装哈希表 1&#xff0c;unorder_map封装 2…

【hot100】跟着小王一起刷leetcode -- 49. 字母异位词分组

【【hot100】跟着小王一起刷leetcode -- 49. 字母异位词分组 49. 字母异位词分组题目解读解题思路代码实现 总结 49. 字母异位词分组 题目解读 49. 字母异位词分组 ok&#xff0c;兄弟们&#xff0c;咱们来看看这道题&#xff0c;很明显哈&#xff0c;这里的关键词是字母异位…

2024生物发酵展全面进行-飞翔泵业制造

参展企业介绍 江苏飞翔泵业制造有限公司始建于上世纪八十年代&#xff0c;二00一年根据《公司法》组建江苏飞翔泵业制造有限公司。公司集科研、设计、生产、经营、服务为一体&#xff0c;企业性质为有限责任公司。现为中国石化集团公司物资资源一级网络成员厂&#xff0c;中国石…

备考2025年考研数学(一)真题练习和解析——填空题

今天距离2025年考研预计还有10个月的时间&#xff0c;看起来挺长&#xff0c;但是对于备考2025年考研的同学来说&#xff0c;必须用好每一天。为了帮助大家提升考研数学一的成绩&#xff0c;我收集整理了1987-2024年的考研数学一的真题和解析&#xff0c;并把2015-2024年十年的…

抖店是怎么运营做起来的?抖音小店每天都需要做什么?新手必看!

大家好&#xff0c;我是电商花花。 很多人疑惑开抖音小店之后&#xff0c;选好商品上架之后每天都需要做什么&#xff1f; 不少新手在开了抖音小店之后每天除了选品之后就不知道要做些什么了。 今天给大家分享一下我们每天做抖音小店的工作内容有哪些&#xff0c;如果你是新…

matlab生成模拟的通信信号

matlab中rand函数生成均匀随机分布的随机数&#xff0c;randn生成正态分布的随机数&#xff1b; matlab来模拟一个通信信号&#xff1b; 通信信号通过信道时&#xff0c;研究时认为它会被叠加上服从正态分布的噪声&#xff1b; 先生成随机信号模拟要传输的信号&#xff0c;s…

【一】【SQL】表的增删查改(部分)

表之“增”操作 建表的操作 mysql> create table students(-> id int unsigned primary key auto_increment,-> sn int unsigned unique key,-> name varchar(20) not null,-> qq varchar(32) unique key-> ); Query OK, 0 rows affected (0.03 sec)mysql&g…

试一下newb,还是有错误呀

解题&#xff1a;原式&#xff1d; 2. 在递增的等比数列 ( a n ) (a_n) (an​)中&#xff0c;若 ( a 3 − a 1 5 2 ) (a_3 - a_1 \frac{5}{2}) (a3​−a1​25​), ( a 2 3 ) (a_2 3) (a2​3), 则公比 (q) A. ( 4 3 ) ( \frac{4}{3} ) (34​) B. ( 3 2 ) ( \frac{3}{2} …

创建vue3项目(基础)

首先打开自己的目录文件输入指令cmd 出现命令行工具 输入指令vue create 项目名称 按回车 选择第三个自己配置 根据需求选择 回车 选择自己需要的版本 出现这个 一直按回车大约5下或者6下 创建完毕 结束 感谢观看

Flutter(二):Row、Column 布局

MaterialApp 对于 MaterialApp&#xff0c;组件提供了一些默认的属性&#xff0c;如AppBar、标题、背景颜色等&#xff0c;你可以默认使用它们 import package:flutter/material.dart;void main() {runApp(const App()); }class App extends StatelessWidget {const App({super…

《名作欣赏》期刊投稿方向投稿邮箱

《名作欣赏》杂志是由国家新闻出版总署批准的正规学术期刊。文学是用语言塑造形象反映社会生活的一种语言艺术&#xff0c;是自觉、独立而又面向整个社会的艺术&#xff0c;是文化中极具强烈感染力的重要组成部分&#xff0c;亦是对美的体现。在现代社会&#xff0c;物欲横流&a…

用matlab实现交通分布预测方法——增长系数法

前言 对于我的第一篇文章&#xff1a;Matlab实现交通分布预测方法 —— 增长系数法 | 平均增长率法、底特律法、福莱特法&#xff0c;有不少同学私信我询问关于如何在 matlab 中调用函数、拆分代码以及需要大量调用的问题。于是我便想着把内容做一些优化&#xff0c;放在这篇文…

【MySQL】MySQL从0到0.9 - 持续更新ing

MySQL SQL 基础 DDL 语句 show databases; show tables; desc table_name; # 获取表信息 show create table 表名; // 查询指定表的建表语句 数据类型 char(10) 不满10个会用空格填充&#xff0c;性能好一点 varchar(10) 变长字符串&#xff0c;性能差一点 CREATE TABLE tabl…

nginx设置缓存时间

一、设置缓存时间 当网页数据返回给客户端后&#xff0c;可针对静态网页设置缓存时间&#xff0c;在配置文件内的http段内server段添加location&#xff0c;更改字段expires 1d来实现&#xff1a;避免重复请求&#xff0c;加快访问速度 第一步&#xff1a;修改主配置文件 #修…

[NOIP2011 普及组] 数字反转

AC代码&#xff1a; #include<iostream>using namespace std;int main() {long long n;cin >> n;long long temp n;long long sum 0;while(temp ! 0){int c temp % 10;sum sum * 10 c;temp temp / 10;}printf("%lld",sum);return 0; }