performance - 现实生活中的人队列数据结构

Question

您将如何为现实生活中的人群队列建模？

考虑到这些主要限制:- 先进先出- 任何时候一个随机元素都可以离开队列- pop 应该总是返回一个仍在队列中的元素- 队列中的任何元素都是唯一可识别的(例如社会安全号码)

我想出的最佳解决方案是同时维护一个 fifo 约束队列和一个哈希集来管理离开的人。当我将一个元素推送到队列中时，我也会将它推送到哈希集中。当我从队列中弹出一个元素时，我也检查了哈希集。如果元素在弹出之前被删除，我将丢弃它并弹出下一个元素。如果该元素仍在哈希集中，我会处理该元素，然后将其从哈希集中删除。在这种情况下，推送和添加、弹出和删除、仅删除操作的时间应该都是 O(1) 还是我错了？

我很幸运，有一个更高效或更优雅的解决方案

Answer 1

我在您的解决方案中看到的一个问题是，您似乎从来没有从哈希集中删除元素(除非我遗漏了一些东西)，这很糟糕 - 尽管每次操作预计 O(1)，但内存无论队列中有多少人，使用率都会不断增加。

我可能已经把它颠倒过来了:

拥有队列中所有人的 HashMap (队列中的人到迭代器)。

对于入队，您还要添加到 map 中，对于出队，您还要从 map 中删除。

对于删除，由于散列映射包含迭代器，因此在删除操作的情况下，您可以从散列映射和队列中删除该人。这假设队列是作为(双)链表实现的，并且仍然是 O(1)。

如果您不熟悉迭代器，它基本上只是指向链表中适用节点的引用或指针。