时间戳

首页 > 解决方案 > 堆栈中 .pop() 的实现和队列中的出队

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

问题描述

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

所以这是我使用数组的堆栈。


    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 时

  1. 为什么我们要保留最后一个弹出的元素？
  1. 实现出队时，队列也有同样的问题。

    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]。

  1. 和 Stacks 一样，为什么我们必须保持一个值？

感谢你的帮助。

标签： javascriptdata-structuresstackqueue

解决方案

为什么我们要保留最后一个弹出的元素？如果我们把它留在数组中，这不会占用更多内存吗？

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

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

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

和 Stacks 一样，为什么我们必须保持一个值？

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

如果堆栈或队列中的值是对象引用，那么您可以通过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();
}

推荐阅读