[C++] 나만의 Queue만들기 (1) - 동적 배열을 이용해서 구현

동적 배열로 구현하면 큐의 단점을 명확하게 볼 수 있다.

구현은 쉽지만, 직접 구현해보면서 어떤 문제가 있는지 보자

이렇게 데이터를 추가하면 차곡차곡 쌓이는데 데이터를 꺼내면 앞 공간이 비게 되고 이 빈 공간은 낭비가 된다.

이걸 방지하기 위해 이런 방법도 있는데...

데이터를 꺼낼 때 마다 나머지 데이터를 한칸씩 앞으로 옮기는 방법이 있다.

하지만 딱 봐도 성능에 좋아 보이지 않는데, 데이터가 수천 수만개라면 이런 방법은 사용하기가 어렵다.

 

구현은 어렵지 않으니 일단 구현해보고, 다음 포스팅엔 이런 문제를 개선한 '원형 큐'를 소개하겠다

 

---

template <typename Data>
class Container_Master
{
protected:
	Data* my_base = nullptr;
	size_t my_capacity = 0;
	size_t my_size = 0;

	//캐퍼시티를 늘릴 때 지정된 값이 없다면 해당 값만큼 늘립니다
	const size_t additive_capacity = 4;
public:
	//컨테이너의 원소개수입니다
	size_t Num()
	{
		return my_size;
	}

	//컨테이너의 캐퍼시티개수입니다
	size_t Max()
	{
		return my_capacity;
	}
};

#pragma once
#include "Container_Master.h"

/*
* 동적 배열 큐 입니다.
*
* 디버깅을 위해 원소를 Pop하게 되면 그 자리를 NULL로 채웁니다
*/

template <typename Data>
class MyQueue_DynamicArray : public Container_Master<Data>
{

public:
	//마지막 위치에 원소를 추가합니다
	//Enqueue()
	void PushBack(const Data& data)
	{
		//rear의 위치가 배열의 최대 크기를 넘었는지 확인
		if (_rear >= this->my_capacity)
		{
			this->Reserve(this->my_capacity + this->additive_capacity);
		}

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

	//가장 처음으로 들어온 원소를 반환합니다
	//디버깅을 위해 bool로 반환의 실패여부를 체크합니다
	//Dequeue
	const bool PopFront(Data& out_data)
	{
		//큐가 비어있으면 Pop을 하지 않습니다
		if (this->my_size <= 0)
		{
			return false;
		}

		--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;
	}

	//앞쪽에 비어있는 배열자리에 기존 원소들로 채웁니다.
	//재할당하는 방법이 있지만, 여기선 빈 공간을 NULL(0)로 표현했습니다
	void SortQueue()
	{
		//원소를 앞으로 이동시킵니다
		size_t i = 0;
		for (i = _front; i < _rear; ++i)
		{
			this->my_base[i - _front] = this->my_base[i];			
		}

		//이동된 원소를 NULL로 채웁니다
		for (i -= _front; i < _rear; ++i)
		{
			std::cout << std::to_string(i) << std::endl;
			this->my_base[i] = NULL;
		}

		_rear -= _front;
		_front = 0;
	}
private:
	//데이터를 꺼낼 공간을 가리키고 있습니다. 데이터가 없을 수도 있습니다.
	size_t _front = 0;
	//데이터를 넣을 빈 공간을 가리키고 있습니다
	size_t _rear = 0;
};

코드가 좀 긴데 일부러 풀어쓰기도 했고, 디버깅으로 코드가 좀 더 길어졌다.

디버깅용으로 큐의 빈 공간은 0(NULL)으로 채웠으니 그점만 유의하면 된다.

 

핵심코드

1. PushBack()(Enqueue)

2. PopFront()(Dequeue)

3. SortQueue() (함수명을 어떻게 작성할지 몰라서 걍 Sort키워드를 썼다...)

굳이 함수명을 Enqueue, Dequeue를 쓰지 않은 이유는 그냥 직관적으로 함수이름만 보고 어떤역할을 하는지 알 수 있게 작성했다.

 

PushBack()은 크게 설명할게 없으니 넘어가고

PopFront()를 보면 데이터를 복사하고 NULL로 바꾸고 반환하고 번거로운 코드가 있는데 디버깅 코드이니 실제 코드는

위에 주석처리한 return base[_front++]; 이것을 보면 된다.

 

SortQueue()는 앞의 빈공간을 채우는 함수이다.

조금 다른점은 PopFront()할 때마다 한칸씩 옮기는 게 아니라 필요할 때 앞의 빈공간으로 이동시키게 한다.

큐를 써야하는데 자주쓰는것은 아니고 원형 큐까지 구현할 필요가 없다면

동적배열로 대충 만들고 빈공간이 5개일때, 10개일때 등 필요한 시점에서 SortQueue()로 빈 공간을 채우면 된다.

 

https://github.com/ForestBird1/MyContainer

GitHub - ForestBird1/MyContainer