How to 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::cin;
using std::cout;
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::cin;
using std::cout;
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
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook