# Implementing Queue operations in $\Theta(1)$

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?

A linked list is indeed a good idea. In addition to keeping a linked list, add a pointer to the middle item. When you insert an item, check to see if the current list's length is even or odd. If its even - move the pointer to the middle item one forward. Do the same (but backwards) when you are popping an item.

• And you will make a Node to have a pointer to left and one to right? So it's a doubly linked list – Andrei Gabor Jun 11 '20 at 21:12
• Yes a doubly linked list it is. – nir shahar Jun 11 '20 at 21:56

The problem can be solved by keeping two deques $$Q_1$$ and $$Q_2$$ (implemented, e.g., using doubly linked lists) with the invariant that $$Q_1$$ always contains the first $$\lceil n/2 \rceil$$ elements of the queue.

The operations are implemented as follows:

• push($$x$$): push $$x$$ at the beginning of $$Q_1$$. If the invariant is violated, then pop the last element $$y$$ from the end of $$Q_1$$ and push $$y$$ at the front of $$Q_2$$.

• get(): return the element at the beginning of $$Q_1$$.

• pop(): pop the the element at the beginning of $$Q_1$$. If the invariant is violated then pop the first element $$y$$ from the beginning of $$Q_2$$ and push $$y$$ at the back of $$Q_1$$.

• getMiddle(): return the element at the end of $$Q_1$$.

• popMiddle(): pop the element at the end of $$Q_1$$. If the invariant is violated then pop the first element $$y$$ from the beginning of $$Q_2$$ and push $$y$$ at the back of $$Q_1$$.