yocto-queue 库如何实现替代数组【玩转源码】

前言

前面提到了可以使用yocto-queue库代替Array操作数组，本篇则深入源码了解一下yocto-queue是如何实现替代数组的。

yocto-queue源码分析

源码中的代码量相对较少，读起来会比较轻松，看似可以琢磨的点少，其实不然。

代码中包含知识点主要包括类的属性、链表与数组的对比、队列、自定义迭代器等，容我细讲。

git 地址：yocto-queue

Node 类

node 类的作用是在新增操作中储存需要插入到队列中的元素。

class Node {
  value;
  next;

  constructor(value) {
    this.value = value;
  }
}

它有两个公有属性：

value：插入到队列中的元素。

next：下一个 Node 实例。

属性的两种写法

Node 类里面正好包含了这两种写法：

第一种，定义在 constructor() 方法里面的 this 上面；

第二种，定义在类的最顶层。（ES2022 新加的写法）

Queue 类

私有属性的“演化”

class Queue {
  #head;
  #tail;
  #size;
}

Queue 类里共包含三个私有属性：

#head：队列的头。

#tail：队列的尾。

#size：队列的长度。

在属性前面使用#，是 ES2022 新加入的写法，从此 class 正式有了私有属性。这个私有属性在 Queue 的外部是无法被使用的。

const queue = new Queue();
console.log(queue.#size);

外部使用 #size 属性，会抛出错误：

Private field '#size' must be declared in an enclosing class

在这之前，主要采用命名方式的不同区分私有属性和公有属性。比如声明一个只有 Queue 内部可用使用的常量_limit。

_limit = 10;

但是其实 Queue 的实例是可以访问到的。

const queue = new Queue();
console.log(queue._limit); // 10

还有将私有方法的名字命名为一个 Symbol 值的方式，可以阅读阮一峰大佬的书详细了解。

链表 vs 数组

数组：一种有序线性数据结构，用一串连续的内存空间进行数据存储。

链表：一种无序线性数据结构，用一串非连续的内存空间进行数据存储，通过链表中节点的指针次序维护线性链路。

两个数据类型在操作元素时的时间复杂度的区别如下：

队列

yocto-queue 库提供的主要功能就是用链表实现队列，然后进行数据的添加和删除。

队列是具有先进先出 (FIFO) 原则的有序集合。

enqueue 入队列

该方法会从队列中的队尾添加一个元素。

class Queue {
  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++;
  }
}

通过队头 #head 的值判断，需要插入的元素存放在队列中的位置：

如果 #head 的值存在，则新添加的元素放在队尾；

如果 #head 的值不存在，则新添加的元素即为队列的队头；

且队列长度加一。

dequeue 出队列

该方法会从队列中的队头元素移除，并返回移除的元素。

class Queue {
  dequeue() {
    const current = this.#head;
    if (!current) {
      return;
    }

    this.#head = this.#head.next;
    this.#size--;
    return current.value;
  }
}

先定义 current 指向队头的元素，通过 current 值的判断进行下一步操作：

如果 current 不存在，则表示队列中已经没有数据。

如果 current 存在，则将队头的元素移除，再队列的长度减一，并返回移除的元素。

我们来调用 dequeue 方法之后，查看队列的值：

const queue = new Queue();
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
console.log(...queue); // 4 5

从打印结果可以看出元素3已经被移除。

自定义迭代器

数组拥有默认的迭代器行为，Queue 类的实例对象理论也应该拥有迭代器行为。

使用 Symbol.iterator 可以创建自定义迭代器，创建方法很简单。

class Queue {
  *[Symbol.iterator]() {
    let current = this.#head;

    while (current) {
      yield current.value;
      current = current.next;
    }
  }
}

Queue 类定义的迭代器，从队列的头开始循环，把每一个元素都返回出来。

这样在查看队列数据的时候可以使用...展开：

const queue = new Queue();
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
console.log(...queue); // 3 4 5

源码阅读的两个重要点

源码阅读的过程中，对实现方法和设计模式的分析、学习、吃透很重要。

遇到问题，提出疑问，寻找答案，这个过程同样重要。在这个过程里，除了锻炼了个人思考的能力，还可以帮助自信心的塑造。

不要担心自己提的问题是多余的或者过于基础，由浅入深，在这个过程中可以实现经验的积累。而后，无论是看待问题的角度，还是提问的内容，都会变得精准。

总结

yocto-queue 库的源码阅读分析之后，收获如下：

1. 通过对 yocto-queue 库的源码分析，了解了它如何替代数组以及若干知识点回顾。
2. 额外的收获，关于源码阅读的两个重要点学习与个人思考。

作者：非职业「传道授业解惑」的开发者叶一一简介：「趣学前端」、「CSS畅想」系列作者，华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。如果看完文章有所收获，欢迎点赞