数据结构与算法 —— 前端的「内力」

1.1 大 O 记法是什么

大 O 描述的是数据规模 n 增长时，运行时间（或空间）的增长趋势，不看常数、不看机器。它回答一个问题：数据量翻 10 倍，你的代码会慢多少？

1.2 空间换时间：前端的核心权衡

缓存、memoization、索引、预计算——本质都是用内存换速度。这是前端性能优化最常见的套路，也是后面哈希表、堆、Trie 能「快」的根本原因。

// 反面：每次递归都重复计算 → O(2^n)
function fib(n){ return n <= 1 ? n : fib(n-1) + fib(n-2); }

// 正面：用 Map 做记忆化缓存 → O(n)
const memo = new Map();
function fib2(n){
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);      // 空间换时间
  const v = fib2(n-1) + fib2(n-2);
  memo.set(n, v);
  return v;
}
console.log(fib2(40)); // 0.001s vs fib(40) 要跑几十秒

2.1 JS 数组的特殊性

JS 数组是动态的、可以稀疏的，底层 V8 会把它优化为真正的连续内存（快数组）或哈希表（慢数组）。你不需要管理长度，但要知道：

• push / pop 在末尾操作 → O(1)
• shift / unshift 在头部操作 → O(n)（所有元素要搬家）
• splice / slice 中间操作 → O(n)
• indexOf / includes / find 无序查找 → O(n)；Set/Map 查找是 O(1)

2.2 案例解析：去重的三种写法，复杂度天差地别

// 写法一：includes 嵌套 → O(n²) ❌ 千万别写
const dedup1 = arr => {
  const r = [];
  for (const x of arr) if (!r.includes(x)) r.push(x);
  return r;
};

// 写法二：Set 去重 → O(n) ✅ 一行搞定
const dedup2 = arr => [...new Set(arr)];

// 写法三：Map 保序+去重（对象数组按 id 去重时） → O(n) ✅
const dedup3 = (arr, key) => {
  const seen = new Map();
  return arr.filter(x => !seen.has(x[key]) && seen.set(x[key], 1));
};
// 实测：10 万条随机数，写法一 ~15s，写法二 ~20ms，差 750 倍

解析过程：写法一每 push 一个元素都要把整个结果数组扫一遍（includes 是 O(n)），n 个元素就是 n×n；写法二 Set 底层是哈希表，插入和判断都是 O(1)，整体 O(n)。这就是「知道数据结构」和「不知道」的差距——同一件事，一个 20ms，一个 15 秒。

3.1 用数组实现一个栈

// push/pop 天然就是 O(1) 的栈操作
class Stack {
  #items = [];
  push(v){ this.#items.push(v); return this; }
  pop(){ return this.#items.pop(); }
  peek(){ return this.#items[this.#items.length - 1]; }
  get size(){ return this.#items.length; }
  get isEmpty(){ return this.#items.length === 0; }
}
// 使用
const undo = new Stack();
undo.push('输入 A'); undo.push('输入 B');
undo.pop(); // '输入 B'，撤销回到 '输入 A'

3.2 案例解析：括号匹配 —— 编译器和 JSX 校验都在用

// 遇到左括号入栈，遇到右括号必须与栈顶匹配
function isValid(s) {
  const map = { ')':'(', ']':'[', '}':'{' };
  const stack = [];
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch);
    else if (stack.pop() !== map[ch]) return false;  // 不匹配立即失败
  }
  return stack.length === 0;   // 栈空了才算全部配对
}
console.log(isValid('({[()]})')); // true
console.log(isValid('([)]'));     // false：交叉嵌套不合法

解析过程：'([)]' 为什么 false？扫描到 ) 时栈是 ['(', '[']，弹出的是 '['，而期望是 '('，不匹配 → 说明是交叉嵌套，语法非法。这个「栈顶必须配对」的思想，就是 ESLint 校验 JSX 标签闭合、Babel 解析代码括号的原理雏形。

4.1 手写队列：别用 shift！

// ❌ 简单但不高效：shift 是 O(n)
const q1 = []; q1.push(1); q1.shift();

// ✅ 用两个数组模拟（出队时反转）→ 均摊 O(1)
class Queue {
  #in = []; #out = [];
  enqueue(v){ this.#in.push(v); }
  dequeue(){
    if (this.#out.length === 0) {
      while (this.#in.length) this.#out.push(this.#in.pop());
    }
    return this.#out.pop();
  }
  get size(){ return this.#in.length + this.#out.length; }
}
// 原理：入队进 #in；出队时把 #in 反转倒入 #out，再 pop
// 每个元素最多被搬两次 → 总复杂度 O(n)，均摊到每次操作就是 O(1)

4.2 案例解析：事件循环里的两个队列

JS 单线程靠队列调度。每次「宏任务」执行完，会清空全部微任务，再取下一个宏任务。这就是为什么 Promise 一定在 setTimeout 之前执行：

console.log('1 同步');
setTimeout(() => console.log('2 宏任务'), 0);
Promise.resolve().then(() => console.log('3 微任务'));
console.log('4 同步');
// 输出顺序：1 → 4 → 3 → 2
// 因为微任务队列(Microtask)在宏任务之间被整体清空

解析过程：① 执行当前宏任务里的同步代码（1、4）；② 同步代码跑完，检查微任务队列，把 3 清空；③ 微任务空了，才去宏任务队列取 2。理解这个队列调度，async/await、setTimeout 顺序题全都能推。

4.3 案例解析：并发控制队列（前端必写）

// 限制同时最多 3 个请求，其余排队 —— 上传/图片预加载场景
async function runPool(tasks, limit = 3) {
  const results = new Array(tasks.length);
  const queue = [...tasks.entries()];       // 队列里放 [索引, 任务]
  const workers = Array.from({length: limit}, async () => {
    while (queue.length) {
      const [i, task] = queue.shift();      // 队头出队，谁闲谁干
      results[i] = await task();
    }
  });
  await Promise.all(workers);
  return results;
}
// 使用：20 张图最多同时下载 3 张
runPool(imgs.map(loadImg), 3).then(console.log);

5.1 手写单向链表

// 节点：存数据 + 指向下一个的指针
class Node {
  constructor(v){ this.value = v; this.next = null; }
}
class LinkedList {
  head = null;
  append(v){                       // 尾插 O(n)
    const node = new Node(v);
    if (!this.head) { this.head = node; return; }
    let cur = this.head;
    while (cur.next) cur = cur.next;
    cur.next = node;
  }
  prepend(v){                      // 头插 O(1)
    const node = new Node(v);
    node.next = this.head;
    this.head = node;
  }
  *[Symbol.iterator](){            // 让 for...of 能遍历
    let cur = this.head;
    while (cur) { yield cur.value; cur = cur.next; }
  }
}
const list = new LinkedList();
list.append(1); list.append(2); list.prepend(0);
console.log([...list]); // [0, 1, 2]

5.2 案例解析：React Fiber 为什么用链表？

React 15 的虚拟 DOM 是递归的：一次 render 必须一口气递归完，不能中断。React 16 的 Fiber 把它改成链表 + 循环：每个 Fiber 节点有 child（第一个子）、sibling（下一个兄弟）、return（父节点）三个指针。

// 一棵组件树对应的 Fiber 链表（简化）
//         <App>
//         /    \
//      <Header>  <Footer>
const fiberApp = {
  type: 'App',
  child: fiberHeader,      // 第一个子节点
  sibling: null,
  return: null,            // 根节点 return 为 null
};
const fiberHeader = {
  type: 'Header',
  child: null,
  sibling: fiberFooter,    // 下一个兄弟
  return: fiberApp,        // 指向父
};
const fiberFooter = { type: 'Footer', child: null, sibling: null, return: fiberApp };

// 为什么是链表？因为可以「走一步、歇一步」：
// 遍历到一半发现还有 5ms 空闲，就先让出主线程处理点击，
// 下一帧回来从 return 指针继续 —— 这就是可中断渲染的前提
function workLoop(fiber) {
  let work = fiber;
  while (work) {
    work = performUnitOfWork(work);   // 处理一个节点
  }
  return fiber;                       // 递归靠调用栈，链表靠指针 —— 调用栈不能暂停，指针可以
}

解析过程：递归依赖「调用栈」保存中间状态，而调用栈无法暂停/恢复；链表把状态显式存在指针里，所以可以随时让出、随时续走。这是「用链表替代递归」最经典的生产案例——面试问「Fiber 是什么」答到这个层面，直接碾压大多数候选人。

6.1 原理与 JS 的三个选择

// 哈希冲突：两个 key 落到同一个桶 → 用链地址法（桶里挂链表）
// 工程上 JS 引擎已处理，你只需要知道：冲突多了会退化成 O(n)

// WeakMap 经典场景：给 DOM 挂私有数据，节点删除后自动回收
const dataMap = new WeakMap();
function setData(el, data){ dataMap.set(el, data); }
function getData(el){ return dataMap.get(el); }

6.2 案例解析：手写 LRU 缓存（前端必考神题）★

LRU（最近最少使用）：容量满了，淘汰最久没用的。怎么做到 get/set 都 O(1)？哈希表负责 O(1) 查找，双向链表负责 O(1) 增删 + 记录访问顺序——这就是「哈希表 + 链表」的黄金组合。

class LRUCache {
  constructor(capacity){
    this.cap = capacity;
    this.map = new Map();        // Map 的插入顺序特性，天然支持 LRU 思想
  }
  get(key){
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key);        // 删掉再插 → 移到末尾 = 标记为「最近使用」
    this.map.set(key, v);
    return v;
  }
  put(key, value){
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.cap) {
      // 删除最早插入的（最久未使用）—— Map 迭代顺序即插入顺序
      this.map.delete(this.map.keys().next().value);
    }
  }
}
// 使用：模拟一个只能存 2 条数据的接口缓存
const cache = new LRUCache(2);
cache.put('user:1', {name:'张三'});
cache.put('user:2', {name:'李四'});
cache.get('user:1');        // 访问后 user:1 变「最近使用」
cache.put('user:3', {name:'王五'}); // 容量满 → 淘汰 user:2
cache.get('user:2');        // -1（已被淘汰）
console.log(cache.get('user:1'));  // {name:'张三'}（还活着）

解析过程：Map 的迭代顺序 = 插入顺序，所以「最久未使用」就是迭代的第一个元素。get 时先删再插，等于把元素「续命」到末尾。删除头部是 O(1)，查找是 O(1)——完美满足 LRU。生产上 React 的缓存、路由懒加载缓存、接口响应缓存，原理全一样。这道题面试命中率极高，值得背下来。

7.1 二叉树的四种遍历（前端必须闭眼能写）

// 先序：根→左→右   中序：左→根→右   后序：左→右→根   层序：逐层
function preorder(root, out = []) {           // 递归版
  if (!root) return out;
  out.push(root.value);
  preorder(root.left, out);
  preorder(root.right, out);
  return out;
}

// 层序遍历（BFS）用队列：虚拟 DOM 挂载时就是「先创建父，再创建子」
function levelOrder(root) {
  if (!root) return [];
  const q = [root], result = [];
  while (q.length) {
    const node = q.shift();                  // 出队父
    result.push(node.value);
    if (node.left)  q.push(node.left);       // 子入队（下一层）
    if (node.right) q.push(node.right);
  }
  return result;
}

7.2 案例解析：虚拟 DOM 的深度优先遍历

虚拟 DOM 就是一棵普通 JS 对象树。React 挂载、diff、commit 全部是深度优先遍历（先自己、再子树、后兄弟）：

// 一棵 vnode 树
const vnode = {
  type: 'div',
  props: { id: 'app' },
  children: [
    { type: 'h1', props: {}, children: ['Hello'] },
    { type: 'p', props: { className: 'desc' }, children: ['world'] },
  ],
};

// 把 vnode 树渲染成真实 DOM —— 本质就是先序 DFS
function createDom(vnode) {
  if (typeof vnode === 'string') return document.createTextNode(vnode);
  const el = document.createElement(vnode.type);
  for (const [k, v] of Object.entries(vnode.props || {})) {
    el.setAttribute(k, v);
  }
  vnode.children.forEach(c => el.appendChild(createDom(c))); // 递归子树
  return el;
}
// 层序遍历 vs 深度优先：DFS 代码简单、顺序天然（父先于子）；
// BFS 用于「按层级查找」（如 diff 时找同一层节点做复用判断）

解析过程：createDom 先创建自己（createElement），再递归子节点（appendChild 子树），这就是先序遍历。递归深度 = 树深度，树太深会爆栈（React 16 之前虚拟 DOM 递归 diff 就有这个问题，后来用 Fiber 链表迭代解决——第 5 节的呼应）。面试手写「vnode → DOM」「DOM → vnode」就是考树遍历。

8.1 手写最小堆（数组存二叉树，完全不用指针）

// 堆用数组存储：下标 i 的父 = (i-1)/2，左子 = 2i+1，右子 = 2i+2
class MinHeap {
  data = [];
  get size(){ return this.data.length; }
  peek(){ return this.data[0]; }

  push(v){
    this.data.push(v);
    this.#siftUp(this.data.length - 1);     // 新元素向上「浮」
  }
  pop(){                                     // 弹出最小值
    if (!this.size) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.size) { this.data[0] = last; this.#siftDown(0); } // 末尾顶上来，向下「沉」
    return top;
  }
  #siftUp(i){
    while (i > 0) {
      const p = (i - 1) >> 1;              // 父节点下标
      if (this.data[p] <= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  #siftDown(i){
    const n = this.size;
    while (true) {
      let min = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l] < this.data[min]) min = l;
      if (r < n && this.data[r] < this.data[min]) min = r;
      if (min === i) break;
      [this.data[i], this.data[min]] = [this.data[min], this.data[i]];
      i = min;
    }
  }
}
// 使用
const h = new MinHeap();
[5,3,8,1,9].forEach(x => h.push(x));
console.log(h.pop()); // 1，永远先出最小的
console.log(h.pop()); // 3

解析过程：push 把元素放数组末尾，然后不断和父节点比大小往上浮（siftUp）；pop 把根（最小）取走，用末尾元素补位，再往下沉（siftDown）恢复堆序。每条路径长度是树高 log n，所以插入/删除都是 O(log n)——比「每次排序取最小」的 O(n log n) 快一个量级。

8.2 案例解析：Top K 问题（性能监控前 10 条慢请求）

// 从海量耗时数据里找最慢的 10 条：维护一个容量 10 的最小堆
// 堆满后，新数据只要比堆顶(当前第10慢)快就丢弃，比它慢就替换
function topK(items, k = 10) {
  const heap = new MinHeap();
  for (const item of items) {
    if (heap.size < k) heap.push(item);
    else if (item.cost > heap.peek().cost) {  // 比堆顶慢才值得留
      heap.pop();
      heap.push(item);
    }
  }
  // 堆里剩下的就是最慢的 k 条（顺序不定，要排序就再排一下）
  return heap.data.sort((a, b) => b.cost - a.cost);
}
// 100 万条日志只维护 10 个元素 → O(n log k) ≈ O(n)，内存 O(k)

解析过程：如果用「全部排序取前 10」，100 万条要 O(n log n)；用容量为 k 的堆，只淘汰最弱的，复杂度 O(n log k)。日志量大时这差距就是「秒级」和「毫秒级」。同样的思路：任务调度器按优先级取任务（BFS/定时器小顶堆）、中位数维护（双堆）、推荐系统 topN。

9.1 图的两种存法：邻接表（前端几乎只用它）

// 邻接表：每个节点 → 它的邻居列表（用 Map 存）
// a 依赖 b、c；b 依赖 d；c 依赖 d
const graph = new Map([
  ['a', ['b', 'c']],
  ['b', ['d']],
  ['c', ['d']],
  ['d', []],
]);
// 图遍历（visited 防死循环）：
function bfs(graph, start) {            // 广度优先：用队列
  const visited = new Set([start]), q = [start], out = [];
  while (q.length) {
    const node = q.shift();
    out.push(node);
    for (const nb of graph.get(node) || []) {
      if (!visited.has(nb)) { visited.add(nb); q.push(nb); }
    }
  }
  return out;
}
console.log(bfs(graph, 'a')); // ['a','b','c','d']

9.2 案例解析：模块依赖拓扑排序（mini webpack 核心）

webpack 要决定模块打包顺序：被依赖的模块必须先执行（d 在 b 前）。这就是拓扑排序——Kahn 算法：每次取出「没有未完成依赖」的节点。

// 入度 = 还有几个依赖没处理完。入度 0 的节点可以立即执行
function topoSort(graph) {
  const indegree = new Map();          // 节点 → 入度
  for (const [node, deps] of graph) indegree.set(node, 0);
  for (const [, deps] of graph) for (const d of deps)
    indegree.set(d, (indegree.get(d) || 0) + 1);

  const q = [...indegree].filter(([, d]) => d === 0).map(([n]) => n);
  const order = [];
  while (q.length) {
    const node = q.shift();
    order.push(node);
    for (const nb of graph.get(node) || []) {
      indegree.set(nb, indegree.get(nb) - 1);  // 依赖少了一个
      if (indegree.get(nb) === 0) q.push(nb);  // 入度归零 → 可执行
    }
  }
  // 如果 order 长度 < 节点数 → 存在循环依赖！
  return order.length === indegree.size ? order : null;
}
console.log(topoSort(graph));
// ['d','b','c','a']：d 最先，a 最后 —— 依赖先于被依赖执行 ✅

解析过程：① 统计每个节点入度（被几个节点依赖）；② 入度为 0 的入队（它们没有前置依赖，先执行）；③ 出队一个，把它「下游」的入度减 1，减到 0 说明下游的所有前置都完成了，入队；④ 循环到队列空。若最后处理的节点数不等于总数 → 有环（循环依赖），工程上直接报错（webpack 的 Circular dependency 警告）。构建工具、npm 安装顺序、TypeScript 编译依赖、路由守卫顺序全是它。

10.1 手写 Trie（60 行内）

// 每个节点只存两个东西：子节点表 + 是否是单词结尾
class TrieNode {
  children = new Map();   // 字符 → 子节点
  isEnd = false;
}
class Trie {
  root = new TrieNode();
  insert(word){
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;                    // 标记这是一个完整词
  }
  // 返回前缀最后一个节点（前缀不存在返回 null）
  #find(prefix){
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
  search(word){                           // 完整匹配
    const node = this.#find(word);
    return !!node && node.isEnd;
  }
  startsWith(prefix){ return !!this.#find(prefix); }
  // 联想：收集以 prefix 开头的所有词
  suggest(prefix, limit = 8){
    const node = this.#find(prefix);
    if (!node) return [];
    const out = [];
    const dfs = (n, cur) => {
      if (out.length >= limit) return;
      if (n.isEnd) out.push(cur);
      for (const [ch, child] of n.children) dfs(child, cur + ch);
    };
    dfs(node, prefix);
    return out;
  }
}
// 使用：输入 "app" 联想出 "apple" "apply"
const t = new Trie();
['apple','apply','apt','apartment','book'].forEach(w => t.insert(w));
console.log(t.startsWith('app')); // true
console.log(t.suggest('app'));    // ['apple','apply','apartment']

10.2 案例解析：搜索框防抖 + Trie 联想（真实交互）

// ① Trie 里存全量词库（如商品名）
// ② 输入时防抖 300ms 再联想，避免每次按键都全量过滤
function debounce(fn, delay = 300) {
  let timer;
  return (...args) => {
    clearTimeout(timer);
    timer = setTimeout(() => fn(...args), delay);
  };
}
const input = document.querySelector('#search');
const onInput = debounce((e) => {
  const kw = e.target.value.trim();
  // 词库 10 万条：filter 全扫 O(n) vs Trie 联想 O(词长) —— 量级差 10⁴ 倍
  const list = trie.suggest(kw, 10);
  renderSuggest(list);
});
input.addEventListener('input', onInput);

// 敏感词过滤：把敏感词建成 Trie，扫描文本时顺着 Trie 走，
// 命中 isEnd 就替换 —— 比 indexOf 逐个查快一个量级

解析过程：不用 Trie 的联想是「全词库 filter」——每次输入都遍历 10 万条，O(n)；Trie 只沿着输入字符走，复杂度 = 输入长度 O(m)，m 通常 < 10。输入「app」时只有 3 步查找 + 深度优先收集。空间换时间的极致体现：每个公共前缀只存一份。

11.1 实战一：接口缓存 LRU + 过期时间（哈希表 + 链表思想）

需求：业务请求同一个接口时先查缓存，缓存最多 50 条，超 30 秒过期，满了淘汰最久未用的。数据结构：Map（LRU 思想见 6.2）+ 时间戳。

class ApiCache {
  constructor(capacity = 50, ttl = 30_000){
    this.cap = capacity; this.ttl = ttl;
    this.map = new Map();          // key → {data, time}
  }
  async get(key, fetcher){
    const hit = this.map.get(key);
    if (hit && Date.now() - hit.time < this.ttl) {
      // 命中：续命（LRU）
      this.map.delete(key); this.map.set(key, hit);
      return hit.data;
    }
    const data = await fetcher();  // 未命中/过期：真实请求
    this.map.set(key, { data, time: Date.now() });
    if (this.map.size > this.cap) this.map.delete(this.map.keys().next().value);
    return data;
  }
  clear(){ this.map.clear(); }     // 退出登录/切换账号时调用
}
// 使用
const userCache = new ApiCache(50, 30_000);
const user = await userCache.get('/api/user', () => fetchUser());

验证：连续调 3 次 get，只有第 1 次真正发请求（fetcher 打点验证）；第 2 次命中缓存立即返回。这就是线上「接口缓存层」的最小实现，接上 staleTime 概念就是 React Query 的雏形。

11.2 实战二：极简虚拟 DOM diff（树的先序比较）

需求：两棵 vnode 树（旧树/新树），输出差异列表。数据结构：树 + 递归 DFS（真实 React 还有 key 复用和 Fiber，这里讲清骨架）。

// 简化版：同层递归比较，只处理「文本节点变化」和「子节点增删」
function diff(oldNode, newNode, patch = [], path = []) {
  // 情况1：节点类型都变了 → 整个替换
  if (!oldNode || oldNode.type !== newNode.type) {
    patch.push({ op: 'replace', path, node: newNode });
    return patch;
  }
  // 情况2：都是文本节点，内容变了 → 更新文本
  if (typeof oldNode === 'string' && typeof newNode === 'string') {
    if (oldNode !== newNode) patch.push({ op: 'text', path, value: newNode });
    return patch;
  }
  // 情况3：遍历子节点，逐个递归比较（真实实现按 key 复用）
  const max = Math.max(oldNode.children.length, newNode.children.length);
  for (let i = 0; i < max; i++) {
    const oldChild = oldNode.children[i];
    const newChild = newNode.children[i];
    if (newChild && !oldChild) {
      patch.push({ op: 'insert', path: [...path, i], node: newChild });
    } else if (oldChild && !newChild) {
      patch.push({ op: 'remove', path: [...path, i] });
    } else {
      diff(oldChild, newChild, patch, [...path, i]);
    }
  }
  return patch;
}
// 用 7.2 的 vnode 结构跑一下：改一行文本，得到一条 text patch

验证：把旧树 children[0].children[0] 从 'Hello' 改成 'Hi'，diff 返回 [{op:'text', path:[0,0], value:'Hi'}]——应用 patch 时只更新那个文本节点，不重建整棵树。这就是「最小化 DOM 操作」的来源，也是面试手写 diff 的标准答案骨架。

11.3 实战三：mini 依赖图打包器（图 + 拓扑排序）

需求：解析模块的 import 关系，按依赖顺序输出「先被依赖后依赖」的模块执行顺序。数据结构：图（邻接表）+ Kahn 拓扑排序。

// 模拟模块依赖：a import 了 b、c；b import 了 d；c import 了 d
const modules = {
  a: { deps: ['b', 'c'] },
  b: { deps: ['d'] },
  c: { deps: ['d'] },
  d: { deps: [] },
};

function buildGraph(mods) {
  const graph = new Map();
  for (const name of Object.keys(mods)) graph.set(name, mods[name].deps);
  return graph;
}

// 复用 9.2 的 topoSort —— 构建工具的打包顺序 = 拓扑序
const order = topoSort(buildGraph(modules));
console.log(order); // ['d','b','c','a'] 或 ['d','c','b','a']
// 执行时按 order 逐个包进闭包：d 先定义，a 最后执行 —— 引用关系永不悬空

验证：如果给 modules 加一个循环依赖 d: { deps: ['a'] }，topoSort 返回 null（order.length !== 节点数）——打包器就会抛「Circular dependency」错误。真实 webpack 的 warning 就是这个检测。

12.1 八种结构复杂度速查

12.2 选型决策树：遇到问题先问四个问题

一句话总结：找最值用堆，找 key 用哈希，看层级用树，管依赖用图，追顺序用栈/队列，省空间省时间看取舍。

• 在循环里 shift() 当队列用 → O(n²)。100 条还好，1 万条就卡。用下标指针或双数组队列（4.1）。
• 用 indexOf 判存在 → 应该用 Set。10 万条数据里 filter 判重，Set 快几百倍。
• 以为对象就是哈希表 → 忘记原型链。obj['constructor'] 会命中原型！用 Object.create(null) 或 Map。
• Map 当 LRU 用，忘了删除再插入 = 没续命。get 时必须 delete + set 才能刷新「最近使用」。
• 递归遍历树，树深 5000+ 直接爆栈。RangeError: Maximum call stack。深层数据用迭代 + 显式栈/队列。
• Vue/React 列表 key 用 index。中间插入/删除时复用错乱。key 要用稳定唯一 id（哈希思想）。
• Set/Map 里存了引用类型 → 内存泄漏。不该被长期引用的数据用 WeakMap/WeakSet。
• 堆排序/建堆时下标算错。父 (i-1)/2、左子 2i+1、右子 2i+2，抄错一个全乱，写的时候画棵树验证。
• 图遍历忘了 visited → 死循环/爆栈。有环图必须记录访问过的节点，BFS/DFS 模板第一行先建 visited。
• sort 默认按字符串排！[10,9,100].sort() → [10,100,9]。数字排序必须 sort((a,b)=>a-b)，这是前端第一坑。