title: Random access queue data structure
body: <p>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 <em>not</em> insertion or deletion). (To clarify: I am <em>only</em> adding elements to the back of the queue, and <em>only</em> removing elements from the front.) Think of it like a sliding window with a variable size.</p>
  
  <ul>
  <li>Must be unbounded (so a fixed-length circular buffer is out, for instance)</li>
  <li>Don't need to worry about concurrency</li>
  <li>Performance is more important than space requirements (within limits of course: a flat array of 2<sup>64</sup> elements is not exactly practical, for instance)</li>
  <li>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.</li>
  </ul>
  
  <p>Ideally I'm looking for something supporting <code>O(1)</code> operations, but at a minimum I'd like something with sublinear worst-case.</p>
  
  <p>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)</p>