Here is a simple algorithm to implement such queue.
- Tag an increasing number to each element in the queue, called this slotNumber. When the queue is initialized, set slotNumber to zero. When an element is pushed to the queue, increase slotNumber by one and tag it to the element.
- The position of each element in the queue is therefore the difference between their slotNumber and the first element's slotNumber.
I used a variant of this algorithm where I kept two counters instead of just one. I called them pushCounter and popCounter. Each time an element was pushed into the queue, I increased the pushCounter. When an element was popped, I increased the popCounter. The answer is the difference between slotNumber and popCounter.