咱们晓得在 JS 中，删除数组元素有两个办法：pop 与 shift，别离能够删除开端与结尾的元素。

然而同样是删除元素，它们的执行工夫的确不同的。

当数组我的项目较多时，shift 的执行工夫显著长于 pop。

const test = (arrLength) => {  let arr1 = []  console.time(`${arrLength}-arr1`)  for (let i = 0; i < arrLength; i++) {    arr1.push(i)  }  for (let i = 0; i < arrLength; i++) {    arr1.pop()  }  console.timeEnd(`${arrLength}-arr1`)  let arr2 = []  console.time(`${arrLength}-arr2`)  for (let i = 0; i < arrLength; i++) {    arr2.push(i)  }  for (let i = 0; i < arrLength; i++) {    arr2.shift()  }  console.timeEnd(`${arrLength}-arr2`)}test(10 ** 5)test(10 ** 6)

后果如下：

这是因为 pop 删除元素后不须要扭转其余元素的索引，工夫复杂度为 O(1)；而调用 shift 办法删除结尾元素后，须要保护数组的索引，相当于对数组中的所有元素都进行了一次赋值操作，其工夫复杂度为 O(n)

栈与队列

栈与队列是咱们罕用的两种数据结构。

栈的元素先进后出，比方函数栈，函数递归调用时，后调用的函数先执行完。

队列的元素先进先出，比方工作队列，工作依照派发的程序顺次执行。

在 JS 中，栈能够看成只调用 push 与 pop 办法的数组，队列能够看成是只调用 shift 与 push 办法的数组。

然而在之前的例子中也看到了，当解决大量数据时，把数组间接当成队列使用性能十分差。

所以，咱们要设法实现队列这一数据结构。

如何实现？

开始之前咱们要明确实现的指标，咱们实现的队列要提供以下几个性能：

  • 存储数据：队列要可能按序存储数据
  • push：增加元素的惟一办法，将元素增加进队列尾部的办法，并返回队列长度
  • shift：删除元素的惟一办法，将队首元素删除的办法，并返回删除的元素
  • length：能够通过 length 属性拜访队列的长度
  • 拜访元素：个别队列会容许访问队头与队尾的元素

这里介绍通过 假删除数组元素 的形式实现队列。

咱们晓得数组的不能当作队列应用的起因是间接应用 shift 删除元素后会挪动其余元素的索引。

咱们能够本人保护数组的索引，防止删除后频繁挪动。

具体实现是定义一个 offset 变量，记录索引的偏移。

在拜访元素时，通过偏移量的计算，获取正确的后果。

在删除元素时，只用把数组首元素置空，而后偏移加 1。

这期间不进行实在的删除操作，这就是所谓的假删除。

但为了防止数组大小有限增大，咱们设置当偏移量(空元素)大于数组的长度的一半时，就将空元素删除，保障占用空间不超过应用队列大小的两倍。

具体实现代码及正文如下

// 创立一个队列function createQueue() {  const arr = [] // 外部的数组  let offset = 0 // 偏移  // 增加元素，返回队列的长度  const push = (...arg) => {    return arr.push(...arg) - offset  }  // 删除元素，返回被删除的元素  const shift = () => {    const res = arr[offset] // 要返回的删除元素    // 假删除    arr[offset] = undefined    offset++    // 防止数组有限扩充，定期一次性删除后面的空元素    if (offset > arr.length / 2) {      arr.splice(0, offset)      offset = 0    }    return res  }  // 通过 Proxy 拦挡队列的操作  const p = new Proxy(    {},    {      get(target, prop) {        switch (prop) {          case 'push': {            return push          }          case 'shift': {            return shift          }          case 'length': {            // 队列长度 = 数组理论长度 - 偏移            return arr.length - offset          }          default: {            // 元素实在索引 = 要拜访的索引 + 偏移            return arr[Number(prop) + offset]          }        }      },    }  )  return p}const queue = createQueue()console.log(queue.push(0, 1, 2, 3, 4)) // 5console.log(queue[0]) // 0console.log(queue.length) // 5console.log(queue.shift()) // 0console.log(queue[0]) // 1console.log(queue.length) // 4console.log(queue.shift()) // 1console.log(queue.push(5)) // 4console.log(queue[0]) // 2console.log(queue[queue.length - 1]) // 5

测试性能

进行 10/100/1000 万次增删操作，测试队列的性能

const test = (arrLength) => {  let arr1 = []  console.time(`${arrLength}-arr1`)  for (let i = 0; i < arrLength; i++) {    arr1.push(i)  }  for (let i = 0; i < arrLength; i++) {    arr1.pop()  }  console.timeEnd(`${arrLength}-arr1`)  let arr2 = createQueue()  console.time(`${arrLength}-arr2`)  for (let i = 0; i < arrLength; i++) {    arr2.push(i)  }  for (let i = 0; i < arrLength; i++) {    arr2.shift()  }  console.timeEnd(`${arrLength}-arr2`)}test(10 ** 5)test(10 ** 6)test(10 ** 7)function createQueue() {……}

测量后果如下：

能够看出，不论数据多大，性能也只差 4 倍。

因为要进行操作的拦挡与索引偏移的计算，分外的性能开销不可避免，常数倍的性能差距曾经能够满足要求。

结语

如果文中有不了解或不谨严的中央，欢送评论发问。

如果喜爱或有所启发，心愿能点赞关注，激励一下作者。