【c++】——栈or队列or优先级队列

目录

🎓容器适配器

🎓Stack栈

🚩Stack的介绍

🚩Stack的基本使用 

🚩Stack底层实现

🎓queue队列

🚩queue的介绍

🚩queue的基本使用

🚩queue的底层实现

🎓priority_queue优先级队列

🚩priority_queue的介绍

✅简单介绍一下仿函数

 🚩priority_queue的基本使用

🚩priority_queue的底层实现

✅仿函数的使用

🎓容器适配器

 容器适配器是一个封装了序列容器的一个类模板，它在一般的序列容器的基础上提供了一些不同的功能。之所以称为容器适配器，是因为它是适配容器来提供其它不一样的功能。通过对应的容器和成员函数来实现我们需要的功能。

        下面介绍了三个容器适配器：statk<T>,queue<T>,priority_queue<T>。

 注意：容器适配器都不存在迭代器。

        如果没有为stack,queue指定容器，默认使用deque作为默认容器。priority_queue容器默认使用vector作为默认容器。

🎓Stack栈

🚩Stack的介绍

以下是stack的成员函数 

string、vector、list都是容器,而stack和queue 是容器适配器,发现stack和queue都没有迭代器，因为stack要保证后进先出(LIFO)，queue要保证先进先出（FIFO）所以其实它们不需要迭代器。

🚩Stack的基本使用 

这下面是stack接口函数，使用是简单的，主要应用的场景。

#include <iostream>
using namespace std;
#include <stack>//记得包头文件
 
int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.push(5);
	st.push(6);
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl;
	return 0;
}

🚩Stack底层实现

stack就是我们数据结构学的栈，是一种操作受限制的线性表，所以它可以用链表实现，也可以用顺序表（数组）实现，不过当时C语言只实现了数组栈，因为相对而言数组的结构实现更优一些。因为数组在尾上插入删除数据的代价比较小。那传统的写法就是用一个数组或链表去写.若按C++STL库里的方式来写，就可以用适配器（配接器）模式来实现。

#pragma once
#include<vector>
#include<list>
#include<deque>

namespace cl {
	template<class T,class Container=deque<T>>//Container缺省用deque容器
	class stack {
	public:
		stack() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_back(); }
		T& top() { return _c.back(); }
		const T& top()const { return _c.back(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		Container _c;
	};

	void test_stack1()
	{
		//stack<int>st;
		stack<int, vector<int>>st;//明确给出用vector容器
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);
		while (!st.empty())
		{
			cout << st.top() << " ";
			st.pop();
		}
		cout << endl;
	}
	void test_stack2()
	{
		stack<int, list<int>>st;//明确给出用list容器
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);
		while (!st.empty())
		{
			cout << st.top() << " ";
			st.pop();
		}
		cout << endl;
	}
}

🎓queue队列

🚩queue的介绍

元素从队尾入队列，从对头出队列。

🚩queue的基本使用

这下面是queue接口函数，使用是简单的，主要应用的场景。

使用queue需要包含头文件#include<queue>，queue容器适配器没有迭代器

int main()
{
	queue<int>q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	cout << q.front() << endl;//队头元素
	cout << q.back() << endl;//队尾元素
	cout << q.size() << endl;//队长
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	return 0;
}

🚩queue的底层实现

因为queue存在头删和尾插，因此使用vector容器来封装效率太低，头删需要挪动数据，并且vector并没有提供pop_front(),因为效率太低。

#pragma once
#include<queue>
#include<list>
namespace cl {
	template <class T,class Container=deque<T>>
	class queue {
	public:
		queue(){}
		void push(const T& x) { _c.push_back(x); }//尾插
		void pop() { _c.pop_front(); }//头删
		T& back() { return _c.back(); }//队尾值
		const T& back()const { return _c.back(); }//取队尾值
		T& front() { return _c.front(); }//队头值
		const T& front()const { return _c.front(); }//取队头值
		size_t size()const { return _c.size(); }//队长
		bool empty()const { return _c.empty(); }//判空

	private:
		Container _c;
	};

	void test_queue()
	{
		queue<int>q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}

	void test_queue2()
	{
		queue<int,list<int>>q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);
		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}
}

🎓priority_queue优先级队列

🚩priority_queue的介绍

默认形成大堆。优先队列使用仿函数来控制生成大根堆还是生成小根堆。

✅简单介绍一下仿函数

 仿函数（Functor）又称为函数对象（Function Object）是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样，不过作为仿函数的类，都必须重载 operator() 运算符。因为调用仿函数，实际上就是通过类对象调用重载后的 operator() 运算符。仿函数是一个类，只是使用起来像函数。等下模拟实现时就知道了。

 🚩priority_queue的基本使用

优先队列默认使用vector作为存储数据的容器，在容器的基础上使用堆算法，将vector中的元素调整成一个堆结构。

注意：优先队列就是一个堆，在使用堆的地方都可以使用优先队列。默认生成大根堆，头文件也是#include<queue>

//默认调整大堆
int main()
{
	priority_queue<int>pq;
	pq.push(1);
	pq.push(2);
	pq.push(5);
	pq.push(3);
	pq.push(0);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
	return 0;
}

//小堆
int main()
{
	priority_queue<int,vector<int>,greater<int>>pq;
	pq.push(1);
	pq.push(2);
	pq.push(5);
	pq.push(3);
	pq.push(0);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
	return 0;
}

🚩priority_queue的底层实现

   回顾一下堆的插入与删除操作。

  •         堆的插入：在堆尾插入数据，再向上调整成堆。
  •         堆的删除：将堆顶元素和对尾元素交换，再向下调整成堆。

#pragma once
#include<vector>
#include<deque>
namespace cl {
	template <class T,class Container=vector<T>>
	class priority_queue {
		void AdjustDown(int parent)
		{
			int 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 Adjustup(int child)
		{
			int parent = (child - 1) / 2;
			while (child >0)
			{
				if (_con[parent]<_con[child])
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}


	public:
		priority_queue() {}
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}
			//建堆
			for (int i = (_con.size - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}
		bool empty() {
			return _con.empty();
		}
		size_t size() {
			return _con.size();
		}
		T& top() {
			return _con.front();
		}
		const T& top()const {
			return _con.front();
		}
		void push(const T& val) {
			_con.push_back(val);
			Adjustup(_con.size() - 1);
		}
		void pop() {
			swap(_con[0], _con[_con.size() - 1]);
			//少一个元素是size减减，交换后，直接删除最后一个元素
			_con.pop_back();
			AdjustDown(0);
		}

	private:
		Container _con;
	};

	void priority_queue1()
	{
		priority_queue<int>pq;
		pq.push(1);
		pq.push(3);
		pq.push(4);
		pq.push(5);
		while(!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}

✅仿函数的使用

仿函数：优先队列通过仿函数来实现建立大根堆还是小根堆。

调整建立大根堆还是小根堆，只需要改变调整函数。父亲结点与孩子结点比较时的大于小于号。怎么通过仿函数来实现呢？

调整函数如何修改

#pragma once
#include<vector>
#include<deque>
template<class T>
class Less {
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};
template<class T>
class Greater {
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};
namespace cl {
	template <class T,class Container=vector<T>,class Compare=Less<T>>
	class priority_queue {
		void AdjustDown(int 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[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void Adjustup(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child >0)
			{
				if (com(_con[parent],_con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}


	public:
		priority_queue() {}
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}
			//建堆
			for (int i = (_con.size - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}
		bool empty() {
			return _con.empty();
		}
		size_t size() {
			return _con.size();
		}
		T& top() {
			return _con.front();
		}
		const T& top()const {
			return _con.front();
		}
		void push(const T& val) {
			_con.push_back(val);
			Adjustup(_con.size() - 1);
		}
		void pop() {
			swap(_con[0], _con[_con.size() - 1]);
			//少一个元素是size减减，交换后，直接删除最后一个元素
			_con.pop_back();
			AdjustDown(0);
		}

	private:
		Container _con;
	};

	void priority_queue1()
	{
		priority_queue<int>pq;//默认调成大根堆
		pq.push(1);
		pq.push(3);
		pq.push(4);
		pq.push(5);
		while(!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;


		priority_queue<int, vector<int>, greater<int>> pq2;//小根堆
		pq2.push(1);
		pq2.push(3);
		pq2.push(4);
		pq2.push(5);
		while (!pq2.empty())
		{
			cout << pq2.top() << " ";
			pq2.pop();
		}
		cout << endl;
	}
}

一帆风顺不现实，祝你挫折少一点。

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

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

相关文章

爬虫之牛刀小试（八）：爬取微博评论

爬虫之牛刀小试（八）：爬取微博评论

今天爬取的是微博评论。 可以发现其特点是下一页评论的max_id在上一页中。 于是代码如下&#xff1a; import requests import json import re import time headers {User-Agent: ,"Cookie": "","Referer": "https://m.weibo.cn/detail/4…
阅读更多...
Kafka-消费者-KafkaConsumer分析-PartitionAssignor

Kafka-消费者-KafkaConsumer分析-PartitionAssignor

Leader消费者在收到JoinGroupResponse后&#xff0c;会按照其中指定的分区分配策略进行分区分配&#xff0c;每个分区分配策略就是一个PartitionAssignor接口的实现。图是PartitionAssignor的继承结构及其中的组件。 PartitionAssignor接口中定义了Assignment和Subscription两个…
阅读更多...
网络安全全栈培训笔记（54-服务攻防-数据库安全RedisHadoopMysqla未授权访问RCE）

网络安全全栈培训笔记（54-服务攻防-数据库安全RedisHadoopMysqla未授权访问RCE）

第54天 服务攻防-数据库安全&Redis&Hadoop&Mysqla&未授权访问&RCE 知识点&#xff1a; 1、服务攻防数据库类型安全 2、Redis&Hadoop&Mysql安全 3、Mysql-CVE-2012-2122漏洞 4、Hadoop-配置不当未授权三重奏&RCE漏洞 3、Redis-配置不当未授权…
阅读更多...
Laya3.0 相机使用

Laya3.0 相机使用

摄像机&#xff0c;是3D场景里边最经常使用的对象了。 官方文档&#xff1a;点击这里学习 1.投影 Projection 透视&#xff1a; 模拟人眼的视觉效果&#xff0c;近大远小。模拟物理世界的规律&#xff0c;将眼睛或相机抽象成一个点&#xff0c;此时视锥体内的物体投影到视平…
阅读更多...
51单片机独立按键

51单片机独立按键

独立按键介绍 在嵌入式系统中&#xff0c;独立按键通常指的是单独的按键开关或按钮&#xff0c;它们通常用于接收用户输入或执行特定的功能。在51单片机&#xff08;指的是Intel 8051或其兼容芯片&#xff09;中&#xff0c;独立按键可以通过简单的硬件连接和软件编程来实现各种…
阅读更多...
Grafana（三）Grafana 免密登录-隐藏导航栏-主题变换

Grafana（三）Grafana 免密登录-隐藏导航栏-主题变换

一. 免密登录 Grafana 的常用方式&#xff1a; 将配置好的Grafana图嵌入到系统页面中 为了实现可免登录访问&#xff0c;可以通过如下方式进行设置&#xff1a; 1. 修改Grafana配置文件 在Grafana的配置文件 /etc/grafana/grafana.ini 中&#xff0c;找到 [auth.anonymous] 配…
阅读更多...
网络编辑day4

网络编辑day4

思维导图 广播模型发送端-->类似于UDP客户端 #include<head.h> int main(int argc, const char *argv[]) {//1、创建套接字int sfdsocket(AF_INET,SOCK_DGRAM,0);if(sfd-1){perror("socket error ");return -1;}//2、将套接字设置成允许广播int broadcast1…
阅读更多...
【SpringCloud】微服务框架后端部署详细过程记录20240119

【SpringCloud】微服务框架后端部署详细过程记录20240119

前言&#xff1a;前两天公司接到客户提供的一个微服务框架&#xff0c;导师让我在本地部署验证一下该框架的可用性&#xff0c;借此机会记录一下微服务项目的一个基本部署流程&#xff0c;仅供学习参考&#xff0c;如有不足还请指正&#xff01; 文件结构 提供的压缩文件共包含…
阅读更多...
【lettuce-排行榜】

【lettuce-排行榜】

背景&#xff1a; 这次游戏中台采用lettuce的zset完成游戏内的本服和跨服排行榜&#xff0c;因此写一下案例。 pom.xml <dependency><groupId>io.lettuce</groupId><artifactId>lettuce-core</artifactId><version>6.2.4.RELEASE</ve…
阅读更多...
Android14之DefaultKeyedVector实现(一百八十二)

Android14之DefaultKeyedVector实现(一百八十二)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…
阅读更多...
python之粘包/粘包的解决方案

python之粘包/粘包的解决方案

python之粘包/粘包的解决方案 什么是粘包 粘包就是在数据传输过程中有多个数据包被粘连在一起被发送或接受 服务端&#xff1a; import socket import struct# 创建Socket Socket socket.socket(socket.AF_INET, socket.SOCK_STREAM)# 绑定服务器和端口号 servers_addr (…
阅读更多...
LeetCode 热题 100 | 双指针（上）

LeetCode 热题 100 | 双指针（上）

目录 1 283. 移动零 2 11. 盛最多水的容器 3 15. 三数之和 菜鸟做题第一周&#xff0c;语言是 C 1 283. 移动零 解题思路&#xff1a; 两个指针一前一后遍历数组前者永远指向 0&#xff0c;后者永远在寻找非 0 数的路上后者找到一个非 0 数就和前者进行一个数值交换 …
阅读更多...
Python爬虫从入门到入狱系列合集

Python爬虫从入门到入狱系列合集

我 的 个 人 主 页&#xff1a;&#x1f449;&#x1f449; 失心疯的个人主页 &#x1f448;&#x1f448; 入 门 教 程 推 荐 &#xff1a;&#x1f449;&#x1f449; Python零基础入门教程合集 &#x1f448;&#x1f448; 虚 拟 环 境 搭 建 &#xff1a;&#x1f449;&…
阅读更多...
linux下USB抓包和分析流程

linux下USB抓包和分析流程

linux下USB抓包和分析流程 在windows下抓取usb包时可以通过wireshark安装时安装USBpcap来实现usb抓包&#xff0c;linux下如何操作呢&#xff1f; 是基于usbmon&#xff0c;本博客简单描述基于usbmon在linux系统上对通过usb口进行发送和接收的数据的抓包流程&#xff0c;分别描…
阅读更多...
Unity SnapScrollRect 滚动 匹配 列表 整页

Unity SnapScrollRect 滚动 匹配 列表 整页

展示效果 原理: 当停止滑动时 判断Contet的horizontalNormalizedPosition 与子Item的缓存值 相减,并得到最小值&#xff0c;然后将Content horizontalNormalizedPosition滚动过去 使用方式&#xff1a; 直接将脚本挂到ScrollRect上 注意&#xff1a;在创建Content子物体时…
阅读更多...
Python初学者须知（10）初识条件判断

Python初学者须知（10）初识条件判断

本系列博客主要针对的是Python初学者。Python语言简洁、强大的特性吸引了越来越多的技术人员将他们的项目转移到Python上。目前&#xff0c;Python已经成为计算机行业最流行的编程语言之一。笔者考虑到Python初学者的多元化&#xff08;Python学习者可能是对编程感兴趣的中学生…
阅读更多...
[小程序]API、数据与事件

[小程序]API、数据与事件

一、API ①事件监听API 以on开头&#xff0c;用来监听事件的触发&#xff08;如wx.inWindowResize&#xff09; ②同步API 以Sync结尾&#xff0c;且可以通过函数返回值获取&#xff0c;执行错误会抛出异常&#xff08;如wx.setStorageSync&#xff09; ③异步API 类似网页中的…
阅读更多...
记录一个sql:查询商品码对应多个商品的商品码

记录一个sql:查询商品码对应多个商品的商品码

目录 背景sql 语句总结 背景 一个项目中&#xff0c;商品表和商品码表是一对多的关系&#xff0c;但由于程序没有控制好&#xff0c;导致有些商品码对应有多个商品&#xff0c;为了修正数据&#xff0c;我们得把商品码对应多个商品的商品码找出来. sql 语句 goods_detail表结构…
阅读更多...
【Spring 篇】MyBatis中的CRUD魔法：数据之美的四重奏

【Spring 篇】MyBatis中的CRUD魔法：数据之美的四重奏

MyBatis&#xff0c;这个数据持久化的魔法师&#xff0c;以其优雅的SQL映射和简洁的配置文件&#xff0c;为我们呈现出一场CRUD&#xff08;Create, Read, Update, Delete&#xff09;的奇妙之旅。在这篇博客中&#xff0c;我们将深入探讨MyBatis中的增、删、改、查操作&#x…
阅读更多...
回归预测 | Matlab基于OOA-SVR鱼鹰算法优化支持向量机的数据多输入单输出回归预测

回归预测 | Matlab基于OOA-SVR鱼鹰算法优化支持向量机的数据多输入单输出回归预测

回归预测 | Matlab基于OOA-SVR鱼鹰算法优化支持向量机的数据多输入单输出回归预测 目录 回归预测 | Matlab基于OOA-SVR鱼鹰算法优化支持向量机的数据多输入单输出回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab基于OOA-SVR鱼鹰算法优化支持向量机的数据…
阅读更多...
最新文章

Copyright @ 2022~2023