源码阅读：yocto-queue

简介

队列是元素的有序列表，其中元素在队列末尾插入，并从队列前面删除。队列基于先进先出原则工作。

如果你在大型数组上执行大量 Array#push() 和 Array#shift() 操作，则应该使用此包而不是数组，因为 Array#shift() 的线性时间复杂度为 O(n)，而 Queue#dequeue() 是基于链表实现的，具有恒定的时间复杂度 O(1)。这对于大型队列来说有很大的不同。

源码解读

这段代码定义了一个队列数据结构，其中包含一个节点类Node和一个队列类Queue。

class Node {

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

Node类表示队列中的节点，它有两个属性，value表示节点的值，next表示指向下一个节点的指针。构造函数constructor用于初始化节点的值。

export default class Queue {
  #head;
  #tail;
  #size;
  
  constructor() {
    this.clear();
  }
  // ...
}

Queue类是一个默认导出的类，表示队列数据结构。它有三个私有属性#head、#tail和#size，分别表示队列的头部节点、尾部节点和队列的大小。构造函数constructor用于初始化队列，调用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++;
}

enqueue(value)方法用于向队列中添加新的元素。它接收一个值作为参数，创建一个新的节点，并将其加入队列的尾部。如果队列为空，则将新节点同时设置为头部和尾部节点。如果队列不为空，则将新节点连接到当前尾部节点的next属性，并将新节点设置为新的尾部节点。最后，队列的大小加一。

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

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

dequeue()方法用于从队列中移除头部的元素，并返回其值。它首先获取当前头部节点，如果队列为空，则直接返回。否则，将头部节点指向下一个节点，并将队列的大小减一，最后返回被移除节点的值。

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

clear()方法用于清空队列，将头部、尾部节点置为undefined，并将队列的大小设为0。

get size() {
    return this.#size;
}

size属性是一个getter，用于获取队列的大小。

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


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

}

[Symbol.iterator]方法是一个生成器函数，用于使队列对象可迭代。它返回一个迭代器对象，通过遍历队列的节点，依次返回节点的值。在每次迭代中，将当前节点的值通过yield关键字返回，并将当前节点指向下一个节点，直到遍历完整个队列。

这个队列数据结构提供了常见的队列操作，如入队、出队、清空队列和获取队列大小，同时还可以通过迭代器遍历队列中的元素。

接下来我们来看看它的类型声明：

export default class Queue<ValueType> implements Iterable<ValueType> {
	/**
	The size of the queue.
	*/
	readonly size: number;
	constructor();

	[Symbol.iterator](): IterableIterator<ValueType>;


	/**
	Add a value to the queue.
	*/
	enqueue(value: ValueType): void;


	/**
	Remove the next value in the queue.

	@returns The removed value or `undefined` if the queue is empty.
	*/
	dequeue(): ValueType | undefined;


	/**
	Clear the queue.
	*/
	clear(): void;
}

这段类型声明表示了一个泛型的队列类Queue，实现了Iterable接口，可以进行迭代操作：

export default class Queue<ValueType> implements Iterable<ValueType>：导出一个默认的Queue类，它是一个泛型类，使用ValueType作为泛型参数，并实现了Iterable接口，表示可以进行迭代操作。
readonly size: number：一个只读的属性，表示队列的大小。
constructor()：构造函数，用于创建一个空的队列。
[Symbol.iterator](): IterableIterator<ValueType>：迭代器方法，返回一个IterableIterator对象，用于迭代队列中的元素。
enqueue(value: ValueType): void：入队方法，接收一个ValueType类型的值作为参数，并将其添加到队列中。
dequeue(): ValueType | undefined：出队方法，移除队列中的下一个元素，并返回其值。如果队列为空，则返回undefined。
clear(): void：清空队列，将队列中的所有元素移除。

这个类型声明定义了一个基本的队列类，包含了入队、出队、清空队列等常用操作，并提供了一个只读的大小属性和迭代器方法，使得队列可以进行遍历操作。

完整源码如下：

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