数组还是队列？yocto-queue 源码告诉你

news/2024/4/27 11:51:47/文章来源:https://blog.csdn.net/web22050702/article/details/129169069

前言

昨天刚学完 omit 的源码，今天趁着学习源码的热度还没结束，来学习一下另一个我之前未接触过的东西 yocto-queue。

yocto-queue 介绍

那么 yocto-queue 是什么呢？它有什么功能呢？查阅资料可得，对于数据比较多的数组，如果需要频繁地使用 push 和 shift 方法，那么可以使用 yocto-queue 来代替数组。因为shift 操作具有 O(n) 的时间复杂度，而通过 yocto-queue，只需要 O(1) 的时间复杂度。

说到 yocto-queue，不得不可以提到队列（毕竟名字中就带有 queue）。队列的工作原理是先进先出(FIFO)，它是一个有序的元素列表，其中一个元素插入到队列的末尾，然后从队列的前面移除。

分析源码

介绍了它的一些基本信息，现在开始分析一下它们的源码部分。进入到 github，找到它的源码中的 package.json 部分，发现源码部分在 ./index.js 文件下。

我们进入到关键源码实现部分，代码不多，才六十多行，代码如下：

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

Node

源码一开始就创建一个节点类 Node。节点里有两个属性， value 表示节点的值，next 是一个指向下一节点的指针，里面还有一个构造函数。

class Node {value;next;constructor(value) {this.value = value;}
}

Queue

在 Queue 中，创建 head 和 tail 头尾指针，并定义 size 来记录大小。每次遍历的时候先找到头结点，然后通过每个结点的 next 指针往后走。这样一看是不是又很像链表。

注：head 指向头节点，用于模拟 shift 来删除第一个元素；tail 指向尾节点，用于模拟 push 向末尾添加新元素。

clear

然后这里还定义了 clear 方法。如下所示：

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

clear 方法对实例的三个属性做了初始化。其中，把指针初始化为 undefined，表示一开始没有节点，将 size 初始化为0，表示是个空链表。

迭代器

这里的链表遍历使用了迭代器，采用了 [Symbol.iterator] 这个方法。之所以会用到这个方法来遍历，是为了让对象可迭代，而这个方法就可以达到此要求。

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

使用 yocto-queue

看完源码后，我们来通过简单的练习更好地看清楚它发挥的作用。我创建了一个 react 项目，写了一个关于使用 yocto-queue 的 demo，代码如下所示：

import Queue from "./index";const queue = new Queue();
queue.enqueue("a");
queue.enqueue("b");
console.log(queue.dequeue());
console.log(...queue);
console.log(queue.size);
for (let q of queue) {console.log(q);
}
queue.clear();function App() {return (<div className="App"></div>)
}
export default App

index 里面是 yocto-queue 源码，相当于引入 yocto-queue 包。然后分别调用了源码中的关键功能函数，并打印结果。

最终打印结果如下：