迭代数组中最旧项目的最快方法？（最快的队列实现）

Question

也见编辑

我在 JavaScript 工作，但任何类型的可读伪代码都可以回答我的问题。

我很难描述这一点，所以请随时评论说明 - 我会回答他们并相应地完善我的 post。

本质上，我有一个充当队列的数组，添加项目，处理它们时需要删除它们，最终会添加更多。当我不关心索引时，获取数组中第一项的最快方法是什么？我只想在第一个添加的基础上进行迭代，而不必每次都向下移动数组中的所有条目。另外值得一提的是，我没有遍历数组，我的应用程序有一个主循环，用于检查数组是否在每个循环中都有项目，如果有，它将获取该数据，然后将其从数组中删除。目前为了快速完成此操作，我使用 pop，但现在认识到我每次都需要先获取队列中最旧的项目，而不是最新的。

如果需要更多说明：

在我的应用程序中，我有一些原始数据块，首先需要通过一个函数运行才能准备好供我的应用程序的其他部分使用。每个块都有一个唯一的 ID，我将其传递给函数以便对其进行解析。出于优化目的，我只在需要时解析数据块。

为了做到这一点，我目前的系统是当我意识到我需要一个块被解析时，我将它的唯一 ID 推入一个数组，然后我的应用程序中的一个连续循环不断地检查该数组，看看它是否里面有物品。如果是，它弹出数组的最后一项并将唯一 id 传递给解析函数。

出于性能原因，在循环的每次迭代中，只能解析一个数据块。当多个数据块已经在队列数组中时，问题就出现了，并且在循环完成将数组中已经存在的 ID 传递给函数之前，我向数组添加了更多项。基本上，需要解析的新 ID 在我的循环清除它们之前被添加到数组的末尾。

现在，这还算不错，因为很少需要新数据，但一旦需要，就会同时添加很多 ID，这是应用程序的一个属性，我无法真正更改。

因为我使用的是 pop，所以最近添加的 ID 显然总是首先被解析，但我选择了这种方法，因为我认为它是迭代这样一个队列的最快方法。但是，我开始意识到我宁愿先解析列表中最旧的项目。

本质上，我正在寻找一种方法来循环遍历从最旧到最新的数组，而不必每次都重新组织数组。数组的索引并不重要，我只需要先添加，先解析的行为。

例如，我知道我总是可以只将数组中的第 0 项传递给我的函数，然后将其余条目向下移动，但是，我认为必须向下移动数组中的其余条目是性能成本太高，不值得。如果我只是愚蠢并且那应该没有现实世界的成本请告诉我，但它仍然看起来像是一个创可贴修复。我确信那里有更好的解决方案。

我也对其他数据结构持开放态度，因为数组只包含字符串。

谢谢

编辑：在进行更多谷歌搜索时，我感到脸一红，意识到我描述的问题是堆栈与队列。但现在我的问题转移到当索引对我没有真正价值时什么是最快的队列实现？

Answer 1

下面是javascript中使用单链表的FIFO队列实现。

更多链表信息-> https://www.geeksforgeeks.org/linked-list-set-1-introduction/

// queue implementation with linked list
var ListNode = function(val,next = null){
  
  this.val  = val 
  this.next = next

};

var Queue = function(){
  
  let head = null;
  let tail = null;
  
  this.show = function(){
    
    let curr = head;
    let q = [];
    
    while(curr){
      q.push(curr.val);
      curr = curr.next;
    }
    
    return q.join(' -> ');
  }
  
  this.enqueue = function(item){
    
    let node = new ListNode(item);
    if(!head) {
      head = node;
      tail = node;
    } else {
      tail.next = node;
      tail = node;
    }
    
  }
  
  this.dequeue = function(){
    
    if(!head) return null;
    else {
    
      let first = head;
      head = head.next;
      
      first.next = null;
      
      return first;
    }
    
  }
  
}

var myQueue = new Queue();
myQueue.enqueue(1); // head -> 1 
console.log(myQueue.show())
myQueue.enqueue(2); // head -> 1 -> 2
console.log(myQueue.show())
myQueue.enqueue(3); // head -> 1 -> 2 -> 3
console.log(myQueue.show())
myQueue.dequeue(); // head -> 2 -> 3
console.log(myQueue.show())

迭代数组中最旧项目的最快方法？（最快的队列实现）

Fastest way to iterate through the oldest items in an array? (Fastest implementation of a queue)

javascript

arrays

iteration

queue

loops

迭代数组中最旧项目的最快方法？ （最快的队列实现）

Fastest way to iterate through the oldest items in an array? (Fastest implementation of a queue)

javascript

arrays

iteration

queue

loops

迭代数组中最旧项目的最快方法？（最快的队列实现）