C++ queue

目录

一、介绍

二、queue使用

三、模拟实现

四、优先级队列

五、priority_queue使用

OJ题:215. 数组中的第K个最大元素

快速排序

优先级队列

TOPK

六、模拟实现priority_queue

1、仿函数

2、优先级队列类

3、测试函数


一、介绍

1、队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
2、队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。
3、底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push:在队列尾部入队列
  • pop:在队列头部出队列
4、标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

二、queue使用

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    // 检测队列是否为空
    if (myQueue.empty()) {
        std::cout << "队列为空" << std::endl;
    }
    else {
        std::cout << "队列不为空" << std::endl;
    }

    // 入队列
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    // 返回队列中有效元素的个数
    std::cout << "队列中的元素个数:" << myQueue.size() << std::endl;

    // 返回队头元素的引用
    std::cout << "队头元素:" << myQueue.front() << std::endl;

    // 返回队尾元素的引用
    std::cout << "队尾元素:" << myQueue.back() << std::endl;

    // 出队列
    myQueue.pop();

    // 返回队头元素的引用
    std::cout << "出队后的队头元素:" << myQueue.front() << std::endl;

    return 0;
}

三、模拟实现

namespace byte
{
	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> q;
		q.push(1);
		q.push(2);
		q.push(3);
		q.push(4);

		while (!q.empty())
		{
			cout << q.front() << " ";
			q.pop();
		}
		cout << endl;
	}
}

四、优先级队列

1、优先级队列是一种容器适配器,根据一些严格的弱排序标准,经过专门设计,其第一个元素始终是它所包含的最大元素。

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

3、优先级队列作为容器适配器实现,容器适配器是使用特定容器类的封装对象作为其基础容器的类,提供一组特定的成员函数来访问其元素。元素从特定容器的“背面”弹出,这称为优先级队列的顶部。

4、基础容器可以是任何标准容器类模板,也可以是一些其他专门设计的容器类。容器应可通过随机访问迭代器访问,并支持以下操作:
  • empty():检测容器是否为空
  • size():返回容器中有效元素个数
  • front():返回容器中第一个元素的引用
  • push_back():在容器尾部插入元素
  • pop_back():删除容器尾部元素
5、标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。

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

五、priority_queue使用

  • priority_queue()/priority_queue(first, last) 构造一个空的优先级队列

  • empty( ) 检测优先级队列是否为空,是返回true,否则返回 false

  • top( ) 返回优先级队列中最大(最小元素),即堆顶元素

  • push(x) 在优先级队列中插入元素x
  • pop() 删除优先级队列中最大(最小)元素,即堆顶元素
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 构造一个空的优先级队列
    priority_queue<int> pq;

    // 检测优先级队列是否为空
    if (pq.empty()) {
        cout << "优先级队列为空" << endl;
    } else {
        cout << "优先级队列不为空" << endl;
    }

    // 使用迭代器范围构造优先级队列
    vector<int> nums = {3, 1, 4, 1, 5, 9};
    priority_queue<int> pq2(nums.begin(), nums.end());

    // 输出堆顶元素
    cout << "堆顶元素为: " << pq2.top() << endl;

    // 在优先级队列中插入元素
    pq2.push(2);
    pq2.push(7);

    // 输出堆顶元素
    cout << "堆顶元素为: " << pq2.top() << endl;

    // 删除堆顶元素
    pq2.pop();

    // 输出堆顶元素
    cout << "堆顶元素为: " << pq2.top() << endl;

    return 0;
}


OJ题:215. 数组中的第K个最大元素

快速排序

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

这个解法使用了 C++ 的标准库函数 sort 对数组进行排序,然后返回倒数第 k 个元素。通过将数组排序,我们可以确保最大的元素位于数组的末尾,倒数第二大的元素位于倒数第二个位置,以此类推。因此,返回 nums[nums.size() - k] 即可得到第 k 大的元素。这种方法的时间复杂度为 O(nlogn),其中 n 是数组的长度。

优先级队列

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(),nums.end());
        while(--k){
            pq.pop();
        }
        return pq.top();
    }
};

这个解法使用了优先队列(priority_queue),它是一个基于堆实现的数据结构,可以自动维护最大(或最小)元素位于队列的顶部。首先,将整个数组构建成一个优先队列 pq,其中元素按照从大到小的顺序排列。然后,通过多次调用 pq.pop() 将队列中的前 k-1 个元素弹出,最后返回队列顶部的元素,即第 k 大的元素。这种方法的时间复杂度为 O(nlogn),空间复杂度为 O(n),其中 n 是数组的长度。

TOPK

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);
        for(size_t i=k;i<nums.size();i++){
            if(nums[i]>pq.top()){
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};
这个解法也使用了优先队列,但是与解法二不同的是,这里构建的是一个最小堆。首先,将数组的前 k 个元素构建成一个最小堆 pq。然后,从第 k+1 个元素开始遍历数组,如果当前元素大于最小堆的堆顶元素(即当前第 k 大的元素),则将堆顶元素弹出,将当前元素插入堆中。最后,返回最小堆的堆顶元素,即第 k 大的元素。这种方法的时间复杂度为 O(nlogk),空间复杂度为 O(k),其中 n 是数组的长度,k为最小堆的大小。

六、模拟实现priority_queue

1、仿函数

 在C++中,仿函数(Functor)是一种重载了函数调用操作符 operator() 的对象。它实际上是一个类或者结构体,通过重载 operator(),使得该对象可以像函数一样被调用。仿函数可以像函数一样接受参数,并返回结果,同时可以包含状态信息,因此它们在C++中被广泛用于实现函数对象,作为算法的参数传递,或者用于定义自定义的操作。

#pragma once
#include <vector>
using namespace std;

namespace hhh
{
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

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

使用仿函数的好处是可以将特定的操作封装为一个对象,使得代码更加灵活和可扩展。通过重载函数调用操作符,可以将对象当作函数来使用,这样可以方便地在算法或数据结构中使用。在这个实现中,less 和 greater 结构体被用作仿函数,用于定义元素的比较方式。less 结构体表示小的元素优先级高,greater 结构体表示大的元素优先级高。

2、优先级队列类

	template<class T, class Container = vector<T>,class Compare=less<T>>
	class priority_queue 
    {
	private:
		Container _con;
    
    public:
		void adjust_up(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0){
				if(com(_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()) {
				Compare com;

				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);
		}

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

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

		bool empty()
		{
			return _con.empty();
		}
    };
}
  1. priority_queue 类:这是一个模板类,可以用于任何类型的元素。它有三个模板参数,T 是元素的类型,Container 是用于存储元素的容器类型,默认是 vectorCompare 是元素的比较方式,默认是 less

  2. adjust_up 函数:这个函数用于调整堆的结构,使得父节点的值大于或小于所有子节点的值。它的参数是一个子节点的索引,它会不断地将这个节点和它的父节点进行比较,如果父节点的值小于子节点的值,就交换这两个节点。

  3. adjust_down 函数:这个函数也是用于调整堆的结构,它的参数是一个父节点的索引,它会不断地将这个节点和它的子节点进行比较,如果父节点的值小于任何一个子节点的值,就交换这两个节点。

  4. push 函数:这个函数用于向优先级队列中添加一个元素。它首先将元素添加到向量的末尾,然后调用 adjust_up 函数来调整堆的结构。

  5. pop 函数:这个函数用于从优先级队列中删除最大或最小的元素。它首先交换向量的第一个元素和最后一个元素,然后删除最后一个元素,最后调用 adjust_down 函数来调整堆的结构。

  6. top 函数:这个函数用于获取优先级队列中最大或最小的元素。

  7. size 和 empty 函数:这两个函数用于获取优先级队列中元素的数量和判断优先级队列是否为空。

3、测试函数

void test_priority_queue()
{

	// 默认是大堆
	priority_queue<int> pq;

	// 小堆
	//priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(1);
	pq.push(0);
	pq.push(5);
	pq.push(2);
	pq.push(1);
	pq.push(7);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

大堆:


小堆:

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

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

相关文章

SpringSecurity深度学习

SpringSecurity简介 spring Security是什么&#xff1f; Spring Security 是一个强大且高度可定制的身份验证和访问控制框架&#xff0c;用于保护基于Spring的应用程序。它是Spring项目的一部分&#xff0c;旨在为企业级系统提供全面的安全性解决方案。 一个简单的授权和校验…

I/O流基础

1.输入/输出流 流是一组有序的数据序列&#xff0c;根据操作的类型&#xff0c;可以分为输入流和输出流两种。 Java定义的输入输出类被放在java.io包中 所有的输入流类都是抽象类InputStream&#xff08;字节输入流&#xff09;或抽象类Reader&#xff08;字符输入流&#xff…

Linux系统性能优化:七个实战经验

Linux系统的性能是指操作系统完成任务的有效性、稳定性和响应速度。Linux系统管理员可能经常会遇到系统不稳定、响应速度慢等问题&#xff0c;例如在Linux上搭建了一个web服务&#xff0c;经常出现网页无法打开、打开速度慢等现象&#xff0c;而遇到这些问题&#xff0c;就有人…

Unity中Shader的_Time精度问题

文章目录 前言一、U方向上优化二、V方向上优化在这里插入图片描述 三、最终代码1、效果2、Shader 前言 在Unity的Shader中&#xff0c;使用了_Time来达到UV的流动效果&#xff0c;普遍会出现一个问题。我们的UV值会随着时间一直增加&#xff08;uv值增加了&#xff0c;但是因为…

web学习笔记(十一)

目录 1.数据类型 1.1数据类型分类 &#xff08;1&#xff09;简单&#xff08;基本&#xff09;数据类型 &#xff08;2&#xff09;复杂&#xff08;特殊&#xff09;数据类型 1.2判断数据类型的方法 &#xff08;1&#xff09;常规判断方法&#xff1a; &#xff08;2…

用判断对齐大语言模型

1、写作动机&#xff1a; 目前的从反馈中学习方法仅仅使用判断来促使LLMs产生更好的响应&#xff0c;然后将其作为新的示范用于监督训练。这种对判断的间接利用受到无法从错误中学习的限制&#xff0c;这是从反馈中学习的核心精神&#xff0c;并受到LLMs的改进能力的制约。 2…

html5实现好看的个人博客模板源码

文章目录 1.设计来源1.1 主界面1.2 认识我界面1.3 我的文章界面1.4 我的模板界面1.5 文章内容界面 2.结构和源码2.1 目录结构2.2 源代码 源码下载 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/135368653 html5实现好看…

rust sqlx包(数据库相关)使用方法+问题解决

可以操作pgsql、mysql、mssql、sqlite 异步的&#xff0c;性能应该不错&#xff0c;具体使用有几个坑 除了sqlx库&#xff0c;还有对于具体数据库的库&#xff0c;比如postgres库 演示以pgsql为例&#xff0c;更新时间2024.1.6 官方github: sqlx github rust官方文档&#xff1…

c语言结构体学习

文章目录 前言一、结构体的声明1&#xff0c;什么叫结构体?2&#xff0c;结构体的类型3,结构体变量的创建和初始化4&#xff0c;结构体的类型5&#xff0c;结构体的初始化 二、结构体的访问1&#xff0c;结构体成员的点操作符访问2&#xff0c;结构体体成员的指针访问 三、结构…

网络连接 UDP2,UDP Connect, bind, send, recieve认知, -入门8

LWIP编程接口有RAW, NETCONN, SOCKET 2.UDP函数的理解 #define UDP_SERVER_PORT 8000 //PC side #define UDP_CLIENT_PORT 1234 // ctrl board side //PC IP address #define DEST_IP_ADDR0 192 #define DEST_IP_ADDR1 168 #define DEST_IP_ADDR2 3 #define DEST_IP_ADDR3 11…

如何安装和使用夜神模拟器连接Android Studio

目录 简介 一、安装 二、使用 三、更多资源 简介 夜神模拟器是一款在Windows平台上运行的Android模拟器软件。它能够模拟Android操作系统环境&#xff0c;让用户在电脑上轻松体验Android应用程序。夜神模拟器的功能强大&#xff0c;可以满足各种需求&#xff0c;无论是娱乐…

实现pytorch版的mobileNetV1

mobileNet具体细节&#xff0c;在前面已做了分析记录&#xff1a;轻量化网络-MobileNet系列-CSDN博客 这里是根据网络结构&#xff0c;搭建模型&#xff0c;用于图像分类任务。 1. 网络结构和基本组件 2. 搭建组件 &#xff08;1&#xff09;普通的卷积组件&#xff1a;CBL …

大模型学习第一课

学习目标&#xff1a; 大模型开源体系 学习内容&#xff1a; 大模型简述大模型性能开源体系 学习时间&#xff1a; 周四上午 10点 学习记录&#xff1a; 大模型简述 大模型是发展通用人工智能的重要途经专用模型到通用大模型实验室开源历程&#xff0c;大模型系列7B-20B-12…

k8s实践(14)--scheduler调度器和pod调度策略

一、scheduler调度器 1、kube-scheduler简介 k8s实践(10) -- Kubernetes集群运行原理详解 介绍过kube-scheduler。 kube-scheduler是运行在master节点上&#xff0c;其主要作用是负责资源的调度&#xff08;Pod调度&#xff09;&#xff0c;通过API Server的Watch接口监听新建…

C++中的new和delete

相关文章 C智能指针 文章目录 相关文章前言一、new 运算符1. operator new 函数的范围2. 在类中重载new运算符3. 分配失败 二、delete 运算符1. 内存泄露统计示例2. 在类中重载delete运算符 总结 前言 在C中&#xff0c;new和delete是用于动态内存管理的运算符&#xff0c;它们…

Halcon计算一个区域的最大内接圆 inner_circle

Halcon计算一个区域的最大内接圆 该算子用于计算一个区域的最大内接圆&#xff0c;其原型如下&#xff1a; inner_circle(Regions : :: Row, Column, Radius)参数1&#xff1a;Regions 表示输入的区域。 参数2和3&#xff1a;Row、Column为输出参数&#xff0c;表示最大内接圆…

面试经典题---6.Z字形变换

6.Z字形变换 我的解法&#xff1a; 首先定义了3个变量&#xff1a;index、add和step。 index&#xff1a;当前处理字符在原字符串中的下标&#xff1b;add&#xff1a;Z字形中相邻两个字符在原字符串中的下标之差&#xff08;非固定值&#xff0c;值随着行的改变会发生变化&am…

Linux 上 Nginx 配置访问 web 服务器及配置 https 访问配置过程记录

目录 一、前言说明二、配置思路三、开始修改配置四、结尾 一、前言说明 最近自己搭建了个 Blog 网站&#xff0c;想把网站部署到服务器上面&#xff0c;本文记录一下搭建过程中 Nginx 配置请求转发的过程。 二、配置思路 web项目已经在服务器上面运行起来了&#xff0c;运行的端…

EtherCAT主站SOEM -- 13 --Qt-Soem通过界面按键控制 EtherCAT IO模块的io输出

EtherCAT主站SOEM -- 13 --Qt-Soem通过界面按键控制 EtherCAT IO模块的io输出 一 mainwindow.c 文件函数:1.1 自定义PDO配置2.2 主站初始化2.3 去motrorcontrol界面二 motrorcontrol.c 文件三 allvalue.h 文件该文档修改记录:总结一 mainwindow.c 文件函数: mainwindow主界…

性能分析与调优: Linux 性能分析60秒

目录 一、实验 1.环境 2.Linux性能分析60秒 一、实验 1.环境 &#xff08;1&#xff09;主机 表1-1 主机 主机架构组件IP备注prometheus 监测 系统 prometheus、node_exporter 192.168.204.18grafana监测GUIgrafana192.168.204.19agent 监测 主机 node_exporter192.168…