前言

Yocto-queue 是一種允許高效存儲(chǔ)和檢索數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。它是一種隊(duì)列類型，是一個(gè)元素集合，其中的項(xiàng)被添加到一端并從另一端移除。

它被設(shè)計(jì)用來(lái)操作數(shù)據(jù)量很大的數(shù)組，在你需要使用大量的 Array.push、Array.shift 操作時(shí)，Yocto-queue 有更好的性能表現(xiàn)。

倉(cāng)庫(kù)地址：sindresorhus/yocto-queue: Tiny queue data structure (github.com)

準(zhǔn)備工作

在瀏覽器中調(diào)試代碼雖然說(shuō)很方便但是多多少少看著有點(diǎn)不專業(yè)，我們還是使用 Github Workspace，不同的是這次是在本地的vscode中使用。

我們打開(kāi) yocto-queue 倉(cāng)庫(kù)，創(chuàng)建一個(gè)Github Codespace，回到 Github 首頁(yè)，在導(dǎo)航欄選中 Workspace ，找到你剛創(chuàng)建的項(xiàng)目，選擇使用 vscode打開(kāi)，如圖：

vscode 會(huì)提示安裝Githbu Workspace 插件，實(shí)際上它跟 Remote SHH 插件的功能差不多，為我們?cè)谶h(yuǎn)程服務(wù)器上開(kāi)發(fā)提供了一種可能，這么做的好處有，跨平臺(tái)，多端操作，環(huán)境統(tǒng)一等。

分析代碼

源碼如下：

/*
How it works:
`this.#head` is an instance of `Node` which keeps track of its current value and nests another instance of `Node` that keeps the value that comes after it. When a value is provided to `.enqueue()`, the code needs to iterate through `this.#head`, going deeper and deeper to find the last value. However, iterating through every single item is slow. This problem is solved by saving a reference to the last value as `this.#tail` so that it can reference it to add a new value.
*/
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;
		}
	}
}

隊(duì)列

隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，具有以下幾個(gè)特點(diǎn)：

• 新元素總是添加到隊(duì)列的末尾。
• 已經(jīng)在隊(duì)列中的元素保持原有的順序不變。
• 任何時(shí)候，只能從隊(duì)列的開(kāi)頭（頂部）刪除元素。

入隊(duì)

	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++;
	}

向隊(duì)列中添加值。該方法需要一個(gè)值作為參數(shù)，它用來(lái)創(chuàng)建一個(gè)新的 Node 對(duì)象。

如果隊(duì)列中已經(jīng)有一個(gè) head 和 tail 節(jié)點(diǎn)，新節(jié)點(diǎn)將會(huì)添加到隊(duì)列末尾，通過(guò)將 tail 節(jié)點(diǎn)的 next 屬性設(shè)置為新節(jié)點(diǎn)，并更新 tail 屬性為新節(jié)點(diǎn)。

如果隊(duì)列為空，新節(jié)點(diǎn)將成為 head 和 tail 節(jié)點(diǎn)。最后，隊(duì)列的 size 屬性會(huì)增加以反映新添加的節(jié)點(diǎn)。

出隊(duì)

從隊(duì)列中刪除頂部節(jié)點(diǎn)的值，并將其返回。

	dequeue() {
		const current = this.#head;
		if (!current) {
			return;
		}
		this.#head = this.#head.next;
		this.#size--;
		return current.value;
	}

它首先通過(guò)檢查 head 屬性是否為空來(lái)檢查隊(duì)列是否為空。如果隊(duì)列為空，該方法返回 null。如果隊(duì)列不為空，head 屬性將更新為隊(duì)列中的下一個(gè)節(jié)點(diǎn)，并且 size 屬性減少以反映刪除的節(jié)點(diǎn)。然后返回原 head 節(jié)點(diǎn)的值。

迭代器

允許在 for...of 循環(huán)中使用 yocto-queue.

	* [Symbol.iterator]() {
		let current = this.#head;
		while (current) {
			yield current.value;
			current = current.next;
		}
	}

使用 Symbol.iterator 符號(hào)來(lái)為隊(duì)列定義一個(gè)自定義迭代器。迭代器首先將 current 變量設(shè)置為隊(duì)列的 head 屬性。然后進(jìn)入一個(gè)循環(huán)，只要 current 不為 null 就繼續(xù)循環(huán)。每次迭代，都會(huì)使用 yield 關(guān)鍵字產(chǎn)生 current 節(jié)點(diǎn)的 value 屬性。然后 current 變量將更新為隊(duì)列中的下一個(gè)節(jié)點(diǎn)，循環(huán)繼續(xù)。這樣 for...of 循環(huán)就可以遍歷隊(duì)列中的所有值。

總結(jié)

通過(guò)閱讀yocto-queue的源碼，學(xué)習(xí)到了隊(duì)列的實(shí)現(xiàn)方式，以及迭代器的使用。數(shù)組 以及 隊(duì)列兩種數(shù)據(jù)結(jié)構(gòu)在使用場(chǎng)景上的異同，數(shù)組是查詢快，插入慢，隊(duì)列是查詢慢，插入快。

以上就是JavaScript數(shù)據(jù)結(jié)構(gòu)yocto queue隊(duì)列鏈表代碼分析的詳細(xì)內(nèi)容，更多關(guān)于JavaScript yocto queue隊(duì)列鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論