如何实现可寻址的FIFO队列？

我目前寻找与所有O（1）的操作如何实现可寻址的FIFO队列？

插入的数据结构（K，V）：在所述队列的末尾插入的值。
remove_key（K）：从与提供的键对应的队列中删除值。
remove_head（）：从队列前面（最早的那个）中删除值。

我能想到的唯一比较容易实现的事情是使用双向链表作为主数据结构，并且将指针指向哈希表中的列表节点，这会获得所需的渐近行为，但是这可能不是实际运行时最有效的选项。

我在文献中发现了“可寻址的优先级队列”，但它们相当复杂（甚至可能更昂贵）的数据结构，所以我想知道是否有人有更好的建议。到目前为止，似乎没有人为Rust实现过这样的功能，这就是为什么我希望它不会太复杂。

来源

2017-10-06 evotopid

你使用一个单独的哈希表的想法是标准的落实。可寻址的优先级队列使用相同的概念。如果你想用二进制堆实现你的优先级队列，那么它会变得复杂。但是如果你使用Pairing heap这样的东西，那么它不会比你的双链表想法更复杂。 –

我会使用pub struct VecDeque<T>并使用pop_front()而不是remove_head()。

看到该文档：VecDeque

来源

2017-10-06 11:36:14 user8731914

问题是'remove_key（K）'。我可以使用一个（可扩展的）环形缓冲区，比如'VecDeque'，但是'remove_key（K）'将会是'O（n）'，因为我必须在最坏的情况下迭代所有的项目。我只是想知道是否有更好的方法来实现它，否则我甚至可能会使用FIFO队列，并将元素标记为已删除，并使remove_head（）跳过已删除的元素。 – evotopid

如何实现可寻址的FIFO队列？

回答

相关问题