大家好，我是若川。持續組織了8個月源碼共讀活動，感興趣的可以?點此加我微信ruochuan12?參與，每周大家一起學習200行左右的源碼，共同進步。同時極力推薦訂閱我寫的《學習源碼整體架構系列》?包含20余篇源碼文章。歷史面試系列。另外：目前建有江西|湖南|湖北籍前端群，可加我微信進群。
這是來自源碼共讀群中大二的小伙伴投稿，寫的非常好，圖文并茂，關鍵還寫了好多篇筆記了。原文鏈接可點擊文末閱讀原文查看。

Part11. 前言

1.1 這個庫，是干啥的

如果你項目中要用到一個非常大的數組，并且你經常需要使用這兩個操作：

Array.push() 在末端添加一個元素.
Array.shift()在取出隊列首端的一個元素，整個隊列往前移，這樣原先排第二的元素現在排在了第一

如果學過數據結構，就會敏銳地發現，誒這兩個操作，不就是在模擬隊列嗎

queue 隊列是一個有序的元素列表，其中一個元素插入到隊列的末尾，然后從隊列的前面移除。隊列的工作原理是**先進先出(FIFO)**。

JS 沒有queue這個數據結構，用數組模擬就好了，真方便！
nonono，回到開頭，當數據量較小的時候，似乎沒什么影響，但如果數據量較大，性能就會嚴重下降
這是因為在底層實現中，數組是順序存儲的，當你shift的時候，會先取出隊列首端的一個元素，整個隊列往前移——整個操作的事件時間復雜度是**O(n)**
如果你的項目正如上面我所說的情況，那么你很可能就需要這個包 yocto-queue，它能讓你的shift操作時間復雜度降為O(1)。（在這庫里面shift用的是dequeue方法）

1.2 你能學到

ES6 中的 class
鏈表和數組的區別，時間復雜度
JS 實現鏈表的方法
學習 Symbol.iterator 的使用場景
調試源碼

Part22. 準備

2.1 了解API

import?Queue?from?'yocto-queue';const?queue?=?new?Queue();queue.enqueue('🦄');
queue.enqueue('🌈');console.log(queue.size);
//=>?2console.log(...queue);
//=>?'🦄?🌈'console.log(queue.dequeue());
//=>?'🦄'console.log(queue.dequeue());
//=>?'🌈'

queue = new Queue()

The instance is an Iterable, which means you can iterate over the queue front to back with a “for…of” loop, or use spreading to convert the queue to an array. Don't do this unless you really need to though, since it's slow.

該實例是可枚舉的，也就是說你可以用for...of來遍歷，并且可以用擴展運算符將其變為數組，但是盡量不要這樣做，這樣性能很差

.enqueue(value)

添加一個元素到隊尾

.dequeue()

刪去隊頭，并返回被刪除的值 || 或者是 undefined（隊列本來就已經為空的情況）

.clear()

清空隊列

.size

返回隊列的大小

Part33 看看 ?源碼

3.1 環境準備

# 克隆官方倉庫
git clone https://github.com/sindresorhus/yocto-queue.git
cd .\yocto-queue\
npm install
code .

3.3 調試源碼

查看 package.json文件來確定主入口為 index.js

demo

新建文件夾examples，存放 demo index.js

//?yocto-queue/examples/index.js
import?Queue?from?"../index.js";const?queue?=?new?Queue();?//此處打斷點
queue.enqueue("?");
queue.enqueue("🌊");console.log(queue.dequeue());console.log(queue.size);
for?(let?q?of?queue)?{console.log(q);
}
queue.clear();

node examples/index.js或者直接F5也可以即可開始調試源碼，其實這個代碼復雜度不手動調試也可以的，但是通過調試可以讓你很明確地看到哪一步代碼用到了哪里的東西

3.4 理解源碼

源碼

Queue中，#head和#tail可以視作虛擬結點，只是分別用來指向頭和尾結點的。每次遍歷的時候先找到頭結點（#head指向的結點），然后通過每個結點的next指針往后走。即使只有頭結點也能組成該鏈表——慢慢遍歷總能到最后面，但是顯然這樣效率就低了，所以還有一個專門的尾指針#tail，方便尾部插入結點
源碼總覽：

class?Node?{value;next;constructor(value)?{this.value?=?value;}
}export?default?class?Queue?{#head;#tail;#size;constructor()?{this.clear();}enqueue(value)?{const?node?=?new?Node(value);if?(this.#head)?{this.#tail.next?=?node;this.#tail?=?node;}?else?{this.#head?=?node;this.#tail?=?node;}this.#size++;}dequeue()?{const?current?=?this.#head;if?(!current)?{return;}this.#head?=?this.#head.next;this.#size--;return?current.value;}clear()?{this.#head?=?undefined;this.#tail?=?undefined;this.#size?=?0;}get?size()?{return?this.#size;}*?[Symbol.iterator]()?{let?current?=?this.#head;while?(current)?{yield?current.value;current?=?current.next;}}
}

分步解析

enqueue

queue.enqueue("?");時，會創造Queue中第一個實例node，第一個結點自然頭和尾都指向他自己

if?(this.#head)?{//...
}?else?{this.#head?=?node;this.#tail?=?node;
}

image.png

queue.enqueue("🌊");隨后我們添加第二個結點

if?(this.#head)?{this.#tail.next?=?node;this.#tail?=?node;
}?else?{//...
}

實際上我們可以發現，這就是尾插法

dequeue

console.log(queue.dequeue());

dequeue()?{const?current?=?this.#head;???//獲取當前if?(!current)?{return;}this.#head?=?this.#head.next;this.#size--;return?current.value;
}

image.png

size

console.log(queue.size);

get?size()?{return?this.#size;
}

這里用到了 class 中 getters

?for...of

這里是本文的一個重點

這里實現了Queue這個對象可以通過for...of來進行遍歷，即讓它可以迭代。
想要讓對象可迭代，需要添加一個Symbol.iterator方法，這個方法專門用來使對象可迭代的內建symbol。
通過調試我們也可以知道，當進入for...of，他就會進入Symbol.iterator這個方法，（如果沒找到，就會報錯，像數組那些對象都是有內置該方法的），該方法必須返回一個迭代器—— 一個有next方法的對象。
像這樣使用：

let?range?=?{from:?1,to:?5,[Symbol.iterator]()?{?//?在?for..of?循環開始時被調用一次return?{current:?this.from,last:?this.to,next()?{?//?每次迭代時都會被調用，來獲取下一個值if?(this.current?<=?this.last)?{return?{?done:?false,?value:?this.current++?};}?else?{return?{?done:?true?};}}};}
};for(let?value?of?range)?{alert(value);?//?1，然后?2，然后?3，然后?4，然后?5
}

而源碼中并不是這樣的，而是這樣：

*?[Symbol.iterator]()?{let?current?=?this.#head;?//通過current記錄當前迭代進程while?(current)?{???//循環取值，直到沒有yield?current.value;??//取值，并返回current?=?current.next;//通過next往下一個走}
}

這是因為這里并不僅是使用了Symbol.iterator

?生成器

生成器是 ES6 新增的一個極為靈活的結構，擁有在一個函數塊內暫停和恢復代碼執行的能力。這種能力具有深遠的影響，比如使用生成器可以自定義迭代器和實現協程。

在函數前面加一個星號*，則表示它是一個生成器。調用生成器函數會產生一個生成器對象，其一開始處于暫停狀態，該對象也實現了Iterator接口，通過調next()使其轉為開始或者恢復執行狀態。生成器函數在遇到yield關鍵字前會正常執行，遇到該關鍵字后，執行會停止，函數作用域的狀態被保留 —— 有點像函數的中間返回語句，它能讓函數返回一個值出去，但是函數仍能繼續執行。隨后通過在生成器對象上調用next方法恢復執行。
實際上，很少在生成器對象上顯式調用next()，而是將其作為可迭代對象——

function*?generatorFn(){yield?1;yield?2;yield?3;
}
for(let?i?of?generatorFn()){console.log(i)?
}
//1
//2
//3

讓我們回到源碼中

for?(let?q?of?queue)?{console.log(q);
}

結合上面對Symbol.iterator的理解

當進入for...of，他就會進入Symbol.iterator這個方法

也就是說這樣調用時，實際上就是

for?(let?q?of?queue[Symbol.iterator]())?{console.log(q);
}

讓[Symbol.iterator]這個函數變為了生成器函數，并將其作為可迭代對象！大大地減少了代碼量~

clear

clear()?{this.#head?=?undefined;this.#tail?=?undefined;this.#size?=?0;
}

很簡單，直接將頭指針和尾指針指向的值改為undefined，size也設置為0，剩下的就靠JS自身的垃圾回收機制了，本文就不涉及了。

Part44. 學習資源

數組
class
Symbol.iterator
垃圾回收機制
紅寶書 7.3 生成器

Part55. 總結 & 收獲

復習了 ES6 中的 class以及相關語法
鏈表和數組的區別，時間復雜度，通過指針的空間來省下按順序遍歷的時間——一種空間換時間的性能優化策略
JS 實現鏈表的方法，有了class這個語法后，和其他語言差不多了
- Node結點，存當前value以及與用于相鄰結點相連的指針
復習 Symbol.iterator 的使用場景以及生成器這個平時可能用的較少的知識點

🌊如果有所幫助，歡迎點贊關注，一起進步?

·················?若川簡介?·················

你好，我是若川，畢業于江西高校。現在是一名前端開發“工程師”。寫有《學習源碼整體架構系列》20余篇，在知乎、掘金收獲超百萬閱讀。
從2014年起，每年都會寫一篇年度總結，已經堅持寫了8年，點擊查看年度總結。
同時，最近組織了源碼共讀活動，幫助4000+前端人學會看源碼。公眾號愿景：幫助5年內前端人走向前列。