Ring Buffer

Tags

comp-sci

Is a queue like data-structure that uses a single fixed-size buffer as if it were connected end to end. We maintain pointers both to the start and end of the buffer and move along the ring while inserting elements, wrapping back around at either end. We also maintain pointers to the effective start and end of the buffer (excluding elements that have been popped or deleted).

The ring buffer is a good FIFO data-structure. Element insertion and removal is a constant time operation since we just overwrite a value at the head of the buffer and then increment or decrement the start/end pointers.