C++ queue&priority_queue

这篇具有很好参考价值的文章主要介绍了C++ queue&priority_queue。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、介绍

二、queue使用

三、模拟实现

四、优先级队列

五、priority_queue使用

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

快速排序

优先级队列

TOPK

六、模拟实现priority_queue

1、仿函数

2、优先级队列类

3、测试函数


一、介绍

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

二、queue使用

函数声明

          接口说明

queue()

    构造空的队列

empty()

 检测队列是否为空,是返回true,否则返回false

size()

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

front()

    返回队头元素的引用

back()

    返回队尾元素的引用

push()

 在队尾将元素val入队列

pop()

    将队头元素出队列

#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;
}
C++ queue&priority_queue,C++,c++,开发语言

三、模拟实现

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

C++ queue&priority_queue,C++,c++,开发语言

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

大堆:

C++ queue&priority_queue,C++,c++,开发语言
小堆:

C++ queue&priority_queue,C++,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-788895.html

到了这里,关于C++ queue&priority_queue的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 优先队列 priority_queue 使用篇

    目录 1.储备知识    (1)数据结构:堆   (2)仿函数(函数对象)     [1]理解仿函数     [2]实现仿函数   (3)priority_queue理解     [1]什么是priority_queue (优先队列)?     [2]优先队列性质 2.priority_queue的参数理解(重要!!!)   (1)priority_queue的参数     [1]priority_queue类模板参数     [

    2024年03月12日
    浏览(81)
  • C++中的优先队列(priority_queue)

    什么是优先队列 优先队列(priority queue) 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有优先级最高先出的性质。通常采用堆数据结构来实现。

    2024年02月15日
    浏览(45)
  • 【C++】priority_queue使用与模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月16日
    浏览(42)
  • C++:模版进阶 | Priority_queue的模拟实现

                                                创作不易,感谢三连支持  模板参数分类为 类型形参与非类型形参 。 类型形参即:出现在模板参数列表中,跟在class或者typename之类的参数类型名称。 非类型形参,就是 用一个常量作为类(函数)模板的一个参数 ,在类(函数

    2024年03月12日
    浏览(42)
  • [C++]priority_queue的介绍及模拟实现

    目录 priority_queue的介绍及模拟实现::                                                         priority_queue的介绍                                                         priority_queue的定义方式                 

    2024年02月04日
    浏览(43)
  • 【C++】STL之priority_queue类源码剖析

    目录 概述 算法 源码 PriorityQueue.h test.cpp 测试结果 priority_queue:优先级队列,包含在头文件queue中 优先级队列类似于堆结构,优先级最高的元素被置为堆顶,最优先被弹出top()和删除pop() 优先级队列的默认调整策略是大根堆,也就是最大值在堆顶 自定义类型需要用户自己提供

    2024年02月02日
    浏览(39)
  • c++ priority_queue用法 入门必看 超详细

    priority_queue即优先级队列,它的使用场景很多,它底层是用大小根堆实现的,可以用log(n)的时间动态地维护数据的有序性。适用于许多场景,比如简化哈夫曼树算法、dijkstra算法等等 priority_queue是不允许随机访问,只能访问队列首部的元素,也只能对首部元素进行出队,下面进

    2024年02月12日
    浏览(35)
  • 【C++】容器适配器之priority_queue & 仿函数

    我们和学习之前的容器一样,可以使用cplusplus官网进行学习:priority_queue文档介绍 priority_queue(优先级队列)是一种容器适配器,它 和queue使用同一个头文件,其底层结构是一个堆,并且默认情况下是一个大根堆,此外,priority_queue也不支持迭代器,这是为了不破坏堆的结构使用

    2024年02月01日
    浏览(43)
  • 『C++ - STL』之优先级队列( priority_queue )

    什么是优先级队列,从该名中可以知道他一定有队列的一定属性,即先入先出(LILO),而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进行出队,这就是优先级队列; 而在数据结构中有一个支持该操作的结构 - 堆( heap ); 而在STL中,这个

    2024年02月07日
    浏览(42)
  • 【C++初阶】模拟实现优先级队列priority_queue

    👦个人主页:@Weraphael ✍🏻作者简介:目前学习C++和算法 ✈️专栏:C++航路 🐋 希望大家多多支持,咱一起进步!😁 如果文章对你有帮助的话 欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨ 优先级队列顾名思义就是 按优先级出队列 priority_queue 是一个容器适配器,默认使用

    2024年02月10日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包