javascript - 在 JavaScript 中创建省略索引的数组结构

Question

数组中的索引(维护索引)使 Array.prototype.shift 和 Array.prototype.unshift O(N) 而不是 O(1)。

但是，如果我们只想使用 pop()/push()/shift() 和 unshift() 而从不使用索引进行查找，是否有一种方法可以实现省略索引的 JavaScript 数组？

我想不出办法。 我能想到的唯一方法是使用数组，并且只使用 pop()/push()(因为它们是 O(1))……但即使有多个数组，也不确定是否可行。

如果可能，希望在不使用链表的情况下执行此操作。我使用双向链表实现了此解决方案，但想知道是否可以在不使用链表的情况下执行此操作。

最终目标:尝试创建一个 FIFO 队列，其中所有操作都在恒定时间内进行，而不使用链表。

Answer 1

ES2015 怎么样 Map你用整数索引？

我们将 map 称为 myFIFOMap。

您保留一个first 和last 整数成员作为您的FIFO 类的一部分。将它们都从零开始。

每次你想push()到你的FIFO队列，你调用myFIFOMap.set(++last,item)。 pop() 看起来像这样:

const item = myFIFOMap.get(first); 
myFIFOMap.delete(first++); 
return item;

应该是 O(1) 来推送或弹出。

不要忘记检查边界条件(例如，当 first===last 时不要让它们 pop())。

鉴于 JavaScript 实际上使用 double float ，您应该能够运行 ~2^53 objects在您遇到整数精度问题之前通过您的 FIFO。因此，如果您每秒通过 FIFO 运行 10,000 个项目，那么对于大约 28,000 年的运行时间来说应该是好的。