Friday, August 12, 2011

A queue whose elements know their positions

Recently I needed a data structure that could support FIFO access and that every item in it would know about their position. Think about a queue in real life. The first person in the queue knows he is next. The second one knows he will be next after one person. You can come up to anyone randomly in the queue and ask "when is your turn." He will be able to tell you "after X more persons."

Here is a simple algorithm to implement such queue.

  1. 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.
  2. The position of each element in the queue is therefore the difference between their slotNumber and the first element's slotNumber.
This algorithm was devised by an intern in our company.

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.

No comments:

Post a Comment