# 堆栈和队列的应用

关于栈和队列的实际应用比比皆是：

浏览器的历史记录，因为回退总是回退“上一个”最近的页面，它需要遵循栈的原则；
类似浏览器的历史记录，任何 Undo/Redo 都是一个栈的实现；
在代码中，广泛应用的递归产生的调用栈，同样也是栈思想的体现，想想我们常说的“栈溢出”就是这个道理；
同上，浏览器在抛出异常时，常规都会抛出调用栈信息；
在计算机科学领域应用广泛，如进制转换、括号匹配、栈混洗、表达式求值等；
队列的应用更为直观，我们常说的宏任务/微任务都是队列，不管是什么类型的任务，都是先进先执行；
后端也应用广泛，如消息队列、RabbitMQ、ActiveMQ 等，能起到延迟缓冲的功效。

另外，与性能话题相关，HTTP 1.1 有一个队头阻塞的问题，而原因就在于队列这样的数据结构的特点。具体来说，在 HTTP 1.1 中，每一个链接都默认是长链接，因此对于同一个 TCP 链接，HTTP 1.1 规定：服务端的响应返回顺序需要遵循其接收到相应的顺序。但这样存在一个问题：如果第一个请求处理需要较长时间，响应较慢，将会“拖累”其他后续请求的响应，这是一种队头阻塞。

HTTP 2 采用了二进制分帧和多路复用等方法，同域名下的通信都在同一个连接上完成，在这个连接上可以并行请求和响应，而互不干扰。

在框架层面，堆栈和队列的应用更是比比皆是。比如 React 的 Context 特性，参考以下代码

import React from "react";
const ContextValue = React.createContext();
export default function App() {
  return (
    <ContextValue.Provider value={1}>
      <ContextValue.Consumer>
        {(value1) => (
          <ContextValue.Provider value={2}>
            <ContextValue.Consumer>
              {(value2) => (
                <span>
                  {value1}-{value2}
                </span>
              )}
            </ContextValue.Consumer>
          </ContextValue.Provider>
        )}
      </ContextValue.Consumer>
    </ContextValue.Provider>
  );
}

@前端进阶之旅: 代码已经复制到剪贴板

对于以上代码，React 内部就是通过一个栈结构，在构造 Fiber 树时的 beginWork 阶段，将 Context.Provider 数据状态入栈（此时 value1：1 和 value2：2 分别入栈），在 completeWork 阶段，将栈中的数据状态出栈，以供给 Context.Consumer 消费。关于 React 源码中，栈的实现，你可以参考这部分源码(https://github.com/facebook/react/blob/master/packages/react-reconciler/src/ReactFiberStack.old.js)

# 链表的应用

React 的核心算法Fiber 的实现就是链表。React 最早开始使用大名鼎鼎的 Stack Reconciler 调度算法，Stack Reconciler 调度算法最大的问题在于：它就像函数调用栈一样，递归地、自顶向下进行 diff 和 render 相关操作，在 Stack Reconciler 执行的过程中，该调度算法始终会占据浏览器主线程。也就是说在此期间，用户的交互所触发的布局行为、动画执行任务都不会得到立即响应，从而影响用户体验。

因此 React Fiber 将渲染和更新过程进行了拆解，简单来说，就是每次检查虚拟 DOM 的一小部分，在检查间隙会检查“是否还有时间继续执行下一个虚拟 DOM 树上某个分支任务”，同时观察是否有更优先的任务需要响应。如果“没有时间执行下一个虚拟 DOM 树上某个分支任务”，且某项任务有更高优先级，React 就会让出主线程，直到主线程“不忙”的时候继续执行任务。

React Fiber 的实现也很简单，它将 Stack Reconciler 过程分成块，一次执行一块，执行完一块需要将结果保存起来，根据是否还有空闲的响应时间（requestIdleCallback）来决定下一步策略。当所有的块都已经执行完，就进入提交阶段，这个阶段需要更新 DOM，它是一口气完成的。

以上是比较主观的介绍，下面我们来看更具体的实现。

为了达到“随意中断调用栈并手动操作调用栈”，React Fiber 专门用于 React 组件堆栈调用的重新实现，也就是说一个 Fiber 就是一个虚拟堆栈帧，一个 Fiber 的结构类似：

function FiberNode(
  tag: WorkTag,
  pendingProps: mixed,
  key: null | string,
  mode: TypeOfMode,
) {
  // Instance
  // ...
  this.tag = tag;                       
  // Fiber
  this.return = null;
  this.child = null;
  this.sibling = null;
  this.index = 0;
  this.ref = null;
  this.pendingProps = pendingProps;
  this.memoizedProps = null;
  this.updateQueue = null;
  this.memoizedState = null;
  this.dependencies = null;
  // Effects
  // ...
  this.alternate = null; 
}

@前端进阶之旅: 代码已经复制到剪贴板

这么看Fiber 就是一个对象，通过 parent、children、sibling 维护一个树形关系，同时 parent、children、sibling 也都是一个 Fiber 结构，FiberNode.alternate 这个属性来存储上一次渲染过的结果，事实上整个 Fiber 模式就是一个链表。React 也借此，从依赖于内置堆栈的同步递归模型，变为具有链表和指针的异步模型了。

具体的渲染过程：

function renderNode(node) {
   // 判断是否需要渲染该节点，如果 props 发生变化，则调用 render
   if (node.memoizedProps !== node.pendingProps) {
      render(node)
   }
   // 是否有子节点，进行子节点渲染
   if (node.child !== null) {
      return node.child
   // 是否有兄弟节点，进行兄弟点渲染
   } else if (node.sibling !== null){
      return node.sibling
   // 没有子节点和兄弟节点
   } else if (node.return !== null){
      return node.return
   } else {
      return null
   }
}
function workloop(root) {
   nextNode = root
   while (nextNode !== null && (no other high priority task)) {
      nextNode = renderNode(nextNode)
   }
}

@前端进阶之旅: 代码已经复制到剪贴板

注意在 Workloop 当中，while 条件 nextNode !== null && (no other high priority task)，这是描述 Fiber 工作原理的关键伪代码。

在 Fiber 之前，React 递归遍历虚拟 DOM，在遍历过程中找到前后两颗虚拟 DOM 的差异，并生成一个 Mutation。这种递归遍历有一个局限性：每次递归都会在栈中添加一个同步帧，因此无法将遍历过程拆分为粒度更小的工作单元，也就无法暂停组件的更新，并在未来的某段时间恢复更新。

# 树的应用

从应用上来看，我们前端开发离不开的 DOM 就是一个树状结构；同理，不管是 React 还是 Vue 的虚拟 DOM 也都是树

上文中我们提到了 React Element 树和 Fiber 树，React Element 树其实就是各级组件渲染，调用 React.createElement 返回 React Element 之后（每一个 React 组件，不管是 class 组件或 functional 组件，调用一次 render 或执行一次 function，就会生成 React Element 节点）的总和。

React Element 树和 Fiber 树是在 reconciler 过程中，相互交替，逐级构造进行的。这个生成过程，就采用了 DFS 遍历，主要源码位于 ReactFiberWorkLoop.js 中。我这里进行简化，你可以清晰看到 DFS 过程：

function workLoopSync() {
  // 开始循环
  while (workInProgress !== null) {
    performUnitOfWork(workInProgress);
  }
}
function performUnitOfWork(unitOfWork: Fiber): void {
  const current = unitOfWork.alternate;
  let next;
  // beginWork 阶段，向下遍历子孙组件
  next = beginWork(current, unitOfWork, subtreeRenderLanes);
  if (next === null) {
    // completeUnitOfWork 是向上回溯树阶段
    completeUnitOfWork(unitOfWork);
  } else {
    workInProgress = next;
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

另外，React 中，当 context 数据状态改变时，需要找出依赖该 context 数据状态的所有子节点，以进行状态变更和渲染。这个过程，也是一个 DFS，源码你可以参考 ReactFiberNewContext.js(https://github.com/facebook/react/blob/v17.0.1/packages/react-reconciler/src/ReactFiberNewContext.old.js#L182-L295)。

# 字典树（Trie）

字典树（Trie）是针对特定类型的搜索而优化的树数据结构。典型的例子是 AutoComplete（自动填充），也就是说它适合实现“通过部分值得到完整值”的场景。因此字典树也是一种搜索树，我们有时候也叫作前缀树，因为任意一个节点的后代都存在共同的前缀

我们总结一下它的特点：

字典树能做到高效查询和插入，时间复杂度为 O(k)，k 为字符串长度；
但是如果大量字符串没有共同前缀，就很耗内存，你可以想象一下最极端的情况，所有单词都没有共同前缀时，这颗字典树会是什么样子；
字典树的核心就是减少不必要的字符比较，提高查询效率，也就是说用空间换时间，再利用共同前缀来提高查询效率。

字典树还有很多其他应用场景

搜索
分类
IP 地址检索
电话号码检索

字典树的实现也不复杂，我们可以一步步来，首先实现一个字典树上的节点，如下代码

class PrefixTreeNode {
  constructor(value) {
    // 存储子节点
    this.children = {}
    this.isEnd = null
    this.value = value
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

一个字典树继承 PrefixTreeNode 类，如下代码：

我们可以通过下述方法实现：

总结

JS数据结构应用场景|算法篇

JS数据结构应用场景|算法篇