【源码学习】第21期 | 长数组频繁shift和push？ 是时候用yocto-queue 队列替代数组了！

• 本文参加了由公众号@若川视野 发起的每周源码共读活动，点击了解详情一起参与。
• 第32期 | yocto-queue 队列 链表

背景

    常用的数据结构有：集合、线性结构、树形结构、图状结构，其中线性结构又包括线性表、栈、队列、双队列、数组、串等，根据需求选用不同的数据结构存储数据能大大提高效率、优化性能，今天就来学习一下yocto-queue 队列的实现！

收获清单

• yocto-queue使用场景
• 链表和数组的区别
• Symbol.iterator使用场景

yocto-queue应用场景

    这个库其实在p-limit源码中也有应用，官方的推荐词是如果您在大数组上执行大量数组push和数组shift，则应使用此软件包，因为数组shift的线性时间复杂度为o(n)而队列的dequeue()具有恒定的时间复杂性o（1）。

    为什么说shift的时间复杂度为o(n),看一下下图shift的实现就知道了，大意就是数组长度大于0时先保存数组第一个值，然后遍历数组（o(n)）把除了第一个值外的值往前覆盖，对于长数组【长度越长，n越大】来说，这时间复杂度可想而知有多大，也进一步说明了应用yocto-queue 队列效率能有多快，接下来就带着问题看源码，看看yocto-queue是怎么提效的！

链表和数组的区别

源码下载

git clone https://github.com/sindresorhus/yocto-queue.git
cd yocto-queue
pnpm install

源码调试

    下载完代码看package.json的script以便开启调试

    调试截图

    从源码中可以发现yocto-queue采用链表存储，那么链表跟数组有什么区别？为什么长数组shift操作采用链表存储后就会比数组快？咱们先看看两者之间的对比，接着再看源码验证一下~

链表和数组对比

对比	数组	链表
定义	具有相同数据类型的变量的集合	一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现
逻辑结构	（1）数组在内存中连续； (2)使用数组之前，必须事先固定数组长度，不支持动态改变数组大小；(3) 数组元素增加时，有可能会数组越界；(4) 数组元素减少时，会造成内存浪费；（5）数组增删时需要移动其它元素	（1）链表采用动态内存分配的方式，在内存中不连续 (2)支持动态增加或者删除元素 (3)需要时可以使用malloc或者new来申请内存，不用时使用free或者delete来释放内存
使用场景	(1)空间：数组的存储空间是栈上分配的，存储密度大，当要求存储的大小变化不大时，且可以事先确定大小，宜采用数组存储数据 (2)时间：数组访问效率高。当线性表的操作主要是进行查找，很少插入和删除时，宜采用数组结构	(1)空间： 链表的存储空间是堆上动态申请的，当要求存储的长度变化较大时，且事先无法估量数据规模，宜采用链表存储；(2)时间：链表插入、删除效率高，当线性表要求频繁插入和删除时，宜采用链表结构

源码详细分析

源码总览

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

    }
}
export default class Queue {
// 定义头部、尾部、节点数等私有变量
    #head;
    #tail;
    #size;
// 构造器，先清空数据
    constructor() {

        this.clear();
    }
// ...删减代码稍候详细分析
    enqueue(value) 
    dequeue() 
    clear()
// 获取节点数
    get size() {
        return this.#size;
    }
    * [Symbol.iterator]() 

}

    三个私有变量的含义：

• #head头节点，可以实现类似数组的shift效果
• #tail尾节点，可以实现类似数组的push效果
• #size，记录节点数用

node节点

    首先定义具有 数据 以及 指向下一个节点的指针的节点类

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

    }
}

enqueue入队

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

    }

    入队函数主要做了以下三件事：

1. new一个以入队值为数据的节点
2. 若有头节点，把节点赋给表尾及表尾指针域next，即入队，若无头节点，则新节点既是头节点也是尾节点
3. 节点数size+1

dequeue出队

dequeue() {

        const current = this.#head;

        if (!current) {

            return;

        }

        this.#head = this.#head.next;

        this.#size--;

        return current.value;

    }

    出队函数的作用其实跟数组的shift类似，但数组需要遍历而链表的删除直接更改指针指向即可，哪个效率更高可想而知，下面是函数的理解：

1. 没有头节点即队列为空时直接返回undefined
2. 把头节点改成头节点的指针域next
3. 节点数size-1
4. 最后返回头节点的值

清空队列

clear() {

        this.#head = undefined;

        this.#tail = undefined;

        this.#size = 0;

    }

    清空队列其实就是把头、尾节点置为undefined，并且把节点个数赋为0

遍历队列

* [Symbol.iterator]() {

        let current = this.#head;

        while (current) {

            yield current.value;

            current = current.next;

        }

    }

    遍历队列用的是迭代器，Symbol.iterator 为每一个对象定义了默认的迭代器。该迭代器可以被 for...of 循环使用，也即实现如下测试用例的效果。【ps：迭代器的详细用法也可以看MDN】

结束语

    至此，yocto-queue的源码就算分析完了，源码总共才67行，但却关联很多知识点，以前总觉得数据结构相关的晦涩难懂且极少应用，但工作了之后才发现数据结构其实贯穿日常开发，还是要多思考总结，毕竟风起于青萍之末，浪成于微澜之间！