在 C++ 中实现循环数组
本文将介绍如何用 C++ 实现一个循环数组数据结构。
C++ 中循环缓冲区实现的用户数组实现
循环数组是一种通常用于实现类似队列的数据集合的数据结构。它也有其他名称，例如循环队列或环形缓冲区，但我们将在本文中将其称为循环数组。
循环数组具有用于元素插入和删除操作的 FIFO（先进先出）机制。通常，缓冲区将具有固定长度。如果达到最大容量，缓冲区可能会拒绝新的插入操作或开始覆盖最旧的元素。后一个功能是一种设计选择，应该针对手头的各个问题考虑好处。
在下面的例子中，我们使用 C 风格的数组实现了一个循环数组，并构造了一个插入函数，这样，完整的缓冲区就不会开始覆盖旧数据。
CircularArray 类包括 5 个数据成员，其中三个具有 T* 类型，用于存储第一个的地址。最后一个元素（分别是 head 和 tail）。arr 成员仅用于使用 delete 运算符使内存释放更容易。其余两个数据成员是整数类型，用于存储圆形数组的容量和当前大小。
构造函数自动将 size 成员初始化为 0，而 cap 值被接受为函数参数，因此用于分配所需的内存区域。此时，tail 和 head 指针都指向同一个位置，即数组中的第一个元素。但是请记住，这些指针可以在对象的生命周期内循环移动，因此我们需要在调用插入和删除操作时控制正确的修改。
#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;
}
输出：
1,1.1
1,1.2
1,1.3
1,1.4
为了将新元素添加到循环数组 enqueue 成员函数应该被调用。此函数获取对通用对象的引用并将其存储在缓冲区的尾部。
如果插入不成功，enqueue 函数返回一个非零值，程序员负责检查相应的返回值。
另一方面，dequeue 函数处理从缓冲区的 head 删除元素的操作。它旨在返回指向已删除元素的指针。在访问它之前必须检查返回指针（取消引用），因为它可能具有 nullptr 值。返回 nullptr 以指示缓冲区为空且无法删除任何元素。
同时，可以使用 getSize 函数安全地访问缓冲区中的当前元素数量，并使用返回值迭代结构。尽管迭代不太可能用于现实世界的场景，但 size 成员可能是实现其他成员功能的重要数据。
#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;
}
输出：
Array is empty !
1,1.9
