2026年1月21日学习记录

今日学习内容

一、栈（Stack）

记一句话：

栈 = 只能从一头进、从同一头出的容器。

头叫做 栈顶（top），规则是 后进先出（LIFO, Last In First Out）。

1.1 用数组实现一个最简单的栈

用数组来模拟是最直观的。

let stack = [];

入栈（push）

stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]

每次 push，都是往数组末尾加元素，相当于把盘子放到最上面。

出栈（pop）

stack.pop(); // 3
// stack 变成 [1, 2]

pop 只会移除并返回最后一个元素。

查看栈顶（peek / top）

stack[stack.length - 1]; // 2

1.2 函数调用为什么离不开栈

程序里的函数调用，本质上就是：

函数一层一层“叠”起来，执行完再一层一层“拆”掉。

这正好符合栈的特性。

调用过程直觉示意

main()
  -> a()
      -> b()
      <- b() 返回
  <- a() 返回
<- main() 返回

每调用一次函数，就会压栈一个「栈帧（stack frame）」

一个栈帧里通常包含：

• 返回地址（函数结束后回到哪一行）
• 参数
• 局部变量

当函数执行完：

• 当前栈帧 出栈

• 控制权回到上一个函数

  为什么用“栈”最自然？

因为：

• 一定是“最后调用的函数先返回”
• 调用顺序天然是 LIFO

1.3 栈溢出（Stack Overflow）是怎么发生的

调用栈的空间是有限的。

如果写了一个递归：

function f() {
  f();
}

发生的事情是：

• f 调用 f

• f 再调用 f

• 不断压栈

• 没有任何出栈机会

  栈空间被用完，就会 Stack Overflow。

常见解决思路

• 把深递归改成迭代

while (condition) {
  // 模拟递归的一步
}

• 用「显式栈」代替系统调用栈

const stack = [initialState];

while (stack.length) {
  const state = stack.pop();
  // 处理 state
  // 把“下一层递归”手动 push 进去
}

• 减少每层递归携带的数据

二、堆（Heap）

“Heap”在中文里经常被翻译成“堆”，但它其实是两个不同概念共用同一个英文单词，这也是最容易卡住的地方。

先记一句话做总开关：

Heap（堆）=（1）内存里的“对象区” 或（2）一种“优先级数据结构”。

• 堆内存（heap memory）：讲的是“数据放在哪、活多久、怎么释放”
• 堆数据结构（heap data structure）：讲的是“怎么快速拿到最大/最小（最高优先级）”

2.1 堆内存（Heap Memory）：动态分配的“对象区”

一个更容易理解的对比方式是：

• 栈（调用栈）：函数调用形成栈帧；进入函数压栈，返回时出栈
• 堆（堆内存）：对象/数据可以在函数返回后继续存在（只要还有引用指向它）

在很多语言里：

• 创建对象/数组/闭包等，往往会落在“堆内存”（具体实现细节因语言/引擎而异，但这个直觉很有用）
• 什么时候释放由不同机制决定：
  • GC（垃圾回收）：Java/JS/Go 等
  • 手动管理或借助所有权模型：C/C++/Rust 等

1 分钟例子（用 JS 直觉理解“函数返回了，对象还在”）

function makeUser() {
  const user = { name: "A" };
  return user;
}

const u = makeUser();
console.log(u.name); // 依然能访问

发生了什么（直觉版）：

• makeUser() 执行时，会有自己的“调用栈帧”（局部变量 user 这个“引用/指针”在这里）
• { name: 'A' } 这个对象本体通常在“堆内存”
• 函数返回后：栈帧消失了，但返回值 u 继续指向堆里的对象，所以对象还能用

今天的关键理解

“栈更像调用过程的临时工作台；堆更像长期存放对象的仓库。”

（这是直觉比喻，不代表所有语言实现细节都完全一致。）

2.2 堆数据结构（Heap DS）：优先队列的经典实现

堆（数据结构）通常指 二叉堆（binary heap）。它不是“随便一堆数据”，而是一种弱有序结构：

• 它不要求“整体排序”
• 但能保证“堆顶永远是最大/最小”

它满足：

• 最大堆：父节点 ≥ 子节点，堆顶是最大值
• 最小堆：父节点 ≤ 子节点，堆顶是最小值

为什么能用数组表示（二叉堆的下标关系）

把堆当作一棵“完全二叉树”，用数组存时有固定映射：

• 父节点：parent(i) = floor((i - 1) / 2)
• 左孩子：left(i) = 2 * i + 1
• 右孩子：right(i) = 2 * i + 2

这会让“向上/向下调整”只需要沿着树高走一条路径。

操作的直觉（只记两句话就够用）

• push：先放在数组末尾，然后**向上冒泡（sift up）**直到满足堆性质
• pop：取走堆顶，把末尾元素放到堆顶，然后**向下下沉（sift down）**恢复堆性质

二叉堆常用数组表示，支持高效操作：

• push（插入）：$O(\log n)$
• pop（弹出堆顶）：$O(\log n)$
• peek（查看堆顶）：$O(1)$

典型用途：

• 优先队列（Priority Queue）
• Top K 问题
• 调度/任务队列
• Dijkstra / A* 等图算法

2.3 栈（Stack）vs 堆（Heap）：一张更不容易误解的对照表

因为“堆”有两层含义，这里分开对比：

对比对象	核心点
栈（调用栈） vs 堆内存	一个偏“函数调用与局部变量生命周期”，一个偏“对象/动态数据的生命周期与管理方式”
栈（数据结构） vs 堆（数据结构）	一个 LIFO；一个用来高效取最大/最小（优先队列）

---

今日小结

• 栈的本质是：只能操作一端的 LIFO 结构
• 调用栈让函数调用天然按「后调用先返回」执行
• “堆”要分清两种：堆内存（对象区）与堆结构（优先队列/二叉堆）

---