堆栈中的 .pop() 和队列中的出列的实现

Question

我目前正在研究堆栈和队列，在实现 pop 和 dequeue 时，有一件事我悄悄地没有真正理解。

这是我使用数组的 Stack。


    const Stack = function() {
      this.store = []; 
      this.top = 0; 
    }
    
    Stack.prototype.push = function(value) {
      return this.store[this.top++] = value
    }
    
    Stack.prototype.pop = function() {
      if (!this.top) return;
    
      return this.store[--this.top]
    }

假设我创建了我的堆栈的新实例并添加了几个数字然后弹出一个。

    const stack= new Stack();
    
    stack.push(1) // store= [1], top = 1
    stack.push(2) // store= [1, 2], top =2
    stack.push(3) // store= [1, 2, 3], top = 3
    
    stack.pop() // store = [1,2,3], top = 2

在我弹出我的最后一个数字后，我仍然留在同一家商店，只是顶部减少了 1。

我不明白的是，在实施 Stack 时

为什么我们保留最后弹出的元素？

如果我们在数组中把它去掉，会不会占用更多的内存？

实施出列时，队列也有同样的问题。


    const Queue = function() {
      this.store = []; // stores data in an array
      this.first = this.last = 0; // tracks first and last position in the queue
    }
    
    Queue.prototype.enqueue = function(value) {
      return this.store[this.last++] = value
    }
    
    Queue.prototype.dequeue = function() {
      const dequeued = this.store[this.first];
    
      if (this.fist === this.last) return;
      this.store[this.first] = null;
      this.first++
    
      return dequeued;
    }
    
    const queue = new Queue();
    
    queue.enqueue(1) //store = [1], last = 1, first = 0
    queue.enqueue(2) //store = [1,2], last = 2, first = 0
    queue.enqueue(3) //store = [1,2,3], last = 3, first = 0
    
    console.log(queue.dequeue()) //store = [null,2,3], last = 3, first = 1

对于出队，当删除队列中的第一项时，我只是简单地将值替换为 null 而不是真正获得 [2,3]。

与 Stacks 相同，为什么我们必须保留一个值？

感谢您的帮助。

Answer 1

why do we keep the last element that was popped off? If we leave this off in the array, won't this take up more memory?

是的，该实现从不缩小数组大小。该数组将保持其最大长度。但是，当新值被压入堆栈时，弹出的值将是 reused/ovewritten 。当您从数组中弹出值时，这不会缩小数组。这可能会或可能不会占用更多内存。数组是在内部实现的，其中有一些额外的松弛度，因此每次您将它们的长度增加或减少一点点时，它们都不必重新分配新大小的内存并将现有数组复制到新块。因此，在数组末尾保留一些额外的元素不一定会改变很多或根本不会改变。现在，如果您将数千个元素压入堆栈，然后将它们全部弹出，那么您的空堆栈中确实会有一堆未使用的内存，这将是低效的。所以，这实际上取决于您要压入堆栈的数量。

您可以很容易地检查末尾有多少额外字节（如果超过某个阈值），然后重置数组的长度以允许系统重新分配一个较小的数组。除非你有无数个这样的堆栈，或者除非你在堆栈上放置了大量的项目，否则在宏伟的计划中这一切都可能无关紧要，但如果你有一个被证明对你的应用程序很重要的理由，你可以优化它以在某些情况下使用更少的内存。

For dequeue, I am simply just replacing the value with null instead of really getting [2,3], when removing the first item in the queue.

Same as Stacks, why do we have to keep a value in place?

队列实现似乎更有问题，因为它的实现似乎会永远变大，因为 this.first 和 this.last 只会递增。没有保留旧数据的队列实现原因。为了防止永远增长，这将需要向下复制并调整数组大小或切换到更多 linked 列表类型实现，您可以在其中自由地删除第一个 link 或添加最后一个 link 没有数组的限制。

如果堆栈或队列中的值是对象引用，那么您可以通过在弹出或出队后将它们的堆栈或队列值设置为 null 来减轻它们的影响。这将允许对象在没有其他人使用它们时被垃圾收集。

一个不累积内存的简单队列是这样的：

const Queue = function() {
  this.store = []; // stores data in an array
}

Queue.prototype.enqueue = function(value) {
  // add to end of the queue
  this.store.push(value);
}

Queue.prototype.dequeue = function() {
  // remove oldest value from the start of the queue
  return this.store.shift();
}

堆栈中的 .pop() 和队列中的出列的实现

Implementation of .pop() in Stacks and dequeue in Queues

javascript

queue

stack

data-structures