How to implement an addressable FIFO queue?

Question

I'm currently looking for a data structure with all O(1) operations

insert(K, V): Insert a value at the end of the queue.
remove_key(K): Remove the value from the queue corresponding to the provided key.
remove_head(): Remove the value from the front of the queue (the oldest one).

The only reasonably easy to implement thing I can think of is using a doubly linked list as the primary data structure, and keeping pointers to the list nodes in a hash table, which would get the desired asymptotic behavior, however this might not be the most efficient option in actual runtime.

I found "addressable priority queues" in the literature, but they are rather complicated (and maybe even more expensive) data structures, so I was wondering if someone has a better suggestion. It seems no one implemented something like this for Rust so far, which is why I'm hoping it doesn't get too complicated.

Your idea of using a separate hash table is the standard implementation. An addressable priority queue uses the same concept. If you're trying to implement your priority queue with a binary heap, then it gets complicated. But if you use something like a Pairing heap, it's not any more complicated than your double-linked list idea. — Jim Mischel
– Jim Mischel, Commented Oct 6, 2017 at 20:20
A bit late but if anyone still looks for a working solution, I wrote the following crate a while ago (not actively maintaing it anymore): crates.io/crates/addressable_queue — evotopid
– evotopid, Commented Jun 16, 2020 at 15:03

Juan Serrats · Accepted Answer · 2017-10-06 21:52:07Z

0

I would use a pub struct VecDeque<T> and use pop_front() instead of remove_head().

See the doc: VecDeque

edited Oct 6, 2017 at 21:52

Juan Serrats

1,3585 gold badges24 silver badges31 bronze badges

answered Oct 6, 2017 at 11:36

DevOrc

292 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

evotopid Over a year ago

The problem is remove_key(K). I could use a (growable) ring buffer like VecDeque but then remove_key(K) would be O(n) since I would have to iterate all items in the worst case. I was just wondering if there is a better way to do it, because otherwise I might even use a FIFO queue and just mark elements as deleted and make remove_head() skip the deleted elements.

Serge Mosin · Accepted Answer · 2020-06-16 08:57:57Z

0

Here I implemented an Addressable Binary Heap in Python, no third-party dependencies.

answered Jun 16, 2020 at 8:57

Serge Mosin

3961 gold badge6 silver badges15 bronze badges

Collectives™ on Stack Overflow

How to implement an addressable FIFO queue?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related