0

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 :)

3
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by tesuji
0

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).

0

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.