c++的学习之路:17、stack、queue与priority_queue

摘要

本文主要是介绍一下stack、queue、priority_queue的使用以及模拟实现,文章末附上代码以及思维导图。

目录

摘要

一、stack的介绍和使用

1、stack的介绍

2、stack的使用

3、stack的模拟实现

二、queue的介绍和使用

1、queue的介绍

2、queue的使用

3、queue的模拟实现

三、priority_queue的介绍和使用

1、priority_queue的介绍

2、priority_queue的使用

3、priority_queue的模拟实现

四、代码

1、stack

2、queue

3、priority_queue

五、思维导图


 

一、stack的介绍和使用

1、stack的介绍

和之前一样这里也是直接介绍一下文档,使用方式和之前的模板大差不差,如下方截图就是cplusplus的介绍,下面四点就是文档上面的翻译,其他的就不详细说了,数据结构里面有更加详细的介绍。

1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。

2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:

empty:判空操作

back:获取尾部元素操作

push_back:尾部插入元素操作

pop_back:尾部删除元素操作

4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque。

44bcb71426bf4a689d374832a3cd9913.png

2、stack的使用

下面的一个表格就是常用的几个函数与接口说明,就不一一说明怎么使用了,和之前vector、list、string所演示的都差不多。

函数说明接口说明
stack()构造空的栈
empty()检测stack是否为空
size()返回stack中元素的个数
top()返回栈顶元素的引用
push()将元素val压入stack中
pop()将stack中尾部的元素弹出

3、stack的模拟实现

这里是直接利用vector作为一个缺省值,直接用模板去创建一栈,这样都可以直接复用vector的函数,这样实现起来就十分容易加上轻松了,如下方代码所示,因为栈不支持迭代器,不能遍历只能一次出一个结果如下方图片所示,其实这里是我康吃康吃写了一个类似c写的那种,然后看了一下源码,大佬不愧是大佬,好轻松。

3e9aa157bed34855b94dd30a65279803.png

namespace ly1
{
	template<class T, class Container = vector<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

	private:
		Container _con;
	};

	void Test_Stack()
	{
		stack<int> s1;
		s1.push(1);
		s1.push(2);
		s1.push(3);
		s1.push(4);
		while (!s1.empty())
		{
			cout << s1.top() << ' ';
			s1.pop();
		}
		cout << endl;
	}
}

 

 

二、queue的介绍和使用

1、queue的介绍

和之前一样这里也是直接介绍一下文档,使用方式和之前的模板大差不差,如下方截图就是cplusplus的介绍,下面四点就是文档上面的翻译,其他的就不详细说了,数据结构里面有更加详细的介绍。

1. 队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。

2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。

3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

empty:检测队列是否为空

size:返回队列中有效元素的个数

front:返回队头元素的引用

back:返回队尾元素的引用

push_back:在队列尾部入队列

pop_front:在队列头部出队列

4. 标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

865bf7703b4848bb98ef3e6209d45ce2.png

2、queue的使用

下面的一个表格就是常用的几个函数与接口说明,就不一一说明怎么使用了,和之前vector、list、string所演示的都差不多。

函数声明接口说明
queue()构造空的队列
empty()检测队列是否为空,是返回true,否则返回false
size()返回队列中有效元素的个数
front()返回队头元素的引用
back()返回队尾元素的引用
push()在队尾将元素val入队列
pop()将队头元素出队列

3、queue的模拟实现

这里也是利用复用直接写的代码和测试如下。

20cbfa36b23d4182b3d06e44c00c6de2.png

namespace ly2
{
	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> q1;
		q1.push(1);
		q1.push(2);
		q1.push(3);
		q1.push(4);
		while (!q1.empty())
		{
			cout << q1.front() << " ";
			q1.pop();
		}
		cout << endl;
	}
}

三、priority_queue的介绍和使用

1、priority_queue的介绍

下面就是优先队列的文档介绍。

1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。

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

3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。

4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:

empty():检测容器是否为空size():返回容器中有效元素个数

front():返回容器中第一个元素的引用

push_back():在容器尾部插入元素

pop_back():删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。

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

3d71be5c46fa4b24b82a51a625225966.png

2、priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。

函数声明接口说明
priority_queue()/priority_queue(first,
last)
构造一个空的优先级队列
empty( )检测优先级队列是否为空,是返回true,否则返回
false
top( )返回优先级队列中最大(最小元素),即堆顶元素
push(x)在优先级队列中插入元素x
pop()删除优先级队列中最大(最小)元素,即堆顶元素

3、priority_queue的模拟实现

这个原理有点像我之前写数据结构的堆,实现方法也差不多,这个优先队列可以进行排序,他默认是降序,代码实现与测试如下。

d2ad3092a0044fff9ccbc572b5f778f4.png

namespace ly3
{
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		priority_queue() : c() {}
		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			int count = c.size();
			int root = ((count - 2) >> 1);
			for (; root >= 0; root--)
				AdjustDown(root);
		}

		void push(const T& data)
		{
			c.push_back(data);
			AdjustUP(c.size() - 1);
		}

		void pop()
		{
			if (empty())
				return;

			swap(c.front(), c.back());
			c.pop_back();
			AdjustDown(0);
		}

		size_t size()const
		{
			return c.size();
		}

		bool empty()const
		{
			return c.empty();
		}

		const T& top()const
		{
			return c.front();
		}
	private:
		void AdjustUP(int child)
		{
			int parent = ((child - 1) >> 1);
			while (child)
			{
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					child = parent;
					parent = ((child - 1) >> 1);
				}
				else
				{
					return;
				}
			}
		}

		void AdjustDown(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < c.size())
			{
				if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
					child += 1;
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					return;
			}
		}
	private:
		Container c;
	};

	void Test_Priority_Queue()
	{
		ly3::priority_queue<int> q1;
		q1.push(5);
		q1.push(1);
		q1.push(4);
		q1.push(2);
		q1.push(3);
		q1.push(6);
		while (!q1.empty())
		{
			cout << q1.top() << " ";
			q1.pop();
		}
		cout << endl;
	}
}

四、代码

1、stack

#pragma once

namespace ly1
{
	template<class T, class Container = vector<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

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

	private:
		Container _con;
	};

	void Test_Stack()
	{
		stack<int> s1;
		s1.push(1);
		s1.push(2);
		s1.push(3);
		s1.push(4);
		while (!s1.empty())
		{
			cout << s1.top() << ' ';
			s1.pop();
		}
		cout << endl;
	}
}

2、queue

#pragma once

namespace ly2
{
	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> q1;
		q1.push(1);
		q1.push(2);
		q1.push(3);
		q1.push(4);
		while (!q1.empty())
		{
			cout << q1.front() << " ";
			q1.pop();
		}
		cout << endl;
	}
}

3、priority_queue

#pragma once

namespace ly3
{
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		priority_queue() : c() {}
		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			int count = c.size();
			int root = ((count - 2) >> 1);
			for (; root >= 0; root--)
				AdjustDown(root);
		}

		void push(const T& data)
		{
			c.push_back(data);
			AdjustUP(c.size() - 1);
		}

		void pop()
		{
			if (empty())
				return;

			swap(c.front(), c.back());
			c.pop_back();
			AdjustDown(0);
		}

		size_t size()const
		{
			return c.size();
		}

		bool empty()const
		{
			return c.empty();
		}

		const T& top()const
		{
			return c.front();
		}
	private:
		void AdjustUP(int child)
		{
			int parent = ((child - 1) >> 1);
			while (child)
			{
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					child = parent;
					parent = ((child - 1) >> 1);
				}
				else
				{
					return;
				}
			}
		}

		void AdjustDown(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < c.size())
			{
				if (child + 1 < c.size() && Compare()(c[child], c[child + 1]))
					child += 1;
				if (Compare()(c[parent], c[child]))
				{
					swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					return;
			}
		}
	private:
		Container c;
	};

	void Test_Priority_Queue()
	{
		ly3::priority_queue<int> q1;
		q1.push(5);
		q1.push(1);
		q1.push(4);
		q1.push(2);
		q1.push(3);
		q1.push(6);
		while (!q1.empty())
		{
			cout << q1.top() << " ";
			q1.pop();
		}
		cout << endl;
	}
}

五、思维导图

2ce6242b15454aa6b6f0dcfe3a619a29.png

 

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

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

相关文章

leetcode刷题日记之接雨水问题

题目描述 解题思路 这个题目相当于一个桶的容量是多少&#xff0c;这取决于最短的模板的高度&#xff0c;&#xff0c;对于位置来讲&#xff0c;第i个位置所能承载的最大的容量为左右两侧最低的高度减去该位置的高度&#xff0c;如果两侧的最低位置小于height【i】&#xff0c…

TSINGSEE青犀边缘计算AI智能分析网关V4客流统计算法的配置步骤及使用

TSINGSEE青犀AI智能分析网关V4内置了近40种AI算法模型&#xff0c;支持对接入的视频图像进行人、车、物、行为、烟火等实时检测分析&#xff0c;上报识别结果&#xff0c;并能进行语音告警播放。硬件支持RTSP、GB28181协议、以及厂家私有协议接入&#xff0c;可兼容市面上常见的…

Python学习从0到1 day21 第二阶段 面向对象 ④ 类型注解

仗剑红尘已是癫&#xff0c;有酒平步上青天 —— 24.4.7 一、变量的类型注解 学习目标 1.理解为什么使用类型注解 2.掌握变量的类型注解语法 为什么使用类型注解 tip&#xff1a;CTRLP&#xff0c;可以提示函数中传入的参数 当我们需要使用pycharm的自动补全功能&#xff0c;又…

Java | Leetcode Java题解之第18题四数之和

题目&#xff1a; 题解&#xff1a; class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> quadruplets new ArrayList<List<Integer>>();if (nums null || nums.length < 4) {return…

(表征学习论文阅读)A Simple Framework for Contrastive Learning of Visual Representations

Chen T, Kornblith S, Norouzi M, et al. A simple framework for contrastive learning of visual representations[C]//International conference on machine learning. PMLR, 2020: 1597-1607. 1. 前言 本文作者为了了解对比学习是如何学习到有效的表征&#xff0c;对本文所…

Disk Drill Enterprise for Mac v5.5.1515数据恢复软件中文版

Disk Drill 是 Mac 操作系统固有的Mac数据恢复软件&#xff1a;使用 Recovery Vault 轻松保护文件免遭意外删除&#xff0c;并从 Mac 磁盘恢复丢失的数据。支持大多数存储设备&#xff0c;文件类型和文件系统。 软件下载&#xff1a;Disk Drill Enterprise for Mac v5.5.1515激…

【YOLOV8】项目目录重点部分介绍和性能评估指标

目录 一 项目目录重点部分介绍 二 性能评估指标 一 项目目录重点部分介绍 1 ultralytics

3D医疗图像配准 | 基于Vision-Transformer+Pytorch实现的3D医疗图像配准算法

项目应用场景 面向医疗图像配准场景&#xff0c;项目采用 Pytorch ViT 来实现&#xff0c;形态为 3D 医疗图像的配准。 项目效果 项目细节 > 具体参见项目 README.md (1) 模型架构 (2) Vision Transformer 架构 (3) 量化结果分析 项目获取 https://download.csdn.net/down…

.NET 设计模式—装饰器模式(Decorator Pattern)

简介 装饰者模式&#xff08;Decorator Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许你在不改变对象接口的前提下&#xff0c;动态地将新行为附加到对象上。这种模式是通过创建一个包装&#xff08;或装饰&#xff09;对象&#xff0c;将要被装饰的对象包裹起来…

基于Springboot考研资讯平台的设计与实现(论文+源码)_kaic

摘 要 随着现在网络的快速发展&#xff0c;网络的应用在各行各业当中它很快融入到了许多学校的眼球之中&#xff0c;他们利用网络来做这个电商的服务&#xff0c;随之就产生了“考研资讯平台”&#xff0c;这样就让学生考研资讯平台更加方便简单。 对于本考研资讯平台的设计来…

npm包安装与管理:深入解析命令行工具的全方位操作指南,涵盖脚本执行与包发布流程

npm&#xff0c;全称为Node Package Manager&#xff0c;是专为JavaScript生态系统设计的软件包管理系统&#xff0c;尤其与Node.js平台紧密关联。作为Node.js的默认包管理工具&#xff0c;npm为开发者提供了便捷的方式来安装、共享、分发和管理代码模块。 npm作为JavaScript世…

C++ | Leetcode C++题解之第18题四数之和

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> quadruplets;if (nums.size() < 4) {return quadruplets;}sort(nums.begin(), nums.en…

谷歌seo自然搜索排名怎么提升快?

要想在谷歌上排名快速上升&#xff0c;关键在于运用GPC爬虫池跟高低搭配的外链组合 首先你要做的&#xff0c;就是让谷歌的蜘蛛频繁来你的网站&#xff0c;网站需要被谷歌蜘蛛频繁抓取和索引&#xff0c;那这时候GPC爬虫池就能派上用场了&#xff0c;GPC爬虫池能够帮你大幅度提…

GD32零基础教程第一节(开发环境搭建及工程模板介绍)

文章目录 前言一、MDK keil5安装二、设备支持包安装三、CH340串口驱动安装四、STLINIK驱动安装五、工程风格介绍总结 前言 本篇文章正式带大家开始学习GD32F407VET6国产单片机的学习&#xff0c;国产单片机性能强&#xff0c;而且价格也便宜&#xff0c;下面就开始带大家来介绍…

致远互联-OA 前台fileUpload.do 绕过文件上传漏洞复现

0x01 产品简介 致远互联-OA 是数字化构建企业数字化协同运营中台,面向企业各种业务场景提供一站式大数据分析解决方案的协同办公软件。 0x02 漏洞概述 致远互联-OA 接口 fileUpload.do 接口处存在文件上传漏洞,未经身份验证的远程攻击者可通过目录遍历的方式绕过上传接口限…

阿里通义千问开源 320 亿参数模型;文字和音频自动翻译成手语Hand Talk拉近人与人的距离

✨ 1: Qwen1.5-32B Qwen1.5-32B是Qwen1.5系列中性能与效率兼顾的最新语言模型&#xff0c;内存占用低&#xff0c;运行速度快。 Qwen1.5-32B是Qwen1.5语言模型系列的最新成员&#xff0c;这个模型是基于先进的技术研发的&#xff0c;旨在提供一种既高效又经济的AI语言理解和生…

Unity面经(自整)——Unity基础知识

Unity基础知识 1. Image和RawImage的区别 Image比RawImage更耗性能。Image只能使用sprite属性的图片。而RawImage什么都可以使用 2. Unity3D中的碰撞器Collider和触发器Trigger的区别 碰撞器是触发器的载体&#xff0c;而触发器是碰撞器上的一个属性。 如果IsTrigger为fal…

Maven POM元素解析

这是对Maven中使用的Maven项目描述符的引用。 <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/…

列车调度

描述 火车站的列车调度铁轨的结构如下图所示。 两端分别是一条入口&#xff08;Entrance&#xff09;轨道和一条出口&#xff08;Exit&#xff09;轨道&#xff0c;它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入&#xff0c;最后从出口离开。在图中有9趟列…

C#操作MySQL从入门到精通(7)——对查询数据进行简单过滤

前言 我们在查询数据库中数据的时候,有时候需要剔除一些我们不想要的数据,这时候就需要对数据进行过滤,比如学生信息中,我只需要年龄等于18的,类似这种操作,本文就是详细介绍如何对查询的数据进行初步的过滤。 1、等于操作符 本次查询student_age 等于20的数据,使用我…