还剩21页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《队列及其应用》ppt课件•队列的基本概念•队列的实现•队列的应用•队列的变种•队列的性能分析01队列的基本概念队列的定义01队列是一种特殊的线性表,它只允许在表的前端进行删除操作,在表的后端进行插入操作02队列中的元素遵循先进先出(FIFO)的原则,即最早进入队列的元素将最先被删除队列的特点010203有界性线性结构队列的运算队列的大小是有限的,有队列中的元素按照一定的队列可以进行插入、删除、一定的容量限制顺序排列,遵循先进先出查找等基本运算的原则队列的操作入队队列的长度在队列的尾部添加一个元素的队列中当前元素的个数操作出队判断队列是否为空从队列的头部删除一个元素的检查队列是否为空,如果为空操作则返回true,否则返回false02队列的实现数组实现队列数组实现队列的基本思路是使用一个数组来存储1队列中的元素,并使用两个指针分别指向队列的头和尾数组实现队列的优点是存取速度快,因为数组的2存取操作是O1时间复杂度数组实现队列的缺点是空间利用率低,因为当队3列为空时,数组中仍有一部分空间被占用链表实现队列链表实现队列的基本思路是使链表实现队列的优点是空间利链表实现队列的缺点是存取速用一个链表来存储队列中的元用率高,因为当队列为空时,度慢,因为链表的存取操作是素,并使用两个指针分别指向链表中的节点可以被释放On时间复杂度队列的头和尾循环队列的实现循环队列的基本思路是将数组中的元素循环使用,当队列满时,01尾指针可以回到数组的开头继续存储元素循环队列的优点是空间利用率高,因为当队列满时,尾指针可02以回到数组的开头继续存储元素,避免了空间的浪费循环队列的缺点是处理溢出情况比较复杂,需要特别处理当队03列满时再添加元素的情况03队列的应用操作系统中的进程调度进程调度操作系统中的进程调度使用队列来实现,按照优先级、时间片轮转等方式对进程进行排队等待处理进程状态进程在等待、就绪、运行等状态之间的转换通过队列实现,等待状态的进程被放入等待队列,就绪状态的进程被放入就绪队列调度算法操作系统中的调度算法如先来先服务(FCFS)、最短作业优先(SJF)、优先级调度等,都是基于队列实现的数据库中的事务处理事务状态事务在等待、执行、提交等状态之事务排队间的转换通过队列实现,等待状态的事务被放入等待队列,执行状态数据库中的事务处理通过队列来的事务被放入执行队列实现,多个事务按照一定的顺序进行排队等待处理事务隔离级别数据库中的事务隔离级别如读未提交、读已提交、可重复读等,会影响事务的排队顺序和执行顺序网络通信中的数据包处理数据包排队01网络通信中的数据包处理通过队列来实现,多个数据包按照一定的顺序进行排队等待处理数据包状态02数据包在发送、接收、转发等状态之间的转换通过队列实现,发送状态的数据包被放入发送队列,接收状态的数据包被放入接收队列数据包调度算法03网络通信中的数据包调度算法如先进先出(FIFO)、最短优先(Shortest First)、基于优先级的调度等,都是基于队列实现的04队列的变种循环队列总结词循环队列是一种特殊的线性表,它使用一组固定大小的存储单元,当队列的尾部到达最后一个位置时,头部会回到第一个位置详细描述循环队列通常使用数组来实现,当队列为空时,头尾指针都指向数组的第一个元素;当队列满时,头尾指针都指向数组的最后一个元素循环队列具有高效的插入和删除操作,时间复杂度为O1双端队列总结词双端队列是一种具有两个端点的队列,可以在两端进行插入和删除操作详细描述双端队列可以在队列的两端进行操作,因此具有更高的灵活性双端队列可以使用数组或链表来实现,其时间复杂度取决于具体的实现方式双端队列在处理数据流或需要频繁在两端进行操作的情况下非常有用优先队列总结词优先队列是一种特殊的数据结构,其中每个元素都有一个优先级,优先级最高的元素最先出队详细描述优先队列可以使用不同的数据结构来实现,如数组、链表、二叉堆等在优先队列中,优先级最高的元素最先出队,而优先级相同的元素按照它们在队列中的顺序出队优先队列在任务调度、路由算法等领域有广泛的应用05队列的性能分析队列的吞吐量吞吐量指队列在单位时间内处理或传输的平均数据量影响因素队列长度、服务时间、到达率等优化策略合理设置队列长度,优化服务时间,控制到达率等队列的延迟延迟指数据项在进入队列到开始处理的时间间隔影响因素服务时间、队列长度、到达率等优化策略提高服务效率,合理设置队列长度,控制到达率等队列的公平性公平性指队列中各个数据项获得处理机会的平等程度影响因素服务策略、优先级设置等优化策略采用公平的服务策略,避免优先级过高或过低的数据项影响其他数据项的处理THANKS感谢观看。