在 C++ 中實現迴圈陣列
本文將介紹如何用 C++ 實現一個迴圈陣列資料結構。
C++ 中迴圈緩衝區實現的使用者陣列實現
迴圈陣列是一種通常用於實現類似佇列的資料集合的資料結構。它也有其他名稱，例如迴圈佇列或環形緩衝區，但我們將在本文中將其稱為迴圈陣列。
迴圈陣列具有用於元素插入和刪除操作的 FIFO（先進先出）機制。通常，緩衝區將具有固定長度。如果達到最大容量，緩衝區可能會拒絕新的插入操作或開始覆蓋最舊的元素。後一個功能是一種設計選擇，應該針對手頭的各個問題考慮好處。
在下面的例子中，我們使用 C 風格的陣列實現了一個迴圈陣列，並構造了一個插入函式，這樣，完整的緩衝區就不會開始覆蓋舊資料。
CircularArray 類包括 5 個資料成員，其中三個具有 T* 型別，用於儲存第一個的地址。最後一個元素（分別是 head 和 tail）。arr 成員僅用於使用 delete 運算子使記憶體釋放更容易。其餘兩個資料成員是整數型別，用於儲存圓形陣列的容量和當前大小。
建構函式自動將 size 成員初始化為 0，而 cap 值被接受為函式引數，因此用於分配所需的記憶體區域。此時，tail 和 head 指標都指向同一個位置，即陣列中的第一個元素。但是請記住，這些指標可以在物件的生命週期內迴圈移動，因此我們需要在呼叫插入和刪除操作時控制正確的修改。
#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;
}
輸出：
1,1.1
1,1.2
1,1.3
1,1.4
為了將新元素新增到迴圈陣列 enqueue 成員函式應該被呼叫。此函式獲取對通用物件的引用並將其儲存在緩衝區的尾部。
如果插入不成功，enqueue 函式返回一個非零值，程式設計師負責檢查相應的返回值。
另一方面，dequeue 函式處理從緩衝區的 head 刪除元素的操作。它旨在返回指向已刪除元素的指標。在訪問它之前必須檢查返回指標（取消引用），因為它可能具有 nullptr 值。返回 nullptr 以指示緩衝區為空且無法刪除任何元素。
同時，可以使用 getSize 函式安全地訪問緩衝區中的當前元素數量，並使用返回值迭代結構。儘管迭代不太可能用於現實世界的場景，但 size 成員可能是實現其他成員功能的重要資料。
#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;
}
輸出：
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