前言

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

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

倉庫地址：sindresorhus/yocto-queue: Tiny queue data structure (github.com)

準(zhǔn)備工作

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

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

vscode 會提示安裝Githbu Workspace 插件，實際上它跟 Remote SHH 插件的功能差不多，為我們在遠(yuǎn)程服務(wù)器上開發(fā)提供了一種可能，這么做的好處有，跨平臺，多端操作，環(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;
		}
	}
}

隊列

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

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

入隊

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

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

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

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

出隊

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

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

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

迭代器

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

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

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

總結(jié)

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

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

最新評論