算法学习

Appearance

什么是队列（Queue）？ ​

队列是一种 先进先出（FIFO） 的数据结构，常用于广度优先搜索、事件处理、滑动窗口等场景。

我们可以把队列想象成一个排队买奶茶的队伍： 谁先来就先买，谁后到就后处理。

队列的应用根据不同问题特征，可以分为以下几种典型类型：

1. 基础队列（Basic Queue） ​

特点：

  • 支持基本的入队（enqueue）和出队（dequeue）操作
  • 用于顺序处理事件、流数据、状态转移等

适用场景：

  • 处理滑动时间窗口
  • 模拟操作顺序
  • 广度优先搜索（BFS）

举例：排队打卡记录签到时间

你是老师，看学生什么时候来上课，只记录最近5分钟内的学生 —— 队列就像一条“时间轴”。

对应题目：

2. 队列设计（Queue Design） ​

特点：

  • 根据题目要求设计复杂队列功能（循环队列、双端、合成结构等）
  • 多用类、链表、数组实现

适用场景：

  • 实现浏览器历史记录、任务分发系统
  • 模拟栈或双端队列

举例：你是地铁列车调度员，设计怎么上车、下车、转车

你要决定乘客从哪边上下、怎么进站、怎么切换列车 —— 不同设计适配不同需求。

对应题目：

3. 双端队列（Deque） ​

特点：

  • 支持两端入队出队
  • 比普通队列灵活，常用于滑动窗口、状态压缩

适用场景：

  • 从两端插入/移除数据
  • 优化搜索顺序或任务调度

举例：你管理一个剧院进出口，有前门和后门

观众既可以从前门进也可以从后门出，有些贵宾还可以插队 —— 这种结构就叫双端队列。

对应题目：

4. 单调队列（Monotonic Queue） ​

特点：

  • 队列内保持单调（通常是递减或递增）
  • 用于滑动窗口内最大值、最小值问题
  • 组合了「滑动窗口 + 单调栈」的技巧

适用场景：

  • 维护一段数据内的最大/最小值
  • 优化暴力嵌套判断为线性

举例：你看股市行情，想知道每个时间点过去几天的最高价

你只保留能代表最大值的价格 —— 谁不够高就踢出去。

对应题目：

5. 单调队列优化 DP（Monotonic Queue Optimized DP） ​

特点：

  • 用单调队列维护状态转移区间最大/最小值
  • 优化传统 DP 的暴力循环，提高效率到 O(n)

适用场景：

  • 解决类似「从前面的 f[j] 转移到 f[i]」的问题
  • 区间滑动，边界递增的转移过程

举例：你在安排快递车队，把不同重量的包裹组合起来最省油

你要找性价比最好的组合，并且每次更新都把差的选项剔除。

对应题目：

6. 队列优化搜索（BFS Queue） ​

特点：

  • 用队列实现层序遍历、状态图遍历
  • 可结合 visited 集合/距离表

适用场景：

  • 图搜索：迷宫、最短路径、多源 BFS
  • 网格搜索：僵尸感染、岛屿问题、火势蔓延等

举例：你是消防员，模拟火势从多点同时蔓延的过程

你按波次展开火源范围 —— 谁先烧到谁就先入队。

经典题型（未列入上方题单，可补刷）：

7. 设计类队列结构（Queue Design） ​

特点：

  • 多端口输入/输出、频率控制、容量限制、优先处理等
  • 通常结合其他数据结构（哈希表、堆、链表等）

适用场景：

  • 模拟现实系统（缓存、排队、资源调度）
  • 高性能系统数据结构

举例：你设计一个饭店等位系统，还要优先照顾老人和孕妇

你用一个系统记录入队时间、是否优先、有无重复 —— 自定义队列结构应运而生。

对应题目：

📌 总结一句话：

队列擅长处理“按顺序推进”的问题，从事件流到图搜索，从滑动窗口到状态转移，只要你需要“排队”，它就是你的好帮手。