罗罗编程学习记录
本页内容 展开查看

02.3.2 栈与队列、单调栈

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列

这个知识域解决什么问题

栈与队列是受限线性结构,分别对应回溯嵌套与顺序处理两类场景。本知识域围绕一条主线展开:栈基础与括号表达式求值 → 单调栈与柱状图、接雨水 → 队列、双端队列与循环队列 → 优先队列、堆与栈队列综合。重点讲清结构语义、模拟推导与单调化维护过程,代码以 Java 为主并标注边界条件。

知识地图

栈基础与括号表达式求值(1)
  → 单调栈与柱状图、接雨水(2)
    → 队列、双端队列与循环队列(3)
      → 优先队列、堆与栈队列综合(4)

子主题

编号 子主题 核心内容 题数
02.3.2.1 栈基础与括号表达式求值 LIFO、数组/链表实现、有效括号、逆波兰求值、中缀转后缀、计算器、字符串解码、调用栈与 DFS 20
02.3.2.2 单调栈与柱状图、接雨水 单调方向、每日温度、下一个更大、循环数组、柱状图最大矩形、接雨水栈/DP/双指针、均摊 O(n) 20
02.3.2.3 队列、双端队列与循环队列 FIFO、链表队列、两栈队列、Deque、循环队列判空判满、队列实现栈、BFS 与层序遍历 20
02.3.2.4 优先队列、堆与栈队列综合 堆数组表示、上浮下沉、建堆 O(n)、Top-K、第 K 大、双堆中位数、单调队列窗口最大、最小栈、复杂度对比 20

合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。

学习路径

先 1 掌握栈语义与括号/表达式求值,再 2 练熟单调栈的弹栈结算模板与柱状图、接雨水三种解法,3 理解队列语义、两栈模拟与循环队列设计,最后 4 掌握堆、优先队列与单调队列的选型和复杂度推导。

自检

  • [ ] 能手写有效括号与逆波兰求值,说明减法除法顺序
  • [ ] 能讲清单调栈弹栈结算时左右边界与当前元素角色
  • [ ] 能写出柱状图最大矩形与接雨水单调栈代码,并对照 DP/双指针空间口径
  • [ ] 能设计循环队列并说明判空判满两种口径
  • [ ] 能说清两栈实现队列的均摊 O(1) 推导
  • [ ] 能手写双堆数据流中位数与窗口最大值单调队列
  • [ ] 每题能报出时间、空间与口径,并列边界用例