[C++] 나만의 Queue만들기 (3) - 원형 큐 구현

원형큐의 구현은 어렵지 않다.

Enqueue하는데 뒷 공간이 없다면 앞으로 오면되고,,,

Dequeue또한 마찬가지이고...

 

그래서 딱 하나만 추가하면 된다

큐가 꽉찼거나 비어있음을 판단

이것만 구현한다면 원형큐도 이젠 쉽다!

 

	MyQueue_FixedCircle(size_t i_init_size)
	{
		//my_base가 nullptr지만
		//사이즈및 캐퍼시티가 0이므로 원소를 추가할때 Reserve()함수에서 할당이 이뤄집니다
		this->my_size = 0;
		this->my_capacity = i_init_size;

		Data* temp = new Data[this->my_capacity];

		this->my_base = temp;

		//Debug
		for (size_t i = 0; i < this->my_capacity; ++i)
			this->my_base[i] = NULL;
	}
    //마지막 위치에 원소를 추가합니다
	//Enqueue()
	const bool PushBack(const Data& data)
	{
		//rear의 위치가 배열의 최대 크기를 넘었는지 확인
		if (_rear >= this->my_capacity)
		{
			_rear = 0;
		}

		//컨테이너에 비어있는 자리가 있는지 확인
		//rear와 front가 동일한 인덱스를 가리키면 큐가 꽉찼거나 비어있음을 의미합니다
		if (_rear == _front)
		{
			//큐가 꽉찼으면 데이터를 채울 수 없습니다
			if (this->my_size > 0)
			{
				return false;
			}
		}

		//추가합니다
		this->my_base[_rear++] = data;
		++this->my_size;
		return true;
	}

	//가장 처음으로 들어온 원소를 반환합니다
	//디버깅을 위해 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;
	}

다른 원형큐 구현을 보면 %연산자를 쓰고, isEmpty() isFull()등의 함수를 추가로 구현하던데 나는 그렇게 하지않고 최대한 직관적으로 구현했다.

EnQ나 DeQ를 하면 rear, front를 ++해주고 최대 사이즈를 넘어가면 0으로 돌아가게 하고,

내 원형큐는 데이터의 개수를 카운팅하고 있어서 rear==front라면 데이터개수를 판단해 큐가 비었는지 꽉찼는지 알 수 있다.

 

생성자를 보면 원형큐의 크기를 '무조건' 설정해줘야한다. 중간에 늘리거나 줄일 수 없다.

다른 원형큐 구현을 보면 const size_t QUEUE_SIZE = 1000; 뭐 이런식으로 하드코딩 해놓기도 하는데 똑같으면 재미없으니까 사용자가 원하는대로 크기를 조절할 수 있게 해놓았다

 

생성자 코드의 자세한 내용은 여기서 Reserve()구현부를 보면 확인할 수 있다.

https://forestbird0.tistory.com/38

[C++] 나만의 Vector만들기 (2) - 생성자, 소멸자, 캐퍼시티, Reserve

 

다음 포스팅은 여기서 더 발전된 '동적 원형 큐'인데 대단한건 아니고 사이즈를 언제든 늘릴 수 있게 구현한 원형큐다.

 

 

https://github.com/ForestBird1/MyContainer

GitHub - ForestBird1/MyContainer