67行JS代码实现队列取代数组，面试官刮目相看

若川

发布于 2022-06-03 11:05:03

4690

发布于 2022-06-03 11:05:03

文章被收录于专栏：若川视野

这是来自源码共读群中大二的小伙伴投稿，写的非常好，图文并茂，关键还写了好多篇笔记了。Part11. 前言

1.1 这个库，是干啥的

如果你项目中要用到一个非常大的数组，并且你经常需要使用这两个操作：

Array.push() 在末端添加一个元素.
Array.shift()在取出队列首端的一个元素，整个队列往前移，这样原先排第二的元素现在排在了第一

如果学过数据结构，就会敏锐地发现，诶这两个操作，不就是在模拟队列吗

queue 队列是一个有序的元素列表，其中一个元素插入到队列的末尾，然后从队列的前面移除。队列的工作原理是**先进先出(FIFO)**。

JS 没有queue这个数据结构，用数组模拟就好了，真方便！ nonono，回到开头，当数据量较小的时候，似乎没什么影响，但如果数据量较大，性能就会严重下降 这是因为在底层实现中，数组是顺序存储的，当你shift的时候，会先取出队列首端的一个元素，整个队列往前移——整个操作的事件时间复杂度是**O(n)** 如果你的项目正如上面我所说的情况，那么你很可能就需要这个包 yocto-queue，它能让你的shift操作时间复杂度降为O(1)。（在这库里面shift用的是dequeue方法）

1.2 你能学到

ES6 中的 class
链表和数组的区别，时间复杂度
JS 实现链表的方法
学习 Symbol.iterator 的使用场景
调试源码

Part22. 准备

2.1 了解API

import Queue from 'yocto-queue';

const queue = new Queue();

queue.enqueue('🦄');
queue.enqueue('🌈');

console.log(queue.size);
//=> 2

console.log(...queue);
//=> '🦄 🌈'

console.log(queue.dequeue());
//=> '🦄'

console.log(queue.dequeue());
//=> '🌈'

queue = new Queue()

The instance is an Iterable, which means you can iterate over the queue front to back with a “for…of” loop, or use spreading to convert the queue to an array. Don't do this unless you really need to though, since it's slow.

该实例是可枚举的，也就是说你可以用for...of来遍历，并且可以用扩展运算符将其变为数组，但是尽量不要这样做，这样性能很差

.enqueue(value)

添加一个元素到队尾

.dequeue()

删去队头，并返回被删除的值 || 或者是 undefined（队列本来就已经为空的情况）

.clear()

清空队列

.size

返回队列的大小

Part33 看看源码

3.1 环境准备

# 克隆官方仓库
git clone https://github.com/sindresorhus/yocto-queue.git
cd .\yocto-queue\
npm install
code .

3.3 调试源码

查看 package.json文件来确定主入口为 index.js

demo

新建文件夹examples，存放 demo index.js

// yocto-queue/examples/index.js
import Queue from "../index.js";

const queue = new Queue(); //此处打断点
queue.enqueue("⛵");
queue.enqueue("🌊");

console.log(queue.dequeue());

console.log(queue.size);
for (let q of queue) {
 console.log(q);
}
queue.clear();

node examples/index.js或者直接F5也可以即可开始调试源码，其实这个代码复杂度不手动调试也可以的，但是通过调试可以让你很明确地看到哪一步代码用到了哪里的东西

3.4 理解源码

源码

Queue中，#head和#tail可以视作虚拟结点，只是分别用来指向头和尾结点的。每次遍历的时候先找到头结点（#head指向的结点），然后通过每个结点的next指针往后走。即使只有头结点也能组成该链表——慢慢遍历总能到最后面，但是显然这样效率就低了，所以还有一个专门的尾指针#tail，方便尾部插入结点源码总览：

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

分步解析

enqueue

queue.enqueue("⛵");时，会创造Queue中第一个实例node，第一个结点自然头和尾都指向他自己

if (this.#head) {
  //...
} else {
  this.#head = node;
  this.#tail = node;
}

image.png

queue.enqueue("🌊");随后我们添加第二个结点

if (this.#head) {
  this.#tail.next = node;
  this.#tail = node;
} else {
  //...
}

实际上我们可以发现，这就是尾插法

dequeue

console.log(queue.dequeue());

dequeue() {
  const current = this.#head;   //获取当前
  if (!current) {
    return;
  }

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

image.png

size

console.log(queue.size);

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

这里用到了 class 中 getters

⭐for...of

这里是本文的一个重点

这里实现了Queue这个对象可以通过for...of来进行遍历，即让它可以迭代。想要让对象可迭代，需要添加一个Symbol.iterator方法，这个方法专门用来使对象可迭代的内建symbol。通过调试我们也可以知道，当进入for...of，他就会进入Symbol.iterator这个方法，（如果没找到，就会报错，像数组那些对象都是有内置该方法的），该方法必须返回一个迭代器—— 一个有next方法的对象。像这样使用：

let range = {
  from: 1,
  to: 5,

  [Symbol.iterator]() { // 在 for..of 循环开始时被调用一次
    return {
      current: this.from,
      last: this.to,

      next() { // 每次迭代时都会被调用，来获取下一个值
        if (this.current <= this.last) {
          return { done: false, value: this.current++ };
        } else {
          return { done: true };
        }
      }
    };
  }
};

for(let value of range) {
  alert(value); // 1，然后 2，然后 3，然后 4，然后 5
}

而源码中并不是这样的，而是这样：

* [Symbol.iterator]() {
  let current = this.#head; //通过current记录当前迭代进程

  while (current) {   //循环取值，直到没有
    yield current.value;  //取值，并返回
    current = current.next;//通过next往下一个走
  }
}

这是因为这里并不仅是使用了Symbol.iterator

⭐生成器

生成器是 ES6 新增的一个极为灵活的结构，拥有在一个函数块内暂停和恢复代码执行的能力。这种能力具有深远的影响，比如使用生成器可以自定义迭代器和实现协程。

在函数前面加一个星号*，则表示它是一个生成器。调用生成器函数会产生一个生成器对象，其一开始处于暂停状态，该对象也实现了Iterator接口，通过调next()使其转为开始或者恢复执行状态。生成器函数在遇到yield关键字前会正常执行，遇到该关键字后，执行会停止，函数作用域的状态被保留 —— 有点像函数的中间返回语句，它能让函数返回一个值出去，但是函数仍能继续执行。随后通过在生成器对象上调用next方法恢复执行。实际上，很少在生成器对象上显式调用next()，而是将其作为可迭代对象——

function* generatorFn(){
  yield 1;
  yield 2;
  yield 3;
}
for(let i of generatorFn()){
  console.log(i) 
}
//1
//2
//3

让我们回到源码中

for (let q of queue) {
 console.log(q);
}

结合上面对Symbol.iterator的理解

当进入for...of，他就会进入Symbol.iterator这个方法

也就是说这样调用时，实际上就是

for (let q of queue[Symbol.iterator]()) {
 console.log(q);
}

让[Symbol.iterator]这个函数变为了生成器函数，并将其作为可迭代对象！大大地减少了代码量~

clear

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

很简单，直接将头指针和尾指针指向的值改为undefined，size也设置为0，剩下的就靠JS自身的垃圾回收机制了，本文就不涉及了。

Part44. 学习资源

数组
class
Symbol.iterator
垃圾回收机制
红宝书 7.3 生成器

Part55. 总结 & 收获

复习了 ES6 中的 class以及相关语法
链表和数组的区别，时间复杂度，通过指针的空间来省下按顺序遍历的时间——一种空间换时间的性能优化策略
JS 实现链表的方法，有了class这个语法后，和其他语言差不多了
- Node结点，存当前value以及与用于相邻结点相连的指针
复习 Symbol.iterator 的使用场景以及生成器这个平时可能用的较少的知识点

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-04-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

javascript

ecmascript

本文分享自若川视野微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

javascript

ecmascript

登录后参与评论

0 条评论

热度