Keyed queues with depth queries and delete I'm interested in a data structure (let's call it a DMV queue, or DMV for short) over keys (say, strings) with the following operations:


empty is a DMV containing no keys.
enqueue(q,k) adds the key k to the back of the DMV q, unless k is already in q, in which case it does nothing.
dequeue(q) deletes the key at the front of the DMV q, if one exists, and returns it.
delete(q,k) removes the key k from the DMV q.
depth(q,k) returns an natural number indicating the approximate number of keys between the key k and the front of the DMV q. Let $k_q$ denote the exact number of keys between k and the front of q. Then there must be some c such that for all k and q, $k_q/c$ &lt; depth(q,k) &lt; $ck_q$.


I think I know how to provide the queue operations in $\Theta(1)$ time and delete and depth in $\Theta(\lg n)$ time (all expected amortized). Is it possible to do better?

My proposed solution is as follows: Maintain a balanced tree with $O(1)$ operations at the ends. Nearly any finger tree will do. This tree will store the keys in queue order at its nodes. Also, annotate every non-spine node with its number of descendants.

Keep a hash table mapping keys to pointers to nodes in the tree.

To enqueue a key k, add k to the back of the tree. This invalidates $O(1)$ node pointers and creates $O(1)$ new node pointers, so we need only perform $O(1)$ hash table operations. Dequeue is similar.

To delete a key, we look it up in the hash table and find its location in the tree, then delete it from the tree. This takes $O(\lg n)$ time in the tree, and invalidates $O(\lg n)$ slots in the hash table. We must also maintain non-spine node size annotations in the tree, but this also only takes logarithmic time.

To find the depth of a key, we first annotate the spine nodes of the tree with their number of descendants. This takes $O(\lg n)$ time. We then look up the key in the hash table and find its location in the tree. We then follow parent pointers until we reach the root, summing the annotations at left siblings. Note that this is the exact depth.
Your solution can be modified to do everything in $O(1)$ amortized time. Instead of maintaining a balanced tree, just keep track of the number of successful enqueue operations (those in which something was actually added to the back of the queue) and attach that number to queue along with the item during a successful enqueue operation. To find the depth of a key, just take the difference between the number of successful enqueues when it was enqueued, and the number of successful enqueues when the item currently at the front of the queue was enqueued. Note that this gives exact depth.

If you're worried about storing excessively large values after many enqueue and dequeue operations, you can also keep track of the size of the queue and whenever the size is less than half the number of enqueues, re-number the number of enqueues for each entry to 1 through the size, and reset the number of enqueues to the size. Everything takes constant amortized time and each key takes at most one more bit than necessary to represent its depth at insertion.