Search code examples
data-structuresqueuefifoabstract-data-type

Where should rear point in queue data structure

Where should rear point in a queue:

  1. Place where new element WILL BE inserted.
  2. Place where last element of the queue resides.

According to my research, I got both above cases as answers.

Solution

  • I'd say go with the TailPointer pointing towards the last element that was added instead of the empty slot where you'd add the new element. I have a few reasons for that:

    • To get the last element you can directly get the value at TailPointer which is more like the name. Instead of going with a TailPointer - 1.

    • In case you have an Array as a backing DataStore for your Queue, it'll be natural to check tailPointer == dataStore.Length - 1 (since 0 based indexing is most common)

    • Also you would be wrapping your data to initial indexes (the one's before the Head Pointer) in case you DeQueue your data. (refer this and this)

    • If no data is in the Queue, you can simply set the TailPointer to -1.