如何實現可尋址的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隊列？

回答

相關問題