我正在参与AdminJS会员专属活动-源码共读第一期，点击参与。
前言
本文主要分析的是 yocto-queue 队列链表的源码，GitHub 地址github.com/sindresorhu…。
队列
在分析源码之前，首先需要了解队列这种数据结构。
队列是只允许在尾部进行插入操作，在头部进行删除操作的数据结构。队列的尾部又叫队尾，头部又叫队头。插入操作又称入队，删除操作又称出队。
如上图所示，如果想添加数据只能从 9 后面开始添加，因为这时候 9 是队尾；删除数据只能从 1 开始删除，因为 1 是 队头。
队列的这种特性又叫先进先出（First In First Out），简称 FIFO，因为先添加进来的元素先被删除。
在 JavaScript 当中，可以通过数组的 push() 和 shift() 方法让数组成为队列。
shift()方法从数组中删除第一个元素，并返回该元素的值。
push()方法将一个或多个元素添加到数组的末尾。
仔细一看，push() 方法就是入队，shift() 方法就是出队。我们利用这两个方法来简单地实现一个队列：
const queue = [];
queue.push(1); // 入队
queue.push(2); // 入队
queue.push(3); // 入队
queue.push(4); // 入队
console.log(queue); // [1,2,3,4]
queue.shift(); // 出队
queue.shift(); // 出队
console.log(queue) // [3,4]
但是我们知道，数组的优点是，获取第 i 个数据的效率高；缺点是，插入和删除第 i 个数据的效率低（i 是数组的索引）。
shift() 方法是指删除第一个数据，也就意味需要向前移动后面的每一个数据，时间复杂度为 O(n) 。
push() 方法是在最后一个位置添加数据，其他元素不需要做任何操作，时间复杂度为 O(1)。
由于 shift() 方法的时间复杂度不是常数（O(1)），所以数组并不适合用来实现队列。
那有没有一种数据结构，能让删除第一个数据的时间复杂度将为 O(1) 呢？有的，那就是下文要介绍的链表数据结构。
链表
什么是链表？最直观的理解就是像一条链子，每一个元素通过某种方式与下一个元素进行相连，一环扣一环。
在 JavaScript 当中，我们可以通过对象来实现链表，这个对象又叫节点对象，有两个属性，value 和 next，value 表示当前元素的值，相当于上图的1，2，3，4数值，next 表示指向下一个节点对象，相当于和下一个元素进行相连（下文都用元素来代替节点对象的说法）。具体实现代码如下：
class Node {
value;
next;
constructor(value) {
this.value = value;
this.next = null;
}
}
let head; // 表示链表的头部
let tail; // 表示链表的尾部
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);
// 每个元素与下一个元素相连
node1.next = node2;
node2.next = node3;
node3.next = node4;
head = node1;
tail = node4;
变量 head 和 tail 表示链表的头部和尾部，这样就可以通过这两个变量来表示整个链表。
试想一下，如果我们要删除链表的第一个元素，是不是只需要两步操作：
- 将变量
head赋值为第二个元素（node2）。 - 将第一个元素的
next属性赋值为null（node1.next赋值为null），第一个元素（node1）与整个链表断开。
其他元素不需要做任何操作，这两步操作的时间复杂度都是 O(1)，因此链表删除第一个元素的效率非常高。
同样，在链表尾部增加元素也只需要进行两步操作：
- 将变量
tail.next赋值为下一个节点对象node5 - 将变量
tail赋值为node5，node5成为链表尾部的元素。
所以，链表插入和删除元素的效率高，适合用来实现队列（yocto-queue 源码内部同样是利用了链表，且看下文分析~）。
由于链表并没有像数组那样有索引，所以如果想获取第 i 个元素，只能一个一个获取，直到第 i 个元素，由此可以得出结论：链表查找元素的时间复杂度是 O(n)，效率比较低。
通过与数组的比较，我们可以很强烈地感受到，数组的优点就是链表的缺点，数组的缺点就链表的优点。
源码分析
先来看看 yocto-queue 的使用方式：
import Queue from 'yocto-queue';
const queue = new Queue();
queue.enqueue('