《队列队列应用举例》课件

队列应用举例队列是计算机科学中常用的数据结构，遵循先进先出原则，广泛应用于操作系统、网络通信等场景课件内容总览算法题及代码实践队列应用典型案例队列常见操作及实现解决经典算法问题队列基本原理与分类分析实际应用场景掌握队列核心操作方法了解队列本质与各种变体什么是队列原则入队操作出队操作FIFO先进先出线性数据结构元素只能从队尾加入元素只能从队首移除队列的日常生活体现银行排队车站购票客户按到达顺序获取服务乘客依次排队买票叫号系统保证公平性先到先得原则队列的特性单向性只能从一端进另一端出有序性按加入顺序排列不可随机访问无法直接访问中间元素队列与栈的区别栈队列先进后出LIFO先进先出FIFO只能在一端操作两端分别进出类比书堆叠放类比排队等候队列的分类链式队列顺序队列基于链表实现基于数组实现循环队列解决假溢出问题双端队列优先队列两端都可操作按优先级出队常见的队列实现方式数组实现固定大小空间操作简单高效需处理队首移动链表实现动态分配内存无需考虑大小指针操作灵活队列的抽象数据类型入队出队取队头FrontEnqueue Dequeue在队尾添加元素移除队首元素查看队首元素判空判满/检查队列状态队列在信息系统中的作用调度管理任务优先级分配异步处理解耦生产消费缓冲区管理平衡处理速率队列基本操作入队判断队列是否已满检查剩余空间新元素加入队尾放置到队尾位置队尾指针后移更新队尾位置队列基本操作出队判断队列是否为空检查队列状态队头元素被移除取出最先进入的元素队头指针后移更新队头位置查看队头元素访问队头位置通过队头指针直接获取返回元素值不修改队列结构预览即将出队元素提前查看不改变队列判空与判满操作判空条件判满条件处理边界情况队头指针等于队尾指针队尾下一位置等于队头防止上溢和下溢顺序队列实现方法数据结构主要问题固定大小数组假溢出现象front指向队头元素空间浪费rear指向队尾后一位置需要数组搬移操作链式队列实现方法节点结构数据域+指针域队列结构头指针+尾指针入队操作修改尾指针出队操作修改头指针优势动态扩容无溢出循环队列的意义解决假溢出提高空间利用率队列空间尚有空余循环复用数组空间因队尾指针到达末端无法入队避免频繁移动元素适用场景固定大小缓冲区需要频繁进出队操作循环队列代码实现要点i+1%n rear+1%n模运算判满条件指针循环移动队尾下一位置为队头front==rear判空条件队头队尾指针重合优先队列的实现堆结构实现最大/最小堆元素优先级排序优先级决定出队顺序时间复杂度插入/删除Olog n双端队列介绍DEQUE双向操作队首队尾均可操作四种基本操作队首队尾分别入队出队应用灵活可同时模拟栈和队列队列在进程调度中的应用就绪队列管理阻塞队列处理进程等待CPU资源等待I/O完成的进程多级反馈队列动态调整进程优先级队列在生产者消费者问题中-生产者数据缓冲区生成数据并入队队列存储临时数据同步机制消费者协调生产消费速率取出数据并处理队列在宽度优先搜索中的应用起点入队搜索起始节点加入队列扩展邻居当前节点的邻接点入队逐层遍历保证先访问近的节点查找目标寻找满足条件的节点队列在消息队列系统中的应用异步通信负载均衡实际产品服务间解耦平滑处理请求RabbitMQ非阻塞处理防止系统过载KafkaRocketMQ队列在缓冲区中的使用IO输入缓冲输出缓冲存储待处理输入数据暂存待输出数据平衡输入速率差异批量高效处理性能优化减少系统调用次数提高响应速度打印任务管理中的队列打印请求入队用户发送打印任务队列中等待按先来先服务排队打印机处理依次处理队首任务任务完成出队移除已完成任务队列在模拟排队系统中的作用双端队列在滑动窗口最大值问题的应用维护单调队列保持队列中元素单调递减移除过期元素队首元素不在当前窗口则出队新元素入队前清理移除队尾小于新元素的所有元素窗口最大值队首元素即为窗口最大值优先队列在事件驱动仿真中的应用事件排序按时间戳或优先级排序处理最紧急事件优先队列弹出最高优先级事件生成新事件处理结果产生新事件入队推进仿真时钟按事件顺序推进系统时间单调队列优化DP核心思想应用案例维护候选状态单调性滑动窗口问题快速查找最优转移区间最值查询特定DP状态转移数据流中的中值计算O1Olog n查询复杂度插入复杂度常数时间获取中位数堆操作对数时间2堆数量大顶堆存小一半数小顶堆存大一半数队列在缓存淘汰策略中的应用新数据入队缓存满时淘汰队首新缓存项加入队尾容量达到上限移除最早进入的缓存项与队列的关系LRU最近使用记录访问提升优先级淘汰最久未用双向链表记录访问顺访问元素移至队尾移除队首元素序哈希表辅助快速定位队列节点路由器数据包调度中的队列高优先级队列实时流量优先处理中优先级队列视频流等带宽需求大低优先级队列普通数据非实时需求音视频流缓冲应用队列数据接收缓冲区存储网络数据包入队2队列暂存媒体数据平滑播放解码处理均衡网络波动影响数据出队进行解码算法思路讲解BFS队列作用算法步骤存储待访问节点起点入队保证访问顺序取出队首扩展实现逐层扩展邻居节点入队直到队列为空示例无权图最短路径BFS起点入队设置访问标记扩展相邻节点未访问邻居入队记录路径信息保存前驱节点找到终点回溯构建最短路径代码实现（简易版）BFSvoid BFSGraphG,int start{Queue Q;//创建队列Q.enqueuestart;//起点入队visited[start]=true;//标记已访问while!Q.isEmpty{int v=Q.dequeue;//出队//处理当前节点processv;//遍历所有邻接点for每个邻接点w{if!visited[w]{Q.enqueuew;//入队visited[w]=true;//标记已访问}}}}循环队列代码实现（）C++templateclass CircularQueue{private:T*data;//存储数据的数组int front;//队头指针int rear;//队尾指针int capacity;//队列容量public:CircularQueueint size{data=new T[size];capacity=size;front=rear=0;}bool isEmpty{return front==rear;}bool isFull{return rear+1%capacity==front;}bool enqueueTvalue{if isFullreturn false;data[rear]=value;rear=rear+1%capacity;return true;}bool dequeueTvalue{if isEmptyreturn false;value=data[front];front=front+1%capacity;return true;}};链式队列的示例代码（）Pythonclass Node:def__init__self,data:self.data=dataself.next=Noneclass LinkedQueue:def__init__self:self.front=None#队头指针self.rear=None#队尾指针self.size=0#队列大小def is_emptyself:return self.front isNonedef enqueueself,data:new_node=Nodedataif self.is_empty:self.front=new_nodeelse:self.rear.next=new_nodeself.rear=new_nodeself.size+=1def dequeueself:if self.is_empty:return Nonedata=self.front.dataself.front=self.front.nextif self.front isNone:self.rear=Noneself.size-=1return data生产者消费者代码（多线程场景）-#include#include#includetemplateclass ThreadSafeQueue{private:std::queue queue;mutable std::mutex mutex;std::condition_variable cond_not_empty;std::condition_variable cond_not_full;unsigned intcapacity;public:ThreadSafeQueueunsigned intcap:capacitycap{}void produceT item{std::unique_lock lockmutex;//队列满则等待cond_not_full.waitlock,[this]{return queue.sizecapacity;};queue.pushitem;//通知消费者有新数据cond_not_empty.notify_one;}T consume{std::unique_lock lockmutex;//队列空则等待cond_not_empty.waitlock,[this]{return!queue.empty;};Titem=queue.front;queue.pop;//通知生产者有空间cond_not_full.notify_one;return item;}};滑动窗口最大值代码实例//使用双端队列解决滑动窗口最大值问题vector maxSlidingWindowvectornums,int k{vector result;deque dq;//存储索引for inti=0;inums.size;i++{//移除超出窗口范围的元素if!dq.emptydq.fronti-k+1{dq.pop_front;}//保持队列单调递减while!dq.emptynums[dq.back]nums[i]{dq.pop_back;}//新元素入队dq.push_backi;//窗口形成后，输出结果if i=k-1{result.push_backnums[dq.front];}}return result;}用队列实现栈（题解）Leetcodeclass MyStack{private:queue q1;queue q2;public:MyStack{}//入栈操作void pushintx{//将新元素加入q2q

2.pushx;//将q1中所有元素移到q2while!q

1.empty{q

2.pushq

1.front;q

1.pop;}//交换q1和q2，使q1包含所有元素swapq1,q2;}//出栈操作int pop{int val=q

1.front;q

1.pop;return val;}//查看栈顶元素int top{return q

1.front;}//判断栈是否为空bool empty{return q

1.empty;}};用栈实现队列（题解）Leetcodeclass MyQueue{private:stack s1;//输入栈stack s2;//输出栈public:MyQueue{}//入队操作void pushintx{s

1.pushx;}//出队操作int pop{//如果输出栈为空，将输入栈的元素全部导入if s

2.empty{while!s

1.empty{s

2.pushs

1.top;s

1.pop;}}int val=s

2.top;s

2.pop;return val;}//查看队头元素int peek{//如果输出栈为空，将输入栈的元素全部导入if s

2.empty{while!s

1.empty{s

2.pushs

1.top;s

1.pop;}}return s

2.top;}//判断队列是否为空bool empty{return s

1.emptys

2.empty;}};优先队列堆排序核心思想插入操作新元素加入堆底上浮调整堆结构弹出堆顶操作取出堆顶元素堆底元素移至堆顶下沉调整堆结构堆排序过程构建最大堆反复取堆顶元素队列应用常见算法题回顾LeetCode225LeetCode232用队列实现栈用栈实现队列LeetCode239LeetCode622滑动窗口最大值设计循环队列队列与并发编程无锁队列阻塞队列原子操作保证线程安全空时阻塞获取操作避免锁竞争开销满时阻塞添加操作线程池应用任务队列管理工作线程分发队列应用领域拓展微服务架构事件流平台分布式系统移动应用服务间解耦通信Kafka流处理任务调度与负载均衡离线数据同步队列课程总结与学习建议理解基本原理掌握队列核心性质实现各类队列亲手编写代码加深理解练习算法题目应用队列解决实际问题拓展实际应用在项目中灵活运用队列谢谢大家！提问环节课后资料欢迎针对课程内容提问代码示例分享队列相关经验算法题推荐联系方式欢迎交流讨论持续学习进步。