javascript 不使用shift()从阵列前面删除项目

wljmcqd8  于 2022-12-28  发布在  Java
关注(0)|答案(1)|浏览(145)

我们知道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);
 }

}

这行吗?

eblbsuwk

eblbsuwk1#

它不会在所有情况下都起作用。这里有两个问题:
1.如果this.vals.length === 0 && this.indexOfFirst < 0,则push()pop()不会按预期运行
1.如果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,或者您可以实现一个双向链表,其中每个节点存储一个值沿着指向下一个和上一个节点的指针(从而避免任何数字限制)。

相关问题