數(shù)據(jù)結(jié)構(gòu)快速盤點(diǎn) - 線性結(jié)構(gòu)

PS:?由于公眾號(hào)本身的限制，有些鏈接無(wú)法給出，需要的可以閱讀原文查看。

這篇文章不是講解數(shù)據(jù)結(jié)構(gòu)的文章，而是結(jié)合現(xiàn)實(shí)的場(chǎng)景幫助大家 理解和復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法， 如果你的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)很差，建議先去看一些基礎(chǔ)教程，再轉(zhuǎn)過(guò)來(lái)看。

本篇文章的定位是側(cè)重于前端的，通過(guò)學(xué)習(xí)前端中實(shí)際場(chǎng)景的數(shù)據(jù)結(jié)構(gòu)，從而加深大家對(duì)數(shù)據(jù)結(jié)構(gòu)的理解和認(rèn)識(shí)。

線性結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)我們可以從邏輯上分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)有 數(shù)組，棧，鏈表等， 非線性結(jié)構(gòu)有樹(shù)，圖等。

其實(shí)我們可以稱樹(shù)為一種半線性結(jié)構(gòu)。

需要注意的是，線性和非線性不代表存儲(chǔ)結(jié)構(gòu)是線性的還是非線性的，這兩者沒(méi)有任何關(guān)系，它只是一種邏輯上的劃分。比如我們可以用數(shù)組去存儲(chǔ)二叉樹(shù)。

一般而言，有前驅(qū)和后繼的就是線性數(shù)據(jù)結(jié)構(gòu)。比如數(shù)組和鏈表。其實(shí)一叉樹(shù)就是鏈表。

數(shù)組

數(shù)組是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)了，很多地方都用到它。比如有一個(gè)數(shù)據(jù)列表等，用它是再合適不過(guò)了。其實(shí)后面的數(shù)據(jù)結(jié)構(gòu)很多都有數(shù)組的影子。

我們之后要講的棧和隊(duì)列其實(shí)都可以看成是一種 受限的數(shù)組, 怎么個(gè)受限法呢？我們后面討論。

我們來(lái)講幾個(gè)有趣的例子來(lái)加深大家對(duì)數(shù)組這種數(shù)據(jù)結(jié)構(gòu)的理解。

React Hooks

Hooks的本質(zhì)就是一個(gè)數(shù)組， 偽代碼：

那么為什么hooks要用數(shù)組？我們可以換個(gè)角度來(lái)解釋，如果不用數(shù)組會(huì)怎么樣？

function Form() {
  // 1. Use the name state variable
  const [name, setName] = useState('Mary');

  // 2. Use an effect for persisting the form
  useEffect(function persistForm() {
    localStorage.setItem('formData', name);
  });

  // 3. Use the surname state variable
  const [surname, setSurname] = useState('Poppins');

  // 4. Use an effect for updating the title
  useEffect(function updateTitle() {
    document.title = name + ' ' + surname;
  });

  // ...
}

基于數(shù)組的方式，F(xiàn)orm的hooks就是 [hook1, hook2, hook3, hook4], 我們可以得出這樣的關(guān)系， hook1就是[name, setName] 這一對(duì)， hook2就是persistForm這個(gè)。

如果不用數(shù)組實(shí)現(xiàn)，比如對(duì)象，F(xiàn)orm的hooks就是

{
  'key1': hook1,
  'key2': hook2,
  'key3': hook3,
  'key4': hook4,
}

那么問(wèn)題是key1，key2，key3，key4怎么取呢？

關(guān)于React hooks 的本質(zhì)研究，更多請(qǐng)查看React hooks: not magic, just arrays

React 將 如何確保組件內(nèi)部hooks保存的狀態(tài)之間的對(duì)應(yīng)關(guān)系這個(gè)工作交給了 開(kāi)發(fā)人員去保證，即你必須保證HOOKS的順序嚴(yán)格一致，具體可以看React 官網(wǎng)關(guān)于 Hooks Rule 部分。

隊(duì)列

隊(duì)列是一種受限的序列，它只能夠操作隊(duì)尾和隊(duì)首，并且只能只能在隊(duì)尾添加元素，在隊(duì)首刪除元素。

隊(duì)列作為一種最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)同樣有著非常廣泛的應(yīng)用， 比如消息隊(duì)列

"隊(duì)列"這個(gè)名稱,可類比為現(xiàn)實(shí)生活中排隊(duì)（不插隊(duì)的那種）

在計(jì)算機(jī)科學(xué)中, 一個(gè) 隊(duì)列(queue) 是一種特殊類型的抽象數(shù)據(jù)類型或集合。集合中的實(shí)體按順序保存。

隊(duì)列基本操作有兩種:

• 向隊(duì)列的后端位置添加實(shí)體，稱為入隊(duì)

• 從隊(duì)列的前端位置移除實(shí)體，稱為出隊(duì)。

隊(duì)列中元素先進(jìn)先出 FIFO (first in, first out)的示意：

(圖片來(lái)自 https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/queue/README.zh-CN.md)

我們前端在做性能優(yōu)化的時(shí)候，很多時(shí)候會(huì)提到的一點(diǎn)就是“HTTP 1.1 的隊(duì)頭阻塞問(wèn)題”，具體來(lái)說(shuō) 就是HTTP2 解決了 HTTP1.1 中的隊(duì)頭阻塞問(wèn)題，但是為什么HTTP1.1有隊(duì)頭阻塞問(wèn)題，HTTP2究竟怎么解決的很多人都不清楚。

其實(shí)“隊(duì)頭阻塞”是一個(gè)專有名詞，不僅僅這里有，交換器等其他都有這個(gè)問(wèn)題，引起這個(gè)問(wèn)題的根本原因是使用了 隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)。

對(duì)于同一個(gè)tcp連接，所有的http1.0請(qǐng)求放入隊(duì)列中，只有前一個(gè) 請(qǐng)求的響應(yīng)收到了，然后才能發(fā)送下一個(gè)請(qǐng)求，這個(gè)阻塞主要發(fā)生在客戶端。

這就好像我們?cè)诘燃t綠燈，即使旁邊綠燈亮了，你的這個(gè)車道是紅燈，你還是不能走，還是要等著。

HTTP/1.0 和 HTTP/1.1:
在 HTTP/1.0 中每一次請(qǐng)求都需要建立一個(gè)TCP連接，請(qǐng)求結(jié)束后立即斷開(kāi)連接。在 HTTP/1.1 中，每一個(gè)連接都默認(rèn)是長(zhǎng)連接(persistent connection)。對(duì)于同一個(gè)tcp連接，允許一次發(fā)送多個(gè)http1.1請(qǐng)求，也就是說(shuō)，不必等前一個(gè)響應(yīng)收到，就可以發(fā)送下一個(gè)請(qǐng)求。這樣就解決了http1.0的客戶端的隊(duì)頭阻塞，而這也就是 HTTP/1.1中 管道(Pipeline)的概念了。但是， http1.1規(guī)定，服務(wù)器端的響應(yīng)的發(fā)送要根據(jù)請(qǐng)求被接收的順序排隊(duì)，也就是說(shuō)，先接收到的請(qǐng)求的響應(yīng)也要先發(fā)送。這樣造成的問(wèn)題是，如果最先收到的請(qǐng)求的處理時(shí)間長(zhǎng)的話，響應(yīng)生成也慢，就會(huì)阻塞已經(jīng)生成了的響應(yīng)的發(fā)送。也會(huì)造成隊(duì)頭阻塞?？梢?jiàn)，http1.1的隊(duì)首阻塞發(fā)生在服務(wù)器端。

如果用圖來(lái)表示的話，過(guò)程大概是：

HTTP/2 和 HTTP/1.1:

為了解決 HTTP/1.1中的服務(wù)端隊(duì)首阻塞， HTTP/2采用了 二進(jìn)制分幀 和 多路復(fù)用 等方法。
二進(jìn)制分幀中，幀是 HTTP/2數(shù)據(jù)通信的最小單位。在 HTTP/1.1數(shù)據(jù)包是文本格式，而 HTTP/2的數(shù)據(jù)包是二進(jìn)制格式的，也就是二進(jìn)制幀。采用幀可以將請(qǐng)求和響應(yīng)的數(shù)據(jù)分割得更小，且二進(jìn)制協(xié)議可以更高效解析。HTTP/2 中，同域名下所有通信都在單個(gè)連接上完成，該連接可以承載任意數(shù)量的雙向數(shù)據(jù)流。每個(gè)數(shù)據(jù)流都以消息的形式發(fā)送，而消息又由一個(gè)或多個(gè)幀組成。多個(gè)幀之間可以亂序發(fā)送，根據(jù)幀首部的流標(biāo)識(shí)可以重新組裝。多路復(fù)用 用以替代原來(lái)的序列和擁塞機(jī)制。在HTTP/1.1 中，并發(fā)多個(gè)請(qǐng)求需要多個(gè)TCP鏈接，且單個(gè)域名有6-8個(gè)TCP鏈接請(qǐng)求限制。在HHTP/2`中，同一域名下的所有通信在單個(gè)鏈接完成，僅占用一個(gè)TCP鏈接，且在這一個(gè)鏈接上可以并行請(qǐng)求和響應(yīng)，互不干擾。

此網(wǎng)站可以直觀感受 HTTP/1.1和 HTTP/2的性能對(duì)比。

棧

棧也是一種受限的序列，它只能夠操作棧頂，不管入棧還是出棧，都是在棧頂操作。

在計(jì)算機(jī)科學(xué)中, 一個(gè) 棧(stack) 是一種抽象數(shù)據(jù)類型,用作表示元素的集合,具有兩種主要操作:

push, 添加元素到棧的頂端(末尾); pop, 移除棧最頂端(末尾)的元素. 以上兩種操作可以簡(jiǎn)單概括為“后進(jìn)先出(LIFO = last in, first out)”。

此外,應(yīng)有一個(gè) peek 操作用于訪問(wèn)棧當(dāng)前頂端(末尾)的元素。（只返回不彈出）

"棧"這個(gè)名稱,可類比于一組物體的堆疊(一摞書,一摞盤子之類的)。

棧的 push 和 pop 操作的示意:

(圖片來(lái)自 https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/stack/README.zh-CN.md)

棧在很多地方都有著應(yīng)用，比如大家熟悉的瀏覽器就有很多棧，其實(shí)瀏覽器的執(zhí)行棧就是一個(gè)基本的棧結(jié)構(gòu)，從數(shù)據(jù)結(jié)構(gòu)上說(shuō)，它就是一個(gè)棧。這也就解釋了，我們用遞歸的解法和用循環(huán)+棧的解法本質(zhì)上是差不多。

比如如下JS代碼：

function bar() {
  const a = 1
  const b = 2;
  console.log(a, b)
}
function foo() {
  const a = 1;
  bar();
}

foo();

真正執(zhí)行的時(shí)候，內(nèi)部大概是這樣的：

我畫的圖沒(méi)有畫出執(zhí)行上下文中其他部分（this和scope等）， 這部分是閉包的關(guān)鍵，而我這里不是將閉包的，是為了講解棧的。

社區(qū)中有很多“執(zhí)行上下文中的scope指的是執(zhí)行棧中父級(jí)聲明的變量”說(shuō)法，這是完全錯(cuò)誤的， JS是詞法作用域，scope指的是函數(shù)定義時(shí)候的父級(jí)，和執(zhí)行沒(méi)關(guān)系

棧常見(jiàn)的應(yīng)用有進(jìn)制轉(zhuǎn)換，括號(hào)匹配，棧混洗，中綴表達(dá)式（用的很少），后綴表達(dá)式（逆波蘭表達(dá)式）等。

合法的棧混洗操作，其實(shí)和合法的括號(hào)匹配表達(dá)式之間存在著一一對(duì)應(yīng)的關(guān)系， 也就是說(shuō)n個(gè)元素的?；煜从卸嗌俜N，n對(duì)括號(hào)的合法表達(dá)式就有多少種。感興趣的可以查找相關(guān)資料

鏈表

鏈表是一種最基本數(shù)據(jù)結(jié)構(gòu)，熟練掌握鏈表的結(jié)構(gòu)和常見(jiàn)操作是基礎(chǔ)中的基礎(chǔ)。

(圖片來(lái)自：https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/linked-list/traversal)

React Fiber

很多人都說(shuō) fiber 是基于鏈表實(shí)現(xiàn)的，但是為什么要基于鏈表呢，可能很多人并沒(méi)有答案，那么我覺(jué)得可以把這兩個(gè)點(diǎn)（fiber 和鏈表）放到一起來(lái)講下。

fiber 出現(xiàn)的目的其實(shí)是為了解決 react 在執(zhí)行的時(shí)候是無(wú)法停下來(lái)的，需要一口氣執(zhí)行完的問(wèn)題的。

圖片來(lái)自 Lin Clark 在 ReactConf 2017 分享

上面已經(jīng)指出了引入 fiber 之前的問(wèn)題，就是 react 會(huì)阻止優(yōu)先級(jí)高的代碼（比如用戶輸入）執(zhí)行。因此 fiber 打算自己自建一個(gè) 虛擬執(zhí)行棧來(lái)解決這個(gè)問(wèn)題，這個(gè)虛擬執(zhí)行棧的實(shí)現(xiàn)是鏈表。

Fiber 的基本原理是將協(xié)調(diào)過(guò)程分成小塊，一次執(zhí)行一塊，然乎將運(yùn)算結(jié)果保存起來(lái)，并判斷是否有時(shí)間（react 自己實(shí)現(xiàn)了一個(gè)類似 requestIdleCallback 的功能）繼續(xù)執(zhí)行下一塊。如果有時(shí)間，則繼續(xù)。否則跳出，讓瀏覽器主線程歇一會(huì)，執(zhí)行別的優(yōu)先級(jí)高的代碼。

當(dāng)協(xié)調(diào)過(guò)程完成（所有的小塊都運(yùn)算完畢）， 那么就會(huì)進(jìn)入提交階段， 真正的進(jìn)行副作用（side effect）操作，比如更新DOM，這個(gè)過(guò)程是沒(méi)有辦法取消的，原因就是這部分有副作用。

問(wèn)題的關(guān)鍵就是將協(xié)調(diào)的過(guò)程劃分為一塊塊的，最后還可以合并到一起，有點(diǎn)像Map／Reduce。

React 必須重新實(shí)現(xiàn)遍歷樹(shù)的算法，從依賴于 內(nèi)置堆棧的同步遞歸模型，變?yōu)?具有鏈表和指針的異步模型。

Andrew 是這么說(shuō)的：如果你只依賴于[內(nèi)置]調(diào)用堆棧，它將繼續(xù)工作直到堆棧為空。。。

如果我們可以隨意中斷調(diào)用堆棧并手動(dòng)操作堆棧幀，那不是很好嗎？這就是 React Fiber 的目的。Fiber是堆棧的重新實(shí)現(xiàn)，專門用于React組件。你可以將單個(gè) Fiber 視為一個(gè) 虛擬堆棧幀。

react fiber 大概是這樣的：

let fiber = {
  tag: HOST_COMPONENT,
  type: "div",
  return: parentFiber,
  children: childFiber,
  sibling: childFiber,
  alternate: currentFiber,
  stateNode: document.createElement("div"),
  props: { children: [], className: "foo"},
  partialState: null,
  effectTag: PLACEMENT,
  effects: []
};

從這里可以看出fiber本質(zhì)上是個(gè)對(duì)象，使用parent，child，sibling屬性去構(gòu)建fiber樹(shù)來(lái)表示組件的結(jié)構(gòu)樹(shù)， return, children, sibling也都是一個(gè)fiber，因此fiber看起來(lái)就是一個(gè)鏈表。

細(xì)心的朋友可能已經(jīng)發(fā)現(xiàn)了， alternate也是一個(gè)fiber， 那么它是用來(lái)做什么的呢？它其實(shí)原理有點(diǎn)像git， 可以用來(lái)執(zhí)行g(shù)it revert ,git commit等操作，這部分挺有意思，我會(huì)在我的《從零開(kāi)發(fā)git》中講解

想要了解更多的朋友可以看這個(gè)文章

如果可以翻墻， 可以看英文原文

這篇文章也是早期講述fiber架構(gòu)的優(yōu)秀文章

我目前也在寫關(guān)于《從零開(kāi)發(fā)react系列教程》中關(guān)于fiber架構(gòu)的部分，如果你對(duì)具體實(shí)現(xiàn)感興趣，歡迎關(guān)注。?

另外最近也發(fā)布了前端領(lǐng)域的數(shù)據(jù)結(jié)構(gòu)與算法解讀 - fiber? 感興趣的可以看一下

??看完三件事

如果你覺(jué)得這篇內(nèi)容對(duì)你挺有啟發(fā)，我想邀請(qǐng)你幫我三個(gè)小忙：

1. 點(diǎn)贊，讓更多的人也能看到介紹內(nèi)容（收藏不點(diǎn)贊，都是耍流氓-_-）
2. 關(guān)注公眾號(hào)“前端勸退師”，不定期分享原創(chuàng)知識(shí)。
3. 也看看其他文章

勸退師個(gè)人微信：huab119

也可以來(lái)我的GitHub博客里拿所有文章的源文件：

前端勸退指南：https：//github.com/roger-hiro/BlogFN一起玩耍呀。