JavaScript數(shù)據(jù)結構yocto queue隊列鏈表代碼分析

更新時間：2022年12月19日 16:47:51 作者：codeniu

這篇文章主要為大家介紹了JavaScript數(shù)據(jù)結構yocto queue隊列鏈表代碼分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

前言

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

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

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

準備工作

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

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

vscode 會提示安裝Githbu Workspace 插件，實際上它跟 Remote SHH 插件的功能差不多，為我們在遠程服務器上開發(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ù)結構，具有以下幾個特點：

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

入隊

	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 對象。

如果隊列中已經有一個 head 和 tail 節(jié)點，新節(jié)點將會添加到隊列末尾，通過將 tail 節(jié)點的 next 屬性設置為新節(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 變量設置為隊列的 head 屬性。然后進入一個循環(huán)，只要 current 不為 null 就繼續(xù)循環(huán)。每次迭代，都會使用 yield 關鍵字產生 current 節(jié)點的 value 屬性。然后 current 變量將更新為隊列中的下一個節(jié)點，循環(huán)繼續(xù)。這樣 for...of 循環(huán)就可以遍歷隊列中的所有值。