C++에서 원형 배열 구현
이 기사에서는 C++에서 순환 배열 데이터 구조를 구현하는 방법을 설명합니다.
C++에서 순환 버퍼 구현을 위한 사용자 배열 구현
순환 배열은 큐와 같은 데이터 컬렉션을 구현하는 데 일반적으로 사용되는 데이터 구조입니다. 순환 대기열 또는 링 버퍼와 같은 대체 이름으로도 알려져 있지만 이 기사 전체에서 순환 배열이라고 부를 것입니다.
원형 어레이에는 요소 삽입 및 제거 작업을 위한 FIFO(선입 선출) 메커니즘이 있습니다. 일반적으로 버퍼의 길이는 고정되어 있습니다. 최대 용량에 도달하면 버퍼가 새로운 삽입 작업을 거부하거나 가장 오래된 요소를 덮어쓰기 시작할 수 있습니다. 후자의 기능은 설계 선택이며 당면한 각 문제에 대한 이점을 고려해야 합니다.
다음 예제에서는 C 스타일 배열을 사용하여 원형 배열을 구현하고 전체 버퍼가 이전 데이터를 덮어쓰지 않도록 삽입 함수를 구성합니다.
CircularArray 클래스에는 5개의 데이터 멤버가 포함되어 있으며 그 중 3개는 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 멤버 함수를 호출해야 합니다. 이 함수는 일반 객체에 대한 참조를 가져와 버퍼의 tail에 저장합니다.
enqueue 함수는 삽입에 실패하면 0이 아닌 값을 반환하고 프로그래머는 해당 반환 값을 확인할 책임이 있습니다.
반면에 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
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