Implementing a Queue with a Circular Buffer in an Array

[surk23]

I kind of understand the basic concept of adding to the end / overwriting the oldest when the buffer is full, but i am not sure about where to add new data in the buffer when there is free space at the start of the array (the left hand side) but it is already occupied by data at the end (the last few elements).

For example... i have an array called 'queue' with 10 elements: queue[0,1,2,3,4,5,6,7,8,9]
It currently has 4 items in it, which occupy elements [6][7][8][9], [6] holds the oldest item and [9] holds the newest item.

When i want to add 2 items to the queue, am i shifting the 4 existing items down 2 elements to make room at the end ? (like this--)

0 1 2 3 4 5 6 7 8 9
[ ][ ][ ][ ][*][*][*][*][ ][ ] (putting the two new items in [8] and [9] )

Or do i leave the 4 existing items where they were and put the two new items in elements [0] and [1] ?

Would be a big help if someone can help :)

[Momerath]

Create 2 'pointers', one to the start of the queue, one to where the next one will go. When you add an item, check to make sure the start and end aren't the same (if they are, then your queue is full. How you want to handle that is your choice). If they aren't the same, store the new value at the 'next' pointer and increment it modulus the size of your array. When you get a value from the queue, get it from the 'start' pointer and increment it modulus the size of your array.

The only issue left is how to deal with an empty array (start=end, but the array isn't full). I'd use a boolean to indicate you have values, and change it in the fetch section when you increment the 'start' pointer (check if = to 'next' and if so set 'is empty' = true. When you add something, set it to false).

[tesuji]

Hi

>>> Or do i leave the 4 existing items where they were and put the two new items in elements [0] and [1] ?

Yes, for it is a circular buffer, and as Momerath already stated "store the new value at the 'next' pointer and increment it modulus the size of your array".

Here is a good explanation on how a circular buffer functions.

-- tesu