Random access queue data structure

Question

I'm looking for a data structure to implement a random access queue ("straight" queue, not priority). That is, standard queue operations (push to back, delete from front, size/isEmpty), but with the wrinkle that I want to be able to do array-like indexing into the middle of the queue (but not insertion or deletion). (To clarify: I am only adding elements to the back of the queue, and only removing elements from the front.) Think of it like a sliding window with a variable size.

• Must be unbounded (so a fixed-length circular buffer is out, for instance)
• Don't need to worry about concurrency
• Performance is more important than space requirements (within limits of course: a flat array of 2⁶⁴ elements is not exactly practical, for instance)
• Consistency of performance is more important than straight performance: true worst cases as opposed to amortized: so (most) array-based data structures are out, as far as I know.

Ideally I'm looking for something supporting O(1) operations, but at a minimum I'd like something with sublinear worst-case.

Note: I'm not looking for an implementation or library, so much as I'm looking for a data structure. (This is a matter of personal curiosity, following a related question asked in a recent exam of mine)

Answer 1

A resizable array would give O(1) amortized cost to insert and delete and O(1) random access.

---

Alternatively, you could implement the queue using an order statistics tree.

An order statistics tree is basically a binary search tree (specifically a self-balancing one to get efficient performance), but each node stores one additional value, which is the size of the subtree rooted at that node (i.e. the number of nodes below it).

Insertion would involve inserting the value in the biggest position, and deletion would delete from the smallest. Random access would just involve using the sizes of the subtrees to traverse to the node corresponding to the given index.

This would result in O(log n) performance for all operations.

---

Similar to the above, but simpler implementation-wise, we could just use a standard binary search tree, indexed by an ever-increasing unique ID - every value inserted would get an ID of the last ID inserted plus one. To do random-access, you could just offset the smallest ID in the tree by the given index and look for that ID in the tree.

If the IDs were to ever overflow, you could continue on another BST, and eventually get rid of the first if it empties - doing this isn't ideal, but it may still be simpler that implementing ones own tree (as order statistics trees aren't common in libraries).