35_队列

一、队列的基本概念1. 队列的定义(1) 队列的逻辑结构a. 线性表的特例i. 在一端插入在另一端删除⓵ 队尾与队头2. 队列的特点(1) 先进先出a. FIFO 结构i. 最先进入的元素最先被访问二、队列的数学表示1. 队列的状态表示(1) 队列的序列形式KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…其中q1q_1q1​为队头qnq_nqn​为队尾2. 队列的基本操作(1) 入队KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…(2) 出队KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…三、队列的存储结构1. 顺序队列(1) 基于数组实现a. 队头指针fronti. 队尾指针rear⓵front rear表示空队列(2) 顺序队列的问题a. 假溢出现象i. 数组前端有空闲但无法插入2. 循环队列(1) 逻辑上的环形结构a. 取模运算实现循环i.rear (rear 1) % MAXSIZE(2) 队空与队满的判断a. 队空条件front rearb. 队满条件(rear 1) % MAXSIZE front(3) 代码结构/** Allman 风格*/KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…3. 链式队列(1) 基于链表实现a. 队头指针指向头结点b. 队尾指针指向尾结点i. 入队尾插法⓵ 出队删除头结点四、队列的时间复杂度分析1. 基本操作(1) 入队a. 循环队列O(1)O(1)O(1)b. 链式队列O(1)O(1)O(1)(2) 出队a. 循环队列O(1)O(1)O(1)b. 链式队列O(1)O(1)O(1)五、队列的变体1. 双端队列(1) 两端都可以插入和删除a. 输入受限的双端队列b. 输出受限的双端队列2. 优先队列(1) 按优先级出队a. 通常用堆实现i. 最大堆与最小堆3. 阻塞队列(1) 队列空时出队阻塞(2) 队列满时入队阻塞六、队列的应用场景1. 任务调度(1) CPU 任务排队a. 先来先服务2. 缓冲区管理(1) 生产者-消费者模型a. 生产者将数据放入队列b. 消费者从队列取出数据3. 广度优先搜索(1) 图的 BFS 算法a. 使用队列存储待访问节点i. 每次从队头取出节点⓵ 将邻接节点加入队尾4. 消息队列(1) 系统间异步通信a. 消息的生产与消费解耦七、队列与栈的对比1. 访问规则(1) 栈LIFO(2) 队列FIFO2. 典型应用(1) 栈递归、表达式求值(2) 队列BFS、任务调度