javascript - JavaScript 队列的 O(1) 删除

Question

我如何在 JavaScript 中创建一个队列，我可以在接近 O(1)/常数的时间内添加/删除元素？现在我有一个简单的数组作为队列，但要找到要删除的元素，我必须遍历数组，然后调用 Array.prototype.splice。

不仅如此，如果你有一个基于简单数组的 FIFO 队列，你将需要调用 Array.prototype.shift 或 Array.prototype.unshift，并且两者都是 O(N)，因为它们必须更新数组中每个项目的索引。

所以我希望在列表/队列中的任何位置不断插入/删除元素。如果您尝试将其放入 FIFO 队列，普通数组似乎不会产生。

Answer 1

我已经考虑了一段时间，我所能想到的就是一个双向链表。双向链表允许我们在常数时间内从队列中添加/删除项目。

在这里查看答案:

https://www.quora.com/How-can-I-create-a-queue-in-JavaScript-where-I-can-search-for-or-remove-elements-in-near-O-1-time-Right-now-I-have-a-simple-array-as-a-queue-but-to-find-an-element-to-delete-I-have-to-go-through-the-array-and-then

这是一个似乎有效的实现:

https://github.com/ORESoftware/linked-queue

为什么这有效的一个简单例子是，对于一个数组，每个 shift/unshift 调用是 O(N)，所以下面需要 80 秒!

const values = [];

const t = Date.now();

for (let i = 0; i < 100000; i++) {
  values.unshift({});
}

console.log('total time:', Date.now() - t); // 80 seconds!

但是如果我们添加到队列的前面，使用上面的库，只需要 60 毫秒。相差2个数量级以上。巨大。

const {LinkedQueue} = require('@oresoftware/linked-queue');

const q = new LinkedQueue();

const t = Date.now();

for (let i = 0; i < 100000; i++) {
  q.addToFront({});
}

console.log('total time:', Date.now() - t);  // 60 milliseconds!