栈、队列和树：在前端需求里认出背后的数据结构

2019-07-16

栈、队列、树最容易被学成一堆定义：后进先出、先进先出、层级结构。定义当然没错，但只背这些，写需求时还是很难主动认出它们。直到一个需求要做撤销、一个需求要控并发上传、一个需求要把扁平数据还原成层级结构时，你才会发现，项目里天天都在用这些东西，只是平时没把它们叫出名字。

这一批需求正好把三种结构凑齐了：优惠券模块要把带 parentId 的扁平数组组装成类目树；商品管理的批量传图不能一股脑把几十个请求同时打出去；活动配置器要支持撤销和回退。三个问题放在一起看，栈、队列、树一下子就从书本名词变成了具体工具。

后面不按课本目录讲，而是按它们在前端代码里真实出现的样子来讲：撤销为什么像栈，并发控制为什么像队列，菜单、类目、组件和虚拟 DOM 为什么本质上都是树。

栈：后进先出，撤销和回溯的本质

栈的规则一句话：后进先出（LIFO），最后放进去的最先拿出来。JS 里压根不需要专门实现一个栈类，一个数组配 push 和 pop 就是现成的栈。

控制台直接验证：

1var stack = []
2stack.push('a')
3stack.push('b')
4console.log(stack)       // ['a', 'b']
5console.log(stack.pop()) // 'b' ← 最后进的最先出
6console.log(stack)       // ['a']

最容易理解的例子是函数调用栈。递归忘了写终止条件，浏览器报 Maximum call stack size exceeded，那个 stack 就是调用栈——每调一层函数压一个帧进去，函数返回再弹出来，爆栈就是压进去的没机会弹出来，把空间撑满了。浏览器的前进后退、编辑器的撤销重做，本质也都是栈。

括号匹配：我被测试逮住的那次

去年我做过一个简易的公式编辑器，要校验用户输入的括号是不是配对的，这是栈的经典用法：

1function isValid(text) {
2  var stack = []
3  var pairs = {
4    ')': '(',
5    ']': '[',
6    '}': '{'
7  }
8
9  for (var i = 0; i < text.length; i++) {
10    var char = text[i]
11
12    if (char === '(' || char === '[' || char === '{') {
13      // 左括号一律入栈
14      stack.push(char)
15    } else if (pairs[char]) {
16      // 遇到右括号，看栈顶是不是它对应的左括号
17      if (stack.pop() !== pairs[char]) {
18        return false
19      }
20    }
21  }
22
23  // 全部匹配完，栈应该是空的
24  return stack.length === 0
25}
26
27isValid('([]{})') // true
28isValid('([)]')   // false，顺序错了
29isValid('(()')    // false，最后栈里还剩一个 (

这里有个我当年栽过的坑：只判断左右括号数量相等是不够的。([)] 左右括号各两个，数量对，但顺序是错的。必须用栈才能保证「最近打开的最先关闭」这个嵌套关系。我最初的版本就是数数量，用户输入 [(]) 也判过了，被测试同学逮个正着。

撤销重做：一个栈不够，要两个

这个月活动页配置器要加撤销功能，我第一版只维护了一个历史栈，每次操作 push 一份状态快照，Ctrl+Z 就 pop。演示时产品顺口问了句「那撤销错了怎么办」，我才发现少了重做。撤销重做的标准做法是双栈：撤销时从 undo 栈弹出来的状态，要压进 redo 栈；一旦产生新操作，redo 栈整个清空——因为历史已经分叉，被撤销掉的未来不作数了：

1var undoStack = []
2var redoStack = []
3
4function doAction(newState) {
5  undoStack.push(currentState)
6  currentState = newState
7  redoStack = [] // 新操作产生，重做历史作废
8}
9
10function undo() {
11  if (!undoStack.length) return
12  redoStack.push(currentState)
13  currentState = undoStack.pop()
14}
15
16function redo() {
17  if (!redoStack.length) return
18  undoStack.push(currentState)
19  currentState = redoStack.pop()
20}

另外快照别无限存，配置器一个操作一份快照，用户拖一下午内存就炸了。我限制了 undo 栈最多 50 步，超了就从栈底丢——数组当栈用的好处这时候体现出来，shift 一下就行。

栈的思路还能往外延伸：面包屑导航的「返回上一级」、简单的状态回退，都可以每进一层 push、每退一步 pop。再比如把递归改成迭代——递归本质就是在用系统的调用栈，当数据层级太深可能爆栈时，可以自己拿一个数组当栈手动模拟，这点后面讲树的遍历会用到。

队列：先进先出，控制并发的利器

队列跟栈正好相反，先进先出（FIFO），像排队买奶茶，先来的先被服务。数组用 push 进队、shift 出队：

1var queue = []
2
3queue.push('task1')
4queue.push('task2')
5
6console.log(queue.shift()) // task1
7console.log(queue.shift()) // task2

批量上传：这个月刚交的作业

商品管理的批量传图就是队列救的场。运营一次选几十张图，如果一股脑全发出去，浏览器对同一域名的并发连接本来就有上限（一般 6 个），剩下的请求全在那干等，而且后端也扛不住——测试环境的图片服务直接被我们打出了一串 502。正确做法是维护一个等待队列，同时只跑固定数量的请求，跑完一个就从队列里取下一个补上：

1function runWithLimit(tasks, limit) {
2  return new Promise(function (resolve) {
3    var results = []
4    var index = 0      // 下一个要取的任务下标
5    var running = 0    // 当前正在跑的数量
6    var finished = 0   // 已完成的数量
7
8    function next() {
9      // 队列空了且都跑完了，整体结束
10      if (finished === tasks.length) {
11        resolve(results)
12        return
13      }
14      // 只要还有空位、还有没派发的任务，就继续派
15      while (running < limit && index < tasks.length) {
16        var current = index++
17        running++
18        tasks[current]().then(function (res) {
19          results[current] = res
20        }).catch(function (err) {
21          results[current] = err
22        }).then(function () {
23          running--
24          finished++
25          next() // 腾出一个空位，立刻补一个
26        })
27      }
28    }
29
30    next()
31  })
32}
33
34// 用法：tasks 是一组返回 Promise 的函数
35var tasks = files.map(function (file) {
36  return function () { return uploadImage(file) }
37})
38
39runWithLimit(tasks, 3).then(function (results) {
40  console.log('全部完成', results)
41})

这里有两个细节是我踩过坑才记住的。一是 tasks 里存的得是「返回 Promise 的函数」，不能直接存 Promise，因为 Promise 一创建就立刻执行了，那样所谓的并发限制根本拦不住，请求早就全发出去了。二是 results[current] = res 用下标存，是为了保证结果顺序跟输入一致——队列是先进先出，但每个请求的耗时不一样，回来的顺序是乱的，靠下标对齐才不会错位。

消息队列：事件循环排的就是这个

再说个更底层的呼应：浏览器的事件循环里，宏任务（setTimeout、事件回调、消息）排的就是一个任务队列，一个一个先进先出地执行。理解了队列，再看事件循环为什么是那个顺序会顺很多。更进一步，每个宏任务执行完，还要把微任务队列（Promise.then、MutationObserver）整个清空才轮到下一个宏任务，所以才有那道经典输出题：

1setTimeout(function () { console.log('macro') }, 0)
2Promise.resolve().then(function () { console.log('micro') })
3console.log('sync')
4// 输出：sync → micro → macro

setTimeout(fn, 0) 是排到宏任务队列尾，then 是排到当前这轮的微任务队列——两个队列，插队规则不同。这道题我年初补事件循环笔记时背过结论，现在从「两个 FIFO 队列 + 微任务优先清空」的角度想，不用背也推得出来。跟后端联调时他们嘴里的「消息队列」（他们用 RabbitMQ 削峰）也是同一个思想：生产快、消费慢，中间垫一个 FIFO 缓冲，谁先来谁先被处理。前端的并发上传队列，其实就是这套思想的迷你版。

树：层级关系的天然表达

前端遇到的层级数据基本都是树：左侧菜单、商品类目、组织部门、多级评论、文件目录、路由配置、省市区三级联动。树的特点是每个节点可以有若干子节点，从根一路往下分叉。

JS 里表达树通常就是对象嵌 children 数组：

1var tree = [
2  {
3    id: 1,
4    name: '系统管理',
5    children: [
6      {
7        id: 2,
8        name: '用户管理',
9        children: [
10          { id: 4, name: '新增用户' },
11          { id: 5, name: '删除用户' }
12        ]
13      },
14      { id: 3, name: '角色管理' }
15    ]
16  }
17]

递归遍历

遍历树最自然的方式是递归，因为树本身就是递归定义的——一棵树的子节点又是一棵子树：

1function walk(nodes, callback) {
2  nodes.forEach(function (node) {
3    callback(node)
4    if (node.children && node.children.length) {
5      walk(node.children, callback)
6    }
7  })
8}
9
10walk(tree, function (node) {
11  console.log(node.name)
12})

这是深度优先（DFS）——一条路走到黑再回头。想按层级一层层扫（广度优先 BFS），就该把队列请出来了，正好把前面两个结构串起来：

1function walkByLevel(nodes, callback) {
2  var queue = nodes.slice() // 拷一份，别污染原数组
3  while (queue.length) {
4    var node = queue.shift()
5    callback(node)
6    if (node.children) {
7      // 子节点排到队尾，保证先把同一层处理完
8      queue.push.apply(queue, node.children)
9    }
10  }
11}

菜单里查找「某个 id 对应的节点」我一般用 DFS 递归；要做「默认展开到第二层」这种按深度的操作，BFS 更顺手。顺带一句，如果树深到几千层（比如异常的脏数据），递归可能爆栈，这时候就得用「拿数组当栈/队列」的迭代写法代替递归——栈那节埋的伏笔在这儿收回来。

按条件过滤子树

去年那个权限菜单的需求——按角色把没权限的节点连同子树砍掉——正是树的递归威力所在，几行搞定：

1function filterTree(nodes, predicate) {
2  var result = []
3  nodes.forEach(function (node) {
4    if (predicate(node)) {
5      var copy = Object.assign({}, node)
6      if (node.children) {
7        // 递归过滤子节点
8        copy.children = filterTree(node.children, predicate)
9      }
10      result.push(copy)
11    }
12  })
13  return result
14}
15
16var allowedIds = { 1: true, 2: true, 4: true }
17var menu = filterTree(tree, function (node) {
18  return allowedIds[node.id]
19})

当年我用嵌套循环写这功能写了一百多行，换成递归就十几行，改需求只改 predicate 一处。这就是认出「它是棵树」之后的差别。这个月类目树选择器的「按可售状态过滤类目」，我直接把这个函数搬了过去，predicate 换一下完事。

天天在用的那两棵树：组件树和虚拟 DOM

补笔记时我发现一件有点好笑的事：我天天写 Vue，其实一直泡在两棵树里而不自知。一棵是组件树——根组件往下嵌套子组件，Vue 实例上的 $parent、$children、$root 就是在树上爬。有次我要从页面级组件里找某个深层的表格子组件，写的就是一个标准 DFS：

1function findComponent(vm, name) {
2  var children = vm.$children
3  for (var i = 0; i < children.length; i++) {
4    if (children[i].$options.name === name) {
5      return children[i]
6    }
7    var found = findComponent(children[i], name) // 递归下钻
8    if (found) return found
9  }
10  return null
11}

另一棵是虚拟 DOM。render 函数产出的 VNode 就是一棵树，每个节点带 tag、data、children；所谓 diff，就是新旧两棵 VNode 树的同层比较——Vue 和 React 都不做跨层级比较，因为完整的树编辑距离算法开销太大，同层比对把复杂度压到了 O(n)。这也解释了为什么列表要写 key：同层的一排子节点，没有 key 时只能按下标硬对，有 key 才能认出「这个节点只是挪了位置」。读到这层我才觉得数据结构这课没白补——框架文档里让你背的规则，在数据结构层面都有个「不这么做就慢」的理由。

二叉树的前 / 中 / 后序：还一月的债

前端的树大多是「任意多个 children」，但教材必讲的是二叉树的三种深度优先遍历——就是一月分享会上让我支支吾吾的那道。三种遍历的差别只在「什么时候访问根节点」，拿这棵小树验证最直观：

1var tree = { v: 1, l: { v: 2, l: { v: 4 }, r: { v: 5 } }, r: { v: 3 } }
2
3function preOrder(n, out) {   // 根 → 左 → 右
4  if (!n) return out
5  out.push(n.v)
6  preOrder(n.l, out)
7  preOrder(n.r, out)
8  return out
9}
10function inOrder(n, out) {     // 左 → 根 → 右
11  if (!n) return out
12  inOrder(n.l, out)
13  out.push(n.v)
14  inOrder(n.r, out)
15  return out
16}
17function postOrder(n, out) {   // 左 → 右 → 根
18  if (!n) return out
19  postOrder(n.l, out)
20  postOrder(n.r, out)
21  out.push(n.v)
22  return out
23}
24
25console.log(preOrder(tree, []))  // [1, 2, 4, 5, 3]
26console.log(inOrder(tree, []))   // [4, 2, 5, 1, 3]
27console.log(postOrder(tree, [])) // [4, 5, 2, 3, 1]

三种顺序里只有「访问根」那一句的位置在变，其余完全一样——记住这个就不用死背遍历结果了。要是一月分享会上我能说出这句，当时台下提问的那位同事大概不会是那个表情。

扁平数组转树：后台接口的常客

回到这个月的类目树选择器。接口为了方便存数据库，返回的不是嵌套树，而是带 parentId 的扁平数组：

1var list = [
2  { id: 1, parentId: 0, name: '系统管理' },
3  { id: 2, parentId: 1, name: '用户管理' },
4  { id: 3, parentId: 1, name: '角色管理' },
5  { id: 4, parentId: 2, name: '新增用户' }
6]

转成树最容易想到的是双重循环：对每个节点遍历一遍找它的孩子，时间复杂度 O(n²)。数据量小无所谓，但类目数据几千条，我去年碰过一次同量级的省市区数据，页面卡了一下肉眼可见。更好的做法是先用一个 map 把 id 映射到节点，再一遍循环把每个节点挂到它父亲下面，整体 O(n)：

1function listToTree(list) {
2  var map = {}
3  var roots = []
4
5  // 第一遍：建立 id -> 节点 的索引，顺便给每个节点加上 children
6  list.forEach(function (item) {
7    map[item.id] = Object.assign({}, item, { children: [] })
8  })
9
10  // 第二遍：根据 parentId 挂到父节点下
11  list.forEach(function (item) {
12    var node = map[item.id]
13    if (item.parentId === 0) {
14      roots.push(node)
15    } else if (map[item.parentId]) {
16      map[item.parentId].children.push(node)
17    } else {
18      // 父节点不存在，说明是脏数据，当成根处理，别让它凭空消失
19      roots.push(node)
20    }
21  })
22
23  return roots
24}

最后那个 else 分支是我加的「保命」逻辑。早先我没写它，结果有一条数据的 parentId 指向一个已经被删掉的父节点，那个节点和它整棵子树直接从界面上消失了，排查半天才发现是数据的锅。宁可把它当根节点露出来让人看见异常，也别让它静默丢失。

反过来，树转扁平数组也偶尔要用，比如把树形数据传给一个只认平铺列表的组件。直接复用前面的 walk 就行：

1function treeToList(nodes) {
2  var list = []
3  walk(nodes, function (node) {
4    var copy = Object.assign({}, node)
5    delete copy.children
6    list.push(copy)
7  })
8  return list
9}

flag 还了一角

笔记补完，再回看这两周的三个需求：撤销靠栈，批量上传的并发控制靠队列，类目、菜单、评论、组件、虚拟 DOM 全是树。这些结构真正的用处，是让你能在一坨需求里认出背后的形状。一旦认出来，原本要堆几百行 if-else 的活，常常十几行递归就解决了；认不出来，就是我去年那一百多行三层循环。

把这三个结构的「脾气」记牢：栈是后进先出、队列是先进先出、树是递归的。下次再碰到嵌套数据或者要排队执行的场景，先别急着撸循环，想想它是不是其中之一。补基础的 flag 今年才还了一角，下一个专题接着写。