我们知道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);
}
}
这行吗?
1条答案
按热度按时间eblbsuwk1#
它不会在所有情况下都起作用。这里有两个问题:
1.如果
this.vals.length === 0 && this.indexOfFirst < 0
,则push()
和pop()
不会按预期运行1.如果
this.indexOfFirst
低于Number.MIN_SAFE_INTEGER
,则unshift()
将无法向队列添加值要解决第一个问题,您可以使用
Map
代替Array
沿着indexOfLast
,就像您已经在处理indexOfFirst
一样:要解决第二个问题,您可以使用
BigInt
代替Number
,或者您可以实现一个双向链表,其中每个节点存储一个值沿着指向下一个和上一个节点的指针(从而避免任何数字限制)。