优先队列----数据结构
概念
不知道你玩过英雄联盟吗?英雄联盟里面的防御塔会攻击离自己最近的小兵,但是如果有炮车兵在塔内,防御塔会优先攻击炮车(因为炮车的威胁性更大),只有没有兵线在塔内时,防御塔才会攻击英雄。所以你可以得出优先级:距离最近的炮车 > 炮车 > 距离最近的小兵 > 小兵 > 距离最近的英雄 > 英雄。

那什么是优先队列?首先它是一个队列,它的入队顺序没有发生改变,但是出队的顺序是根据优先级的高低来实现的,遍历队列,优先级高的先出队,有多个节点具有最高的优先级,选取遇到的第一个具有最高的优先级的节点。

空队列

插入一个元素

插入第二个元素

删除一个节点


上列情况是最普通的情况(无需多余的操作),显然如果删除的是队列中的最后一个节点,尾指针需要手动移动;如果删除的是队列中的第一个节点,头指针会自动移动。如果删除的队列只有一个节点,那头尾指针需要手动置空。所以总共有 2 种情况需要考虑。
队列的算法实现
队列的结构体定义
其中优先级的高低是自己定义的,你也可以令 0 为最高优先级,优先级数也不只有这 9 个。
#define MAX_SIZE 15
typedef int DateElem;typedef struct _QNode
{int priority; //节点的优先级,9为最高优先级,0为最低优先级,优先级相同的取第一个DateElem date;struct _QNode* next;
}QNode;typedef QNode* QueuePtr; //QueuePtr a; 就定义了一个指向结构体QNode的指针typedef struct _Queue
{int length; //队列长度QueuePtr head; //头指针QueuePtr tail; //尾指针
}Queue;
队列的初始化、判空、判满、插入
//队列的初始化,初始化为空队列
void initQueue(Queue* q)
{if (!q) //指向队头的指针为空{return;}q->head = NULL;q->tail = NULL;q->length = 0;
}//判断队列是否为空
bool IsEmpty(Queue* q)
{if (!q) return false;if (q->head == NULL) //条件用 q->tail == NULL 也行{return true;}return false; //不为空
}//判断队列是否为满
bool IsFull(Queue* q)
{if (!q) return false;if (q->length >= MAX_SIZE) //也可以用 q->length == MAX_SIZE{return true;}return false;
}//入队
bool enterQueue(Queue* q, DateElem e, int priority)
{if (!q || IsFull(q)){cout << "队列已满" << endl;return false;}QNode* p = new QNode;//if (!q) return false; 一般不会生成失败p->priority = priority;p->date = e;p->next = NULL;//插入有两种情况if (IsEmpty(q)) //空队列{q->head = p;q->tail = p;}else //队列中已有元素{q->tail->next = p; //队列中的最后一个节点的next指针指向新加节点q->tail = p; //更新尾指针}q->length++;return true;
}
出队
唯一与普通队列有较大差别的就是队列的出队,其他的操作变化很小。
//遍历队列
bool popQueue(Queue* q,DateElem *out)
{if (!q || IsEmpty(q)){cout << "队列为空" << endl;return false;}if (!out){cout << "无法传递删除节点的值" << endl;return false;}QNode** prev_node_next = NULL; //二级指针,指向优先级最高的节点的前一个节点的next指针QNode* prev_node = NULL; //指向优先级最高的节点的前一个节点QNode* temp = NULL,*last = NULL; //temp遍历队列,last指向temp指向的前一个节点prev_node_next = &(q->head); //最开始指向队头指针(也就是第一个节点的前一个节点的next指针),解引用就是指向第一个节点last = q->head; temp = last->next; while (temp != NULL){if (temp->priority > (*prev_node_next)->priority){cout << "找到了一个更高的优先级:" << temp->priority << endl;prev_node_next = &(last->next); //指向temp的前一个节点的next指针prev_node = last; //指向temp的前一个节点}last = temp;temp = temp->next;}*out = (*prev_node_next)->date; //传递出队元素的值temp = *prev_node_next; // temp指向要删除节点*prev_node_next = (*prev_node_next)->next; //或者是 prev_node_next = & (*prev_node_next)->next;delete temp;q->length--;//情况一:删除节点后为空队列if (q->length == 0){q->head = q->tail = NULL;}//情况二:删除的是尾节点else if ( *prev_node_next == NULL && prev_node != NULL){q->tail = prev_node;}//情况三:删除的是首节点,与情况一不同的是删除节点后,队列不为空//情况四:普通情况//这两种情况遍历结束后的调整中头尾指针就弄好了return true;
}
如果你觉得我这里写得不好,嘻嘻,因为明明只需要用一级指针,我偏要用二级指针,这就是我与明明的区别,哈哈,好了不开玩笑,可以看看下图帮助理解。

队列的打印、清空、获取队首元素
//打印队列
bool Print(Queue* q)
{if (!q) return false;if (IsEmpty(q)){cout << "队列为空" << endl;}QNode* p = q->head;cout << "队列中的元素:";while (p != NULL){printf("%d[优先级%d] ", p->date,p->priority);p = p->next;}cout << endl;return true;
}
//清空队列
bool ClearQueue(Queue* q)
{if (!q || IsEmpty(q)) return false;QNode* temp = q->head, * tmp = NULL;while (temp != NULL){tmp = temp->next;delete temp;temp = tmp;}q->length = 0;q->head = NULL;q->tail = NULL;return true;
}//获取队头
bool GetHead(Queue* sq, DateElem* date)
{if (!date || !sq || IsEmpty(sq))return false;*date = sq->head->date; return true;}
主函数测试代码
int main(void)
{Queue* q = new Queue;DateElem e = -1;initQueue(q);for (int i = 0; i < 10; i++){enterQueue(q, i + 2, i);}printf("队列中有%d个元素\n", q->length);Print(q);for (int i = 0; i < 5; i++){if (popQueue(q, &e)){cout << "出队的元素是:" << e << endl;}else{cout << "出队失败" << endl;}}cout << "出队后,";Print(q);cout << "清空队列后,";ClearQueue(q);Print(q);//清理资源delete q;return 0;
}
运行结果:

相关文章:
优先队列----数据结构
概念 不知道你玩过英雄联盟吗?英雄联盟里面的防御塔会攻击离自己最近的小兵,但是如果有炮车兵在塔内,防御塔会优先攻击炮车(因为炮车的威胁性更大),只有没有兵线在塔内时,防御塔才会攻击英雄。…...
nginx项目部署教程
nginx项目部署教程 1. 项目部署介绍 当我们的项目开发完毕后,我们需要将项目打包、部署到服务器上,供用户来使用。 目前,常见的部署方式有两种: 后端部署 前后端分离部署 1-1 后端部署 这是最古老的部署方式,也是…...
资源限流 + 本地分布式多重锁——高并发性能挡板,隔绝无效流量请求
前言 在高并发分布式下,我们往往采用分布式锁去维护一个同步互斥的业务需求,但是大家细想一下,在一些高TPS的业务场景下,让这些请求全部卡在获取分布式锁,这会造成什么问题? 瞬时高并发压垮系统 众所周知…...
day52【子序列】300.最长递归子序列 674.最长连续递增序列 718.最长重复子数组
文章目录 300.最长递增子序列674.最长连续递增序列718.最长重复子数组 300.最长递增子序列 题目链接:力扣链接 讲解链接:代码随想录链接 题意:给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而…...
计算机视觉 计算机视觉识别是什么?
计算机视觉识别(Computer Vision Recognition)是计算机科学和人工智能领域中的一个重要分支,它致力于使计算机系统能够模拟和理解人类视觉的过程,从而能够自动识别、分析和理解图像或视频中的内容。这一领域的发展旨在让计算机具备…...
Make.com实现多个APP应用的自动化的入门指南
Make.com是一款基于云的自动化平台,可帮助用户将多个应用程序连接在一起,并通过设置自动化流程来简化日常任务。Make.com提供丰富的API集成,支持连接各种流行的应用程序,包括社交媒体、电子商务、CRM等。 使用Make.com实现多个AP…...
LLMs之HFKR:HFKR(基于大语言模型实现异构知识融合的推荐算法)的简介、原理、性能、实现步骤、案例应用之详细攻略
LLMs之HFKR:HFKR(基于大语言模型实现异构知识融合的推荐算法)的简介、原理、性能、实现步骤、案例应用之详细攻略 目录 HFKR的简介 异构知识融合:一种基于LLM的个性化推荐新方法...
多模态 多引擎 超融合 新生态!2023亚信科技AntDB数据库8.0产品发布
9月20日,以“多模态 多引擎 超融合 新生态”为主题的亚信科技AntDB数据库8.0产品发布会成功举办,从技术和生态两个角度全方位展示了AntDB数据库第8次大型能力升级和生态建设成果。浙江移动、用友、麒麟软件、华录高诚、金云智联等行业伙伴及业界专家共同…...
elasticsearch无法访问9200端口
近期部署elasticsearch后,启动时发现一直报如下错误: curl: (7) Failed connect to localhost:9200; Connection refused 部署的版本为elasticsearch-7.13.2,排查原因是因为开启了ssl认证。 解决方法: 在/opt/software/elasticsearch-7.13.2/config下…...
【Linux】进程等待
文章目录 进程等待进程等待必要性实验(见见猪跑)进程等待的方法wait方法waitpid**方法**宏的使用方法获取子进程status 阻塞VS非阻塞概念对比非阻塞有什么好处 具体代码实现进程的阻塞等待方式:进程的非阻塞等待方式:让父进程做其他任务 进程等待 进程等待必要性 之前讲过&am…...
电视「沉浮录」:跌出家电“三大件”?
【潮汐商业评论/原创】 “这年头谁还看电视,家里电视近一年都没打开过了,我明天就打算把它二手卖掉。”想到已落灰许久的电视机,Andy打开了二手平台。 “要不是这几年孩子网课多,我是真没考虑换新电视,家里用了8年的…...
前端实现调用打印机和小票打印(TSPL )功能
Ⅰ- 壹 - 使用需求 前端 的方式 点击这个按钮,直接让打印机打印我想要的东西 Ⅱ - 贰 - 小票打印 目前比较好的方式就是直接用 TSPL 标签打印指令集, 基础环境就不多说了,这个功能的实现就是利用usb发送指令,现在缺少个来让我们能够和usb沟通的工具,下面这就是推…...
串口通信(6)应用定时器中断+串口中断实现接收一串数据
本文为博主 日月同辉,与我共生,csdn原创首发。希望看完后能对你有所帮助,不足之处请指正!一起交流学习,共同进步! > 发布人:日月同辉,与我共生_单片机-CSDN博客 > 欢迎你为独创博主日月同…...
【WinForm详细教程六】WinForm中的GroupBox和Panel 、TabControl 、SplitContainer控件
文章目录 1.GroupBox和Panel2.TabControl3.SplitContainer 1.GroupBox和Panel GroupBox:是一个分组容器,提供一个框架将相关的控件组织在一起,它有标题、边框,但没有滚动条。 Panel:也是一个容器控件,用来…...
gradle与maven
Gradle 和 Maven 都是流行的构建工具,通常用于构建和管理 Java 和 Android 项目。它们都可以自动下载依赖库、编译代码、运行测试、打包和发布等。 以下是对 Gradle 和 Maven 的介绍: Gradle: Gradle 是一个基于 Groovy 和 Kotlin 的构建自…...
2.Docker基本架构简介与安装实战
1.认识Docker的基本架构 下面这张图是docker官网上的,介绍了整个Docker的基础架构,我们根据这张图来学习一下docker的涉及到的一些相关概念。 1.1 Docker的架构组成 Docker架构是由Client(客户端)、Docker Host(服务端)、Registry(远程仓库)组成。 …...
拓世法宝 | 数字经济崛起,美业如何抓住流量风口?
爱美之心,人皆有之。无论男女,都会很自然地对美好事物燃起兴致,跟高颜值相关的事物总能聚集注意力。例如直播平台里的美女网红收割流量赚得盆满钵满,面庞俊俏的年轻偶像吸引万千粉丝,还有“央视最美记者”王冰冰、“最…...
Scala 泛型编程
1. 泛型 Scala 支持类型参数化,使得我们能够编写泛型程序。 1.1 泛型类 Java 中使用 <> 符号来包含定义的类型参数,Scala 则使用 []。 class Pair[T, S](val first: T, val second: S) {override def toString: String first ":" sec…...
索引失效的场景有哪些?
虽然你这列上建了索引,查询条件也是索引列,但最终执行计划没有走它的索引。下面是引起这种问题的几个关键点。 列与列对比 某个表中,有两列(id和c_id)都建了单独索引,下面这种查询条件不会走索引 select…...
Java进阶04 final关键字、abstract抽象、interface接口、JDK8与JDK9中接口的区别、内部类和匿名类
文章目录 一、final关键字二、abstract关键字三、接口interface四、JDK8和JDK9中接口的区别五、内部类 一、final关键字 final可以修饰类、方法、变量 用final修饰类 表示此类不能被继承 用final修饰方法 表示方法不可以被重写 用final修饰变量 既可以修饰成员变量也可以修饰…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...
医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor
1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...
Axure零基础跟我学:展开与收回
亲爱的小伙伴,如有帮助请订阅专栏!跟着老师每课一练,系统学习Axure交互设计课程! Axure产品经理精品视频课https://edu.csdn.net/course/detail/40420 课程主题:Axure菜单展开与收回 课程视频:...
前端异步编程全场景解读
前端异步编程是现代Web开发的核心,它解决了浏览器单线程执行带来的UI阻塞问题。以下从多个维度进行深度解析: 一、异步编程的核心概念 JavaScript的执行环境是单线程的,这意味着在同一时间只能执行一个任务。为了不阻塞主线程,J…...
Unity VR/MR开发-开发环境准备
视频讲解链接: 【XR马斯维】UnityVR/MR开发环境准备【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...
