# 堆栈和队列的应用

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

• 浏览器的历史记录，因为回退总是回退“上一个”最近的页面，它需要遵循栈的原则；
• 类似浏览器的历史记录，任何 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 树上某个分支任务”，且某项任