算法 - 找到项目在队列中的位置

Question

我有一个任意对象的数组

1. 每个对象都有一个唯一的id
2. 新对象添加到队列的末尾(tail)
3. 对象从顶部移除以进行处理(先进先出)
4. 如果需要，可以删除待处理的对象。

问题是在给定 id 的情况下从尾部找到对象在队列中的当前位置。

最快的方法是什么？需要明确的是，我不想要来自 id 的对象，所以 HashMap 不是解决方案。我真正需要的是职位。

我们想到了两种方式:

1. 蛮力，循环查找
2. 在对象中添加一个新字段，该字段存储一个全局索引，该索引会随着每个添加到队列中的对象而递增。然后我们可以通过检查存储在最后一个项目和这个项目中的全局索引来快速获得位置。然而，唯一复杂的是，如果删除其中一个对象，则需要更新下面所有项目的全局索引。

有什么更好的主意吗？请提出建议。

Answer 1

最简单的方法是将 FIFO 表示为双向链表。此列表可以是Object(这意味着如果您有一个 ID，您还需要一个映射， HashMap 或其他方法，从 ID 到对象)，或独立的 FIFO 节点(在这种情况下，您会有一个从 ID 到节点地址的映射)。