# Implement Circular Array in C++

This article will describe how to implement a circular array data structure in C++.

## User Array Implementation for Circular Buffer Implementation in C++

A circular array is a data structure commonly utilized to implement a queue-like collection of data. It’s also known with alternative names such as a circular queue or ring buffer, but we will refer to it as a circular array throughout this article.

The circular array has FIFO (First In, First Out) mechanism for element insertion and removal operations. Usually, the buffer will have a fixed length. If the maximum capacity is reached, the buffer may refuse new insertion operations or start overwriting the oldest elements. The latter feature is a design choice, and benefits should be considered for the respective problem at hand.

In the following examples, we implement a circular array using a C-style array and construct an insertion function so that the full buffer will not start overwriting old data.

The `CircularArray`

class includes 5 data members, three of which have `T*`

type, and these are used to store the addresses for the first. The last elements (`head`

and `tail`

respectively). `arr`

member is only used to make memory deallocation easier using the `delete`

operator. The remaining two data members are integral types that store the capacity and the current size of the circular array.

The constructor automatically initializes the `size`

member to `0`

, while the `cap`

value is accepted as the function parameter and consequently used to allocate the required memory region. At this point, both `tail`

and `head`

pointers point to the same location, which is the first element in the array. Remember, though, these pointers can move circularly during the lifetime of the object, so we need to control the correct modifications when insertion and removal operations are called.

```
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
template<typename T>
class CircularArray {
public:
explicit CircularArray(const size_t elems) {
cap = elems;
arr = new T[elems];
tail = head = arr ;
size = 0;
};
int enqueue(const T &data);
T *dequeue();
size_t getSize();
~CircularArray();
private:
T *arr = nullptr;
T *head = nullptr;
T *tail = nullptr;
size_t cap;
size_t size;
};
template<typename T>
CircularArray<T>::~CircularArray() {
delete [] arr;
}
template<typename T>
int CircularArray<T>::enqueue(const T &data) {
if (size < cap) {
if (size == 0) {
head = tail = arr;
*tail = data;
size++;
return 0;
}
if (tail == &arr[cap]) {
tail = arr;
*tail = data;
size++;
} else {
tail = tail + 1;
*tail = data;
size++;
}
return 0;
} else {
return -1;
}
}
template<typename T>
T *CircularArray<T>::dequeue() {
if (size != 0) {
auto ret = head;
if (head == &arr[cap]) {
head = arr;
} else {
head = head + 1;
}
size--;
return ret;
} else {
cout << "Array is empty !" << endl;
return nullptr;
}
}
template<typename T>
size_t CircularArray<T>::getSize() {
return size;
}
struct MyClass {
int num;
double num2;
};
int main() {
CircularArray<MyClass> m1(4);
m1.enqueue({1, 1.1});
m1.enqueue({1, 1.2});
m1.enqueue({1, 1.3});
m1.enqueue({1, 1.4});
m1.enqueue({1, 1.5});
m1.enqueue({1, 1.6});
auto size = m1.getSize();
for (size_t i = 0; i < size; ++i) {
auto elem = m1.dequeue();
cout << elem->num << "," << elem->num2 << endl;
}
return EXIT_SUCCESS;
}
```

Output:

```
1,1.1
1,1.2
1,1.3
1,1.4
```

In order to add new elements into the circular array `enqueue`

member function should be called. This function takes a reference to the generic object and stores it at the `tail`

of the buffer.

The `enqueue`

function returns a non-zero value if the insertion is unsuccessful, and the programmer is responsible for checking the corresponding return value.

On the other hand, the `dequeue`

function handles the element removal operation from the `head`

of the buffer. It is designed to return the pointer to the removed element. One must check the return pointer before accessing it (dereferencing) as it may have the `nullptr`

value. `nullptr`

is returned to indicate the buffer is empty and no elements can be removed.

Meanwhile, one can safely access the current number of elements in the buffer using the `getSize`

function and use the returned value to iterate over the structure. Although the iteration is not likely to be used in real-world scenarios, the `size`

member can be important data for implementing additional member functions.

```
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
template<typename T>
class CircularArray {
public:
explicit CircularArray(const size_t elems) {
cap = elems;
arr = new T[elems];
tail = head = arr ;
size = 0;
};
int enqueue(const T &data);
T *dequeue();
size_t getSize();
~CircularArray();
private:
T *arr = nullptr;
T *head = nullptr;
T *tail = nullptr;
size_t cap;
size_t size;
};
template<typename T>
CircularArray<T>::~CircularArray() {
delete [] arr;
}
template<typename T>
int CircularArray<T>::enqueue(const T &data) {
if (size < cap) {
if (size == 0) {
head = tail = arr;
*tail = data;
size++;
return 0;
}
if (tail == &arr[cap]) {
tail = arr;
*tail = data;
size++;
} else {
tail = tail + 1;
*tail = data;
size++;
}
return 0;
} else {
return -1;
}
}
template<typename T>
T *CircularArray<T>::dequeue() {
if (size != 0) {
auto ret = head;
if (head == &arr[cap]) {
head = arr;
} else {
head = head + 1;
}
size--;
return ret;
} else {
cout << "Array is empty !" << endl;
return nullptr;
}
}
template<typename T>
size_t CircularArray<T>::getSize() {
return size;
}
struct MyClass {
int num;
double num2;
};
int main() {
CircularArray<MyClass> m1(4);
m1.dequeue();
m1.enqueue({1, 1.9});
auto elem = m1.dequeue();
if (elem)
cout << elem->num << "," << elem->num2 << endl;
return EXIT_SUCCESS;
}
```

Output:

```
Array is empty !
1,1.9
```