We want to implement a Queue which has two special operations besides the regular Queue operations: $ getMiddle$ (returns the element from the middle of the Queue, for example, if the Queue has 7 elements, it returns the 4th element, if the Queue has 6 elements, it returns the 3rd or the 4th) and $ popMiddle$ (removes the middle element). We want both of these operations and all the other Queue operations to run in $ \theta(1)$ . Pick a suitable data structure for representing the Queue, implement the $ popMiddle$ , pop and push operations and explain in short how the other operations would be implemented.

I was thinking that the linked list would be a good pick if we keep in mind also the tail. But there is a problem when popping the middle because we have to iterate until there. An array would not be good because when erasnig we have to move all the elements to the left, if not there is no suitable formula to find the middle. Does somebody have better ideas?