Persistent random-access queue
Yes there is a data structure which name is  Treap   You can also do other things too (ex. range sum, range min-max, etc.) using this or you can also use BBST (Balanced binary search tree like  AVL ).  

Okay i will explain some terms i am assuming you have some Knowledge about Trees and BST(Binary search Tree) 
Q. What Treap is? 
A. Treap = Tree + Heap (in easy way) 

Q. Use of Treap?  
A. its randomized balanced tree basically its contain 2 values first one is data and second is rank (data, rank) and it has two property using data we keep BST(Binary search Tree) property it mean smaller than data will go on left side and bigger will be on right side and rank keep heap property its your choice that you want min heap aur max heap property. trick here is that rank is given uniformly random. So when we heapify using rank height of tree will not exceed O(LogN). so in easy implementation we can get a self balanced binary search tree.  

Q. How to implement above requirements? 
A. Insert and Delete methods are easy and equal to BST's methods 

struct Node *insert(struct Node *root, int pos, int data) {
  if(root == dummy) {
    ptr -&gt;left = ptr -&gt;rig = dummy;
    ptr -&gt;size = 1;
    ptr -&gt;pri = rand();
    ptr -&gt;data = data;
    return ptr++;
  } else if(root -&gt;left -&gt;size &gt;= pos) {
    root -&gt;left = insert(root -&gt;left, pos, data);
    if(root -&gt;left -&gt;pri &gt; root -&gt;pri) root = rot(root, root -&gt;left);
  } else {
    root -&gt;rig = insert(root -&gt;rig, pos - root -&gt;left -&gt;size - 1, data);
    if(root -&gt;rig -&gt;pri &gt; root -&gt;pri) root = rot(root, root -&gt;rig);
  }
  update(root);
  return root;
}


here you can see 2 methods which are unknown to you actually one it rot which is rotation when our tree violate heap property and update where you can update your tree's attribute here we keeping size so you can updated this information here 

Delete method is homework for you it will be same as insert in above code pos define that you want to insert an element in between pos-1 pos. 

okay now lets come on your requirements :

enqueue -&gt; call insert and pos will be root -&gt;size
denqueue -&gt; call delete 
lookup -&gt; search method same as binary search tree's search method
update , insert -&gt; call insert
length -&gt; root -&gt;size