JavaScript数据结构yocto queue队列链表代码分析

时间:2022-12-19 codeniu 人气:0

前言

Yocto-queue 是一种允许高效存储和检索数据的数据结构。它是一种队列类型，是一个元素集合，其中的项被添加到一端并从另一端移除。

它被设计用来操作数据量很大的数组，在你需要使用大量的 Array.push、Array.shift 操作时，Yocto-queue 有更好的性能表现。

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

准备工作

在浏览器中调试代码虽然说很方便但是多多少少看着有点不专业，我们还是使用 Github Workspace，不同的是这次是在本地的vscode中使用。

我们打开 yocto-queue 仓库，创建一个Github Codespace，回到 Github 首页，在导航栏选中 Workspace ，找到你刚创建的项目，选择使用 vscode打开，如图：

vscode 会提示安装Githbu Workspace 插件，实际上它跟 Remote SHH 插件的功能差不多，为我们在远程服务器上开发提供了一种可能，这么做的好处有，跨平台，多端操作，环境统一等。

分析代码

源码如下：

/*
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）的数据结构，具有以下几个特点：

新元素总是添加到队列的末尾。
已经在队列中的元素保持原有的顺序不变。
任何时候，只能从队列的开头（顶部）删除元素。

入队

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

向队列中添加值。该方法需要一个值作为参数，它用来创建一个新的 Node 对象。

如果队列中已经有一个 head 和 tail 节点，新节点将会添加到队列末尾，通过将 tail 节点的 next 属性设置为新节点，并更新 tail 属性为新节点。

如果队列为空，新节点将成为 head 和 tail 节点。最后，队列的 size 属性会增加以反映新添加的节点。

出队

从队列中删除顶部节点的值，并将其返回。

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

它首先通过检查 head 属性是否为空来检查队列是否为空。如果队列为空，该方法返回 null。如果队列不为空，head 属性将更新为队列中的下一个节点，并且 size 属性减少以反映删除的节点。然后返回原 head 节点的值。

迭代器

允许在 for...of 循环中使用 yocto-queue.

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

使用 Symbol.iterator 符号来为队列定义一个自定义迭代器。迭代器首先将 current 变量设置为队列的 head 属性。然后进入一个循环，只要 current 不为 null 就继续循环。每次迭代，都会使用 yield 关键字产生 current 节点的 value 属性。然后 current 变量将更新为队列中的下一个节点，循环继续。这样 for...of 循环就可以遍历队列中的所有值。

总结

通过阅读yocto-queue的源码，学习到了队列的实现方式，以及迭代器的使用。数组以及队列两种数据结构在使用场景上的异同，数组是查询快，插入慢，队列是查询慢，插入快。

加载全部内容