In this post, I explain a particular type of queues called the circular buffer. At the end I show an example implementation using Python.

Short description

A queue is a data structure that implements the FIFO (First-In-First-Out) principle. That means, the first element added (enqueue) to the queue is the first element that gets removed (dequeue). In other areas of life, this is often referred to as a first-come, first-served principle.

A circular (or ring) buffer is a specialized typed of a queue. It is assigned a length at initialization. This length if fixed and not changed during runtime. If the queue is full, it will start to overwrite its values in a circular movement.

Simplified schematic of a circular buffer

The image shows the schematic of a circular buffer. If a new element is enqueued, it will be inserted right to “40”, and the back_pointer will move one position right. If a value is inserted at the most right field the “back pointer” jumps to the left end of the queue. So the back_pointer is left to the front_pointer. If it is one less to the “front pointer” the buffer is full. To add a new element, one must first be removed.

Advantages

A circular buffer brings some advantages. The memory is allocated at the initialization and constant during runtime. Growing queues could be a problem if they grow faster than they shrink as they continuously allocate more memory. This problem does not exist for a circular buffer. They also do not need dynamic memory and don’t require to copy data around. This eliminates the problem of memory leaks. Another advantage is the simple and fast implementation.

Disadvantages

The fixed length could be a problem in some cases. The required length must be known beforehand and could not be changed if required.

Definitions and naming

Length: The length of the buffer is the number of elements that it could store.

Size: The size of the buffer is the number of elements that are currently stored in the buffer.

Empty: The buffer is empty if there is no element in it. This is indicated if the start_pointer and end pointer point to the same element.

Full: The buffer is full if each element is filled with a value. This indicated if the end_pointer is one less than the start_pointer.

UML Modelling

Use case diagram

The use case diagram shows the actions that the Circular buffer must provide. In the code, each action is implemented as a public function of the class.

Class diagram

The class diagram shows the required classes and their functions. Since the full buffer is implemented in a single class the diagram only contains one class. The public functions mirror the actions defined in the use case diagram.

To make the buffer definition as abstract as possible, the generic type “T” is used. This variable could be replaced by the required type (for example int, string, …). The “enqueue” function returns a Boolean value. If the value could be inserted, the function returns true. Otherwise, it will return false.

Implementation

The following code demonstrates an implementation of a Circular buffer in Python.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from typing import TypeVar, Optional, List


T = TypeVar("T")


class CircularBuffer(Generic[T]):
    data: List[T] = []

    length: int
    size: int = 0

    front_pointer: int = 0
    back_pointer: int = 0

    def __init__(self, length: int = 5):
        self.length = length

        self.data = [None] * length

    def enqueue(self, val: T) -> bool:
        if self.is_full():
            return False

        self.data[self.back_pointer] = val

        self.back_pointer = (self.back_pointer + 1) % self.length
        self.size += 1
        
        return True

    def dequeue(self) -> Optional[T]:
        if self.is_empty():
            return None

        val: T = self.data[self.front_pointer]

        self.front_pointer = (self.front_pointer + 1) % self.length
        self.size -= 1

        return val

    def is_empty(self) -> bool:
        if self.size == 0:
            return True

        return False

    def is_full(self) -> bool:
        if self.size == self.length:
            return True

        return False

    def get_size(self) -> int:
        return self.size

    def get_length(self) -> int:
        return self.length

In order to make the code not too long, the comments have been removed. For the full code see the Github repo.

The class uses a TypeVar so the concrete type must be provided at the initialization. For example to use the class with int types the a new buffer is created with the following code.

1
2
3
4
5
6
7
8
9
    cb = CircularBuffer[int](10)

    cb.enqueue(5)
    cb.enqueue(6)
    cb.enqueue(7)

    val = cb.dequeue()

    print(val)  # 5

To use another type replace int with the target type.

Conclusion

Circular buffers are handy structures. They provide a lot of advantages and can be easily implemented. Since they can be used in many different cases, every programmer should know them and should be able to implement them.