不使用shift()从Array的前面删除项

Question

我们知道Array.prototype.shift()/Array.prototype.unshift()是CPU密集型的，因为它们更新数组中的所有索引。我想创建一个基本队列，并更新索引。

class MyQueue {
vals = [1,2,3];
indexOfFirst = 0;
shift(){
const val = this.vals[this.indexOfFirst];
delete this.vals[this.indexOfFirst];
this.indexOfFirst++;
return val;
}
unshift(val){
this.indexOfFirst--;
this.vals[this.indexOfFirst] = val;
}
pop(){
return this.vals.pop()
}
push(v: any){
return this.vals.push(v);
}
}

可以吗?

Answer 1

并非在所有情况下都有效。这里有两个问题:

1. 如果this.vals.length === 0 && this.indexOfFirst < 0，那么push()和pop()将不符合期望
2. 如果this.indexOfFirst低于Number.MIN_SAFE_INTEGER，则unshift()将无法向队列添加值

要解决第一个问题，您可以使用Map代替Array以及indexOfLast，就像您已经处理indexOfFirst一样:

class Queue {
indexedVals = new Map();
indexOfFirst = 0;
indexOfLast = -1;
constructor(vals) {
if (vals) for (const val of vals) this.push(val);
}
shift() {
if (this.indexOfFirst > this.indexOfLast) return;
const val = this.indexedVals.get(this.indexOfFirst);
this.indexedVals.delete(this.indexOfFirst++);
return val;
}
unshift(val) {
this.indexedVals.set(--this.indexOfFirst, val);
}
pop() {
if (this.indexOfLast < this.indexOfFirst) return;
const val = this.indexedVals.get(this.indexOfLast);
this.indexedVals.delete(this.indexOfLast--);
return val;
}
push(val) {
this.indexedVals.set(++this.indexOfLast, val);
}
}

要解决第二个问题，你可以使用BigInt代替Number，或者你可以实现一个双链表，其中每个节点存储一个值以及指向下一个和上一个节点的指针(从而避免任何数字限制)。