Best data structure for a queue with random reads?

Question

Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads.

Imagine an algorithm that maintains a list of elements so that:

1. It reads an element from the list based on its key.
2. It then inserts that element as the last element in the list.
3. On demand it returns all entities in the order in which they were inserted.

And I am looking for a solution that is faster than a naive implementation based on a linked list, which would have complexity O(n) for all three parameters - search, insert as the last element, and return all elements in the inserted order.

Such a data structure should probably:

1. Allow for a quick lookup of the key (e.g. a tree, a hashmap)
2. Maintain the order in which elements were inserted (e.g. a list, a queue)

---

A practical example is a list of agents receiving calls. When an agent is called, it's fetched from the list, and when it finishes the call, it's put at the back of the list. Therefore the agent that is first in that list is the most idle agent (waiting for a call the longest). In other words, the list would be sorted according to agent's idleness.

---

Another example implementation could be based on two structures, one dictionary and one array, referencing each other. The dictionary would keep the index in the array as the value and the array would keep the key as the value. Then the element would be removed from the array by looking up the value/index in the dictionary and the dictionary would be updated with the new index once the element was put as the last element in the array.

Answer 1

Take any dictionary data structure and link its entries in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure.

In search trees, this is called threading. It gives you constant-time access to the first and last element, respectively, and maintaining the threading takes only constant-time overhead for each dictionary or queue operation. As a consequence, you get $\Theta(\log n)$ access by key, $O(1)$ access to front and back of the queue (without modification), and $\Theta(\log n)$ insertion and deletion.

If you use hashtables you get $O(1)$/$\Theta(n)$ (AC/WC) access by key, $O(1)$ access to front and back of the queue (without modification), and $O(1)$/$\Theta(n)$ (AC/WC) insertion and deletion. The usual caveats apply.