共计 2635 个字符，预计需要花费 7 分钟才能阅读完成。
咱们晓得在 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)) // 5
console.log(queue[0]) // 0
console.log(queue.length) // 5
console.log(queue.shift()) // 0
console.log(queue[0]) // 1
console.log(queue.length) // 4
console.log(queue.shift()) // 1
console.log(queue.push(5)) // 4
console.log(queue[0]) // 2
console.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 倍。
因为要进行操作的拦挡与索引偏移的计算，分外的性能开销不可避免，常数倍的性能差距曾经能够满足要求。
结语
如果文中有不了解或不谨严的中央，欢送评论发问。
如果喜爱或有所启发，心愿能点赞关注，激励一下作者。
