【C++打怪之路Lv11】-- stack、queue和优先级队列

🌈 个人主页:白子寰
🔥 分类专栏:重生之我在学Linux,C++打怪之路,python从入门到精通,数据结构,C语言,C语言题集👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+),分享更多关于深度学习、C/C++,python领域的优质内容!(希望得到您的关注~)

目录

C++为什么要学习stack、queue和优先级队列

stack类

stack类的介绍

stack的基本操作

stack的模拟实现

 queue类

queue类的介绍

queue的基本操作

queue的模拟实现

 优先级队列

优先级队列的介绍

仿函数 

什么是仿函数 

为什么要有仿函数 

优先级队列的使用

成员函数

 排序准则

优先级队列的模拟实现

关于容器适配器


C++为什么要学习stack、queue和优先级队列

学习C++中的栈(stack)、队列(queue)和优先级队列(priority queue)对开发者来说非常重要,因为它们是常用的数据结构,在解决各种编程问题时提供了高效的方法。

以下是它们的核心作用和特点:

1. 栈(Stack)
   特点后进先出(LIFO),即最后入栈的元素最先出栈。
   应用:适用于函数调用、表达式求值、撤销操作等场景。例如,程序在执行递归调用时会用栈来存储函数状态。

2. 队列(Queue)
   特点先进先出(FIFO),即最先进入队列的元素最先被处理。
   应用:适用于任务调度、消息处理、广度优先搜索等需要按顺序处理数据的场景。

3. 优先级队列(Priority Queue):
   特点:元素按优先级排序,每次取出的是优先级最高的元素,而不是按插入顺序。
   应用:适用于任务管理(例如操作系统中的任务调度)、最短路径算法(如Dijkstra算法)、数据流中找出Top K元素等场景。

这些数据结构在C++中有标准库支持(如`<stack>`、`<queue>`和`<priority_queue>`),可以帮助开发者更高效地处理特定类型的问题,提高程序的可读性和性能。


stack类

stack类的介绍

stack 是 C++ 标准模板库(STL)中的一个容器适配器,用于实现后进先出(LIFO)数据结构。

基于其他序列容器(如 dequevectorlist)构建,默认使用 deque 作为底层容

stack<int, vector<int>> st;

注:

1、定义了一个名为 st 的栈(stack)

其中包含 int 类型的元素,并使用 vector<int> 作为其底层容器

2、stack 默认使用 deque 作为底层容器,但可以通过这种方式替换成其他容器

3、特点 & 好处

  • 该栈 st 仍然保持 stack 的 后进先出 特性。
  • 使用 vector 作为底层容器意味着栈的元素实际上存储在一个 vector 中,但只能通过 stack 提供的接口(如 push()pop()top() 等)访问。

这样做的优势在于,如果对底层容器的特性(如内存管理或其他特定操作)有特殊需求,可以灵活选择适合的容器


stack的基本操作

  • push()将元素压入栈顶
  • pop()移除栈顶元素
  • top():返回栈顶元素的引用只能访问栈顶元素(通过 top()),无法直接访问其他位置的元素
  • empty():判断栈是否为空
  • size():返回栈中元素的个数


stack的模拟实现

namespace sky
{template<class T, class Container = vector<int>>class Stack{public:void push(const T& val){_con.push_back(val);	// 压栈插入数据}void pop(){_con.pop_back();		// 删除用尾删}const T& top(){return _con.back();		// 后进先出}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}int main()
{sky::Stack<int,vector<int>>	st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout << st.size() << endl;while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;return 0;
}


 queue类

queue类的介绍

1、queue 是标准库容器适配器,用于实现先进先出(FIFO)队列。

它基于底层容器(如 dequelist)进行封装

2、默认使用 deque 作为存储容器,也可以指定其他符合双端操作要求的容器。

queue 适用于需要按顺序处理数据的场景,如任务调度或广度优先搜索等


queue的基本操作

  • push():向队尾添加元素
  • pop()移除队头元素
  • front():返回队头元素的引用
  • back():返回队尾元素的引用
  • empty()检查队列是否为空
  • size():返回队列中元素的数量

 


queue的模拟实现

namespace sky
{template<class T, class Container = list<int>>class Queue{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}T& front(){return _con.front();}T& back(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}int main()
{sky::Queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << q.back() << endl;cout << q.size() << endl;while (!q.empty()){cout << q.front() << " ";q.pop();} return 0;
}


 优先级队列

优先级队列的介绍

priority_queue 是标准库容器适配器,用于实现优先级队列,其元素根据优先级自动排序。默认情况下,它使用最大堆结构,使得队头元素总是优先级最高的元素

priority_queue 适用于需要动态维护最大(或最小)元素的场景,如任务调度、路径规划等

注:需要包头文件<queue>


仿函数 

什么是仿函数 

priority_queue的函数原型比queuestack多了一个参数,用于指定比较函数,这个参数决定了元素在priority_queue中的排序方式

比较函数(仿函数)priority_queue需要一个比较函数(通常是仿函数)来定义元素之间的优先级顺序。默认情况下,它使用std::less<T>,这意味着它将按照从小到大的顺序排列,形成一个最大堆

这是priority_queuequeuestack最显著的区别,因为priority_queue需要根据元素的优先级来组织数据,而queuestack仅需要遵循基本的先进先出或后进先出原则


为什么要有仿函数 

  • 自定义比较逻辑:优先级队列默认情况下是一个最大堆,即最大的元素具有最高的优先级。但有时我们可能需要根据不同的标准来排序元素,比如最小堆或者基于对象的某个成员函数。通过使用仿函数,我们可以自定义比较逻辑,使得优先级队列能够按照我们期望的顺序排列元素。
  • 状态保持:仿函数可以保持状态,这意味着它们可以在调用之间保留信息,这在某些复杂的比较逻辑中非常有用。
  • 类型安全:使用仿函数可以保证类型安全,因为编译器会在编译时检查传递给仿函数的参数类型是否正确。

优先级队列的使用

成员函数

  • push()插入元素,并自动调整位置
  • pop()移除优先级最高的元素(队头)
  • top()访问优先级最高的元素
  • empty():检查队列是否为空。
  • size():返回元素的数量

 排序准则

默认使用 std::less(大顶堆),可以通过自定义比较函数来实现小顶堆或其他排序


优先级队列的模拟实现

namespace sky
{template<class T>class less{public:bool operator()(const T& x, const T& y){// 在构建堆时,x < y 的意思是:如果 x 比 y 小,// 那么 x 的优先级低于 y,所以 y 应该排在 x 前面return x < y;}};template<class T>class greater{public:// 当使用 greater 作为比较器时,较小的元素会排在前面,因此可以创建一个"最小优先队列"bool operator()(const T& x, const T& y){return x > y;}};template<class T, class Container = vector<int>, class Compare = less<T>>class priority_queue{public:void adjust_up(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;}}}void adjust_down(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 push(const T& val){_con.push_back(val);adjust_up(_con.size() - 1);}// 删除堆顶元素并调整堆void pop(){if (!_con.empty()){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}int main()
{sky::priority_queue<int> pq;pq.push(3);pq.push(1);pq.push(5);pq.push(4);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

关于容器适配器


***********************************************************分割线*****************************************************************************
完结!!!
感谢浏览和阅读。

等等等等一下,分享最近喜欢的一句话:

“把自己活出一道光”。

我是白子寰,如果你喜欢我的作品,不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力!!! 
好了划走吧。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RabbitMQ进阶_可靠性

文章目录 一、 发送者的可靠性1.1、 生产者重试机制1.2、 生产者确认机制1.2.1、确认机制理论1.2.2、确认机制实现1.2.2.1、定义ReturnCallback1.2.2.2、定义ConfirmCallback 二、 MQ的可靠性2.1、 数据持久化2.1.1、 交换机持久化2.1.2、 队列持久化2.1.3、 消息持久化 2.2、 …

《使用Gin框架构建分布式应用》阅读笔记:p88-p100

《用Gin框架构建分布式应用》学习第6天&#xff0c;p88-p100总结&#xff0c;总计13页。 一、技术总结 1.MongoDB CRUD操作 (1)InsertOne(), InsertMany() (2)Find() (3)UpdateOne, UpdateMany() (4)DeleteOne(), DeleteMany() 2.MongoDB primitive p96&#xff0c;rec…

记录:网鼎杯2024赛前热身WEB01

目录扫描&#xff0c;发现上传点&#xff0c;判断可能存在文件上传漏洞&#xff0c;并根据文件后缀判断网站开发语言为php 编写蚁剑一句话木马直接上传 蚁剑连接 这里生成 的flag是随机的&#xff0c;因为烽火台反作弊会随机生成环境&#xff0c;在一顿查找后&#xff0c;在hom…

复旦大学全球供应链研究中心揭牌,合合信息共话大数据赋能

10月13日&#xff0c;复旦大学全球供应链研究中心&#xff08;以下简称“中心”&#xff09;揭牌仪式在复旦大学管理学院政立院区隆重举行。我国的供应链体系庞大复杂&#xff0c;在百年未有之大变局下&#xff0c;保障产业链供应链安全已成为我国的重要战略目标。中心的设立旨…

九、pico+Unity交互开发——触碰抓取

一、VR交互的类型 Hover&#xff08;悬停&#xff09; 定义&#xff1a;发起交互的对象停留在可交互对象的交互区域。例如&#xff0c;当手触摸到物品表面&#xff08;可交互区域&#xff09;时&#xff0c;视为触发了Hover。 Grab&#xff08;抓取&#xff09; 概念&#xff…

张雪峰:如果你现在是计算机专业,一定要优先报网络安全,它是未来国家发展的大方向

&#x1f91f; 基于入门网络安全/黑客打造的&#xff1a;&#x1f449;黑客&网络安全入门&进阶学习资源包 前言 “计算机专业 一定要优先报 网络安全 它是未来国家发展的大方向” 为什么推荐学网络安全&#xff1f; “没有网络安全就没有国家安全。”当前&#xff…

优化UVM环境(九)-将interface文件放在env pkg外面

书接上回&#xff1a; 优化UVM环境&#xff08;八&#xff09;-整理project_common_pkg文件 My_env_pkg.sv里不能包含interface&#xff0c;需要将my_intf.sv文件放在pkg之外

使用飞桨AI Studio平台训练数据,并进行图像识别分析得牡丹花测试

&#x1f3bc;个人主页&#xff1a;【Y小夜】 &#x1f60e;作者简介&#xff1a;一位双非学校的大二学生&#xff0c;编程爱好者&#xff0c; 专注于基础和实战分享&#xff0c;欢迎私信咨询&#xff01; &#x1f386;入门专栏&#xff1a;&#x1f387;【MySQL&#xff0…

【Qt】控件——Qt多元素控件、常见的多元素控件、多元素控件的使用、List Widget、Table Widget、Tree Widget

文章目录 QtQt多元素控件List WidgetTable WidgetTree Widget Qt Qt多元素控件 List Widget 使用 QListWidget 能够显示一个纵向的列表。 属性说明currentRow当前被选中的是第几行。count一共有多少行。sortingEnabled是否允许排序。isWrapping是否允许换行。itemAlignment元素…

【vue 封装一个select组件】封装一个select组件,包括select样式的修改,以及解决select,onchange事件失效问题

实现效果:封装一个下拉菜单组件,效果如下图 父组件代码如下: 子组件代码: <template><div><form><select name="languages" id="lang" ><option :value="item.value" v-for="item in optionList" >…

【火山引擎】语音合成 | HTTP接口 | 一次性合成 | python

目录 一 准备工作 二 HTTP接口(一次性合成-非流式) 1 接口说明 2 身份认证 3 请求方式 三 实践 四 注意事项 火山引擎语音合成TTS(Text-to-Speech)是一种基于云计算的语音合成服务,可以将文本转化为自然、流畅的语音。以下是火山引擎TTS的主要功能和特点: ①多种语音…

CMOS 图像传感器:像素寻址与信号处理

CMOS image sensor : pixel addressing and signal processing CMOS image sensor 对于寻址和信号处理有三种架构 pixel serial readout and processingcolumn parallel readout and processingpixel parallel readout and processing 其中&#xff0c;column parallel reado…

kebuadm部署k8s集群

官方文档&#xff1a; Installing kubeadm | Kubernetes 切记要关闭防⽕墙、selinux、禁用交换空间&#xff0c; cpu核⼼数⾄少为2 内存4G kubeadm部署k8s⾼可用集群的官方文档&#xff1a; Creating Highly Available Clusters with kubeadm | Kubernetes 你需要在每台…

Docker 安装Postgres和PostGIS,并制作镜像

1. 查找postgres和postgis现有的镜像和版本号 镜像搜索网站&#xff1a;https://docker.aityp.com/ 测试使用的是postgres:15.4 和 postgis:15-3.4 2、镜像拉取 docker pull postgres:15.4docker pull postgis/postgis:15-3.4镜像下载完成&#xff0c;docker images 查看如…

konvajs -基础图形-标签-箭头,动画,学习笔记

官网&#xff1a; Konva 框架概述 |Konva - JavaScript 2d 画布 图书馆 (konvajs.org)https://konvajs.org/docs/overview.html konva是canvas的一个库&#xff0c;可快速画出想要的图形。 基础创建步骤&#xff1a; // 第一步&#xff0c;创建一个Stage舞台 var stage new…

element设置时间和日期框早于现在的时间和日期禁用

效果: 今日此时此刻之前的日期、时间禁止选用&#xff0c;切换日期和时间为“2024-10-19 00:00:00"&#xff0c;再切换为”2024-10-18 00:00:00"时&#xff0c; 会给form.time默认赋值为今日此时此刻&#xff08;日期时间少于今日此时此刻则重新赋值&#xff09; 安…

Go语言基础学习(Go安装配置、基础语法)

一、简介及安装教程 1、为什么学习Go&#xff1f; 简单好记的关键词和语法&#xff1b;更高的效率&#xff1b;生态强大&#xff1b;语法检查严格&#xff0c;安全性高&#xff1b;严格的依赖管理&#xff0c; go mod 命令&#xff1b;强大的编译检查、严格的编码规范和完整的…

【优选算法】探索双指针之美(一):双指针与单调性的完美邂逅

文章目录 前言&#xff1a;1.盛水最多的容器2.有效三角形个数3. 和为s的两个数字4. 三数之和5. 四数之和 最后想说&#xff1a; 前言&#xff1a; 在上一章中我们已经认识到了双指针&#xff0c;在这章里我们就来探索一下当双指针和单调性遇见后会擦出怎样的火花呢&#xff1f…

几何算法系列:空间实体体积计算公式推导

1.前言 面积和体积的计算是常见和基础的几何算法话题&#xff0c;面积和体积通常作为面或构件的基本信息参与相关的建模、计算、分析等过程。 有关面积的计算&#xff0c;可以参考博主此前的文章&#xff0c; 一种误差较小的轮廓面积计算算法_轮廓面积计算原理-CSDN博客文章…

深入理解Qt中的QTableView、Model与Delegate机制

文章目录 显示效果QTableViewModel(模型)Delegate(委托)ITEM控件主函数调用项目下载在Qt中,视图(View)、模型(Model)和委托(Delegate)机制是一种非常强大的架构,它们实现了MVC(模型-视图-控制器)设计模式。这种架构分离了数据存储(模型)、数据展示(视图)和数据操作(委托),使…