Implementar Matriz Circular em C++
Este artigo descreve como implementar uma estrutura de dados de array circular em C++.
Implementação de array de usuário para implementação de buffer circular em C++
um array circular é uma estrutura de dados comumente utilizada para implementar uma coleção de dados semelhante a uma fila. Ele também é conhecido por nomes alternativos, como fila circular ou buffer de anel, mas iremos nos referir a ele como um array circular ao longo deste artigo.
A matriz circular possui mecanismo FIFO (First In, First Out) para as operações de inserção e remoção de elementos. Normalmente, o buffer terá um comprimento fixo. Se a capacidade máxima for atingida, o buffer pode recusar novas operações de inserção ou começar a sobrescrever os elementos mais antigos. O último recurso é uma escolha de design e os benefícios devem ser considerados para o respectivo problema em questão.
Nos exemplos a seguir, implementamos um array circular usando um array de estilo C e construímos uma função de inserção para que o buffer completo não comece a sobrescrever dados antigos.
A classe CircularArray inclui 5 membros de dados, três dos quais têm o tipo T* e são usados para armazenar os endereços do primeiro. Os últimos elementos (head e tail respectivamente). O membro arr é usado apenas para tornar a desalocação de memória mais fácil usando o operador delete. Os dois membros de dados restantes são tipos integrais que armazenam a capacidade e o tamanho atual do array circular.
O construtor inicializa automaticamente o membro size como 0, enquanto o valor cap é aceito como o parâmetro da função e, conseqüentemente, usado para alocar a região de memória necessária. Nesse ponto, os ponteiros tail e head apontam para o mesmo local, que é o primeiro elemento na matriz. Lembre-se, porém, de que esses ponteiros podem se mover circularmente durante a vida útil do objeto, portanto, precisamos controlar as modificações corretas quando as operações de inserção e remoção são chamadas.
#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;
}
Produção:
1,1.1
1,1.2
1,1.3
1,1.4
Para adicionar novos elementos na matriz circular, a função de membro enqueue deve ser chamada. Esta função pega uma referência ao objeto genérico e armazena-o no tail do buffer.
A função enqueue retorna um valor diferente de zero se a inserção não for bem-sucedida, e o programador é responsável por verificar o valor de retorno correspondente.
Por outro lado, a função dequeue trata da operação de remoção do elemento da head do buffer. Ele é projetado para retornar o ponteiro ao elemento removido. Deve-se verificar o ponteiro de retorno antes de acessá-lo (desreferenciamento), pois ele pode ter o valor nullptr. nullptr é retornado para indicar que o buffer está vazio e nenhum elemento pode ser removido.
Enquanto isso, pode-se acessar com segurança o número atual de elementos no buffer usando a função getSize e usar o valor retornado para iterar sobre a estrutura. Embora a iteração provavelmente não seja usada em cenários do mundo real, o membro size pode ser um dado importante para a implementação de funções de membro adicionais.
#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;
}
Produção:
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