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

2022-06-03 11:05:03 浏览数 (1)

这是来自源码共读群中大二的小伙伴投稿,写的非常好,图文并茂,关键还写了好多篇笔记了。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

代码语言:javascript复制
import Queue from 'yocto-queue';

const queue = new Queue();

queue.enqueue('


	

0 人点赞