当前位置: 首页 > news >正文

优先队列----数据结构

概念

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

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

空队列

插入一个元素

插入第二个元素

 删除一个节点

上列情况是最普通的情况(无需多余的操作),显然如果删除的是队列中的最后一个节点,尾指针需要手动移动;如果删除的是队列中的第一个节点,头指针会自动移动。如果删除的队列只有一个节点,那头尾指针需要手动置空。所以总共有 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;
}

 运行结果:

相关文章:

优先队列----数据结构

概念 不知道你玩过英雄联盟吗&#xff1f;英雄联盟里面的防御塔会攻击离自己最近的小兵&#xff0c;但是如果有炮车兵在塔内&#xff0c;防御塔会优先攻击炮车&#xff08;因为炮车的威胁性更大&#xff09;&#xff0c;只有没有兵线在塔内时&#xff0c;防御塔才会攻击英雄。…...

nginx项目部署教程

nginx项目部署教程 1. 项目部署介绍 当我们的项目开发完毕后&#xff0c;我们需要将项目打包、部署到服务器上&#xff0c;供用户来使用。 目前&#xff0c;常见的部署方式有两种&#xff1a; 后端部署 前后端分离部署 1-1 后端部署 这是最古老的部署方式&#xff0c;也是…...

资源限流 + 本地分布式多重锁——高并发性能挡板,隔绝无效流量请求

前言 在高并发分布式下&#xff0c;我们往往采用分布式锁去维护一个同步互斥的业务需求&#xff0c;但是大家细想一下&#xff0c;在一些高TPS的业务场景下&#xff0c;让这些请求全部卡在获取分布式锁&#xff0c;这会造成什么问题&#xff1f; 瞬时高并发压垮系统 众所周知…...

day52【子序列】300.最长递归子序列 674.最长连续递增序列 718.最长重复子数组

文章目录 300.最长递增子序列674.最长连续递增序列718.最长重复子数组 300.最长递增子序列 题目链接&#xff1a;力扣链接 讲解链接&#xff1a;代码随想录链接 题意&#xff1a;给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而…...

计算机视觉 计算机视觉识别是什么?

计算机视觉识别&#xff08;Computer Vision Recognition&#xff09;是计算机科学和人工智能领域中的一个重要分支&#xff0c;它致力于使计算机系统能够模拟和理解人类视觉的过程&#xff0c;从而能够自动识别、分析和理解图像或视频中的内容。这一领域的发展旨在让计算机具备…...

Make.com实现多个APP应用的自动化的入门指南

Make.com是一款基于云的自动化平台&#xff0c;可帮助用户将多个应用程序连接在一起&#xff0c;并通过设置自动化流程来简化日常任务。Make.com提供丰富的API集成&#xff0c;支持连接各种流行的应用程序&#xff0c;包括社交媒体、电子商务、CRM等。 使用Make.com实现多个AP…...

LLMs之HFKR:HFKR(基于大语言模型实现异构知识融合的推荐算法)的简介、原理、性能、实现步骤、案例应用之详细攻略

LLMs之HFKR:HFKR(基于大语言模型实现异构知识融合的推荐算法)的简介、原理、性能、实现步骤、案例应用之详细攻略 目录 HFKR的简介 异构知识融合:一种基于LLM的个性化推荐新方法...

多模态 多引擎 超融合 新生态!2023亚信科技AntDB数据库8.0产品发布

9月20日&#xff0c;以“多模态 多引擎 超融合 新生态”为主题的亚信科技AntDB数据库8.0产品发布会成功举办&#xff0c;从技术和生态两个角度全方位展示了AntDB数据库第8次大型能力升级和生态建设成果。浙江移动、用友、麒麟软件、华录高诚、金云智联等行业伙伴及业界专家共同…...

elasticsearch无法访问9200端口

近期部署elasticsearch后&#xff0c;启动时发现一直报如下错误: curl: (7) Failed connect to localhost:9200&#xff1b; Connection refused 部署的版本为elasticsearch-7.13.2,排查原因是因为开启了ssl认证。 解决方法: 在/opt/software/elasticsearch-7.13.2/config下…...

【Linux】进程等待

文章目录 进程等待进程等待必要性实验(见见猪跑)进程等待的方法wait方法waitpid**方法**宏的使用方法获取子进程status 阻塞VS非阻塞概念对比非阻塞有什么好处 具体代码实现进程的阻塞等待方式:进程的非阻塞等待方式:让父进程做其他任务 进程等待 进程等待必要性 之前讲过&am…...

电视「沉浮录」:跌出家电“三大件”?

【潮汐商业评论/原创】 “这年头谁还看电视&#xff0c;家里电视近一年都没打开过了&#xff0c;我明天就打算把它二手卖掉。”想到已落灰许久的电视机&#xff0c;Andy打开了二手平台。 “要不是这几年孩子网课多&#xff0c;我是真没考虑换新电视&#xff0c;家里用了8年的…...

前端实现调用打印机和小票打印(TSPL )功能

Ⅰ- 壹 - 使用需求 前端 的方式 点击这个按钮&#xff0c;直接让打印机打印我想要的东西 Ⅱ - 贰 - 小票打印 目前比较好的方式就是直接用 TSPL 标签打印指令集, 基础环境就不多说了,这个功能的实现就是利用usb发送指令,现在缺少个来让我们能够和usb沟通的工具,下面这就是推…...

串口通信(6)应用定时器中断+串口中断实现接收一串数据

本文为博主 日月同辉&#xff0c;与我共生&#xff0c;csdn原创首发。希望看完后能对你有所帮助&#xff0c;不足之处请指正&#xff01;一起交流学习&#xff0c;共同进步&#xff01; > 发布人&#xff1a;日月同辉,与我共生_单片机-CSDN博客 > 欢迎你为独创博主日月同…...

【WinForm详细教程六】WinForm中的GroupBox和Panel 、TabControl 、SplitContainer控件

文章目录 1.GroupBox和Panel2.TabControl3.SplitContainer 1.GroupBox和Panel GroupBox&#xff1a;是一个分组容器&#xff0c;提供一个框架将相关的控件组织在一起&#xff0c;它有标题、边框&#xff0c;但没有滚动条。 Panel&#xff1a;也是一个容器控件&#xff0c;用来…...

gradle与maven

Gradle 和 Maven 都是流行的构建工具&#xff0c;通常用于构建和管理 Java 和 Android 项目。它们都可以自动下载依赖库、编译代码、运行测试、打包和发布等。 以下是对 Gradle 和 Maven 的介绍&#xff1a; Gradle&#xff1a; Gradle 是一个基于 Groovy 和 Kotlin 的构建自…...

2.Docker基本架构简介与安装实战

1.认识Docker的基本架构 下面这张图是docker官网上的&#xff0c;介绍了整个Docker的基础架构&#xff0c;我们根据这张图来学习一下docker的涉及到的一些相关概念。 1.1 Docker的架构组成 Docker架构是由Client(客户端)、Docker Host(服务端)、Registry(远程仓库)组成。 …...

拓世法宝 | 数字经济崛起,美业如何抓住流量风口?

爱美之心&#xff0c;人皆有之。无论男女&#xff0c;都会很自然地对美好事物燃起兴致&#xff0c;跟高颜值相关的事物总能聚集注意力。例如直播平台里的美女网红收割流量赚得盆满钵满&#xff0c;面庞俊俏的年轻偶像吸引万千粉丝&#xff0c;还有“央视最美记者”王冰冰、“最…...

Scala 泛型编程

1. 泛型 Scala 支持类型参数化&#xff0c;使得我们能够编写泛型程序。 1.1 泛型类 Java 中使用 <> 符号来包含定义的类型参数&#xff0c;Scala 则使用 []。 class Pair[T, S](val first: T, val second: S) {override def toString: String first ":" sec…...

索引失效的场景有哪些?

虽然你这列上建了索引&#xff0c;查询条件也是索引列&#xff0c;但最终执行计划没有走它的索引。下面是引起这种问题的几个关键点。 列与列对比 某个表中&#xff0c;有两列&#xff08;id和c_id&#xff09;都建了单独索引&#xff0c;下面这种查询条件不会走索引 select…...

Java进阶04 final关键字、abstract抽象、interface接口、JDK8与JDK9中接口的区别、内部类和匿名类

文章目录 一、final关键字二、abstract关键字三、接口interface四、JDK8和JDK9中接口的区别五、内部类 一、final关键字 final可以修饰类、方法、变量 用final修饰类 表示此类不能被继承 用final修饰方法 表示方法不可以被重写 用final修饰变量 既可以修饰成员变量也可以修饰…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...