구글링으로 원형큐 구현을 보면 이상하게 원형큐의 사이즈가 정해져있고, 꽉차면 원형큐의 크기가 커지지않고 채울수 없는 구현만 봤다. 내가 못본걸수도 있지만,,,
이건 너무 이상해서 언제든 크기조절이 가능한 큐를 구현해보았다.
기존 원형큐의 단점은 위에 설명했듯이 큐에 데이터가 꽉차면 더이상 값을 넣을 수 없고, 그렇다고 큐의 사이즈를 키울 수도 없고, 빈공간을 효율적으로 관리하지만, 큐의 사이즈를 초기값설정후 다시 늘릴 수 없는 것이다.
분명 개발중 큐의 크기를 추정하기 애매할 때가 있을 거라 생각하고 원형큐의 장점인 빈 공간활용을 살리되, 언제든 벡터(vector)처럼 큐의 크기를 늘릴수 있는 기능을 추가하고 싶었다.
void Reserve(size_t capacity) override
{
//기존 캐퍼시티가 더 크다면 재할당을 하지 않습니다
if (this->my_capacity >= capacity)
return;
Data* temp = new Data[capacity];
//Debug
for (size_t i = 0; i < capacity; ++i)
{
temp[i] = NULL;
}
//0번째 인덱스부터 rear까지 새로 할당한 배열에 복사합니다
for (size_t i = 0; i < _rear; ++i)
{
temp[i] = this->my_base[i];
}
//컨테이너에 원소가 있다면 새로 할당한 주소로 옮겨줍니다
if (this->my_capacity > 0 &&
this->my_size > 0 &&
_rear <= _front)
{
//front부터 마지막인덱스까지 새로 할당한 배열에 복사합니다
for (size_t i = 0; i < this->my_capacity - _front; ++i)
{
temp[capacity - i - 1] = this->my_base[this->my_capacity - i - 1];
}
_front += capacity - this->my_capacity;
delete[] this->my_base;
}
this->my_capacity = capacity;
this->my_base = temp;
}
//마지막 위치에 원소를 추가합니다
//Enqueue()
void PushBack(const Data& data)
{
//rear의 위치가 배열의 최대 크기를 넘었는지 확인
if (_rear >= this->my_capacity)
{
_rear = 0;
}
//컨테이너에 비어있는 자리가 있는지 확인
//rear와 front가 동일한 인덱스를 가리키면 큐가 꽉찼거나 비어있음을 의미합니다
if (_rear == _front)
{
//큐가 꽉찼으면 재할당합니다
if (this->my_size > 0)
{
this->Reserve(this->my_capacity + this->additive_capacity);
}
}
//추가합니다
this->my_base[_rear++] = data;
++this->my_size;
}
//가장 처음으로 들어온 원소를 반환합니다
//디버깅을 위해 bool로 반환의 실패여부를 체크합니다
//Dequeue
const bool PopFront(Data& out_data)
{
//rear와 front가 동일한 인덱스를 가리키면 큐가 꽉찼거나 비어있음을 의미합니다
if (_rear == _front)
{
//큐가 비어있으면 Pop을 하지 않습니다
if (this->my_size <= 0)
{
return false;
}
}
if (_front >= this->my_capacity)
{
_front = 0;
}
--this->my_size;
//return this->my_base[_front++];
//Debug
Data& data = this->my_base[_front++];
Data data_new = data;
out_data = data_new;
data = NULL;
return true;
}PushBack()을 보면 데이터가 꽉 찰때Reserve()함수를 사용하는데 이것말고는 기존 원형큐과 똑같고 PopFront()도 변경점은 없다.
자세히 봐야할것은 Reserve()함수인데 이 함수는 이전에 벡터(vector)구현할 때 소개했던것과 동일하지만, 기존 데이터를 재할당한 배열에 추가하는 방법이 조금 달라졌다.
데이터가 앞쪽에 그대로 있다면 이런식으로 재할당한 배열에 추가된다
벡터와 동일하게 데이터가 추가되지만
만약 뒷 공간이 꽉차서 앞 공간까지 넘어오게 되었을때는 이런식으로 동작한다
이건 벡터와 동일하다.
rear가 뒷공간을 넘어서 앞으로 넘어오게된 상황에서 어떻게 재할당이 이뤄지는것이 핵심이다
rear와 front사이의 공간을 확보한다.
이말은 추가데이터의 위치를 가리키는 rear의 뒷부분을 확보한다고 봐도 된다
그러기 위해 front를 기준으로 뒷부분의 데이터를 옮긴다.
데이터가 꽉차서 자동으로 재할당이 될 경우는 이렇게 된다.
rear와 front가 겹치고, 데이터가 있다는 뜻은 꽉찼다는 뜻이므로 rear와 front가 겹쳐있을 때 재할당이 이루어진다.
front위치 이후의 3개의 데이터가 계속 뒤로 밀리고 있으며 rear위치뒤에 빈공간을 계속 생성하는게 보일것이다.
벡터와 마찬가지로 크기재할당은 가급적 피하는것이 좋다.
https://github.com/ForestBird1/MyContainer
GitHub - ForestBird1/MyContainer
Contribute to ForestBird1/MyContainer development by creating an account on GitHub.
github.com
'C++ 자료구조' 카테고리의 다른 글
| [C++] 나만의 DoubleLinkedList(이중연결리스트)만들기 (2) - 생성자, 데이터추가 (0) | 2023.08.29 |
|---|---|
| [C++] 나만의 DoubleLinkedList(이중연결리스트)만들기 (1) - 기초 (0) | 2023.08.28 |
| [C++] 나만의 Queue만들기 (3) - 원형 큐 구현 (0) | 2023.08.27 |
| [C++] 나만의 Queue만들기 (2) - 원형 큐, 기초 (0) | 2023.08.27 |
| [C++] 나만의 Queue만들기 (1) - 동적 배열을 이용해서 구현 (0) | 2023.08.27 |
