ForestBird

	//가장 앞, 뒤의 데이터를 삭제합니다
	const bool RemoveFront()
	{
		return Remove(head->next);
	}
	const bool RemoveBack()
	{
		return Remove(tail->prev);
	}

    private:
	//데이터를 찾아서 삭제합니다
	const bool Remove(Node* nd_remove)
	{
		if (size <= 0) return false;

		nd_remove->prev->next = nd_remove->next;
		nd_remove->next->prev = nd_remove->prev;
		delete nd_remove;
		--size;
		return true;
	}

이전 포스팅에서 소개한 AddFront(),AddBack(),Add()와 동일한 구조의 함수다

Remove()는 성공과 실패를 리턴하고, 노드를 삭제하며 삭제된 노드 앞뒤의 노드끼리 연결시킨다

	//원하는 데이터를 찾아서 삭제합니다
	const bool RemoveData(const Data& data)
	{
		if (size <= 0) return false;

		for (Node* nd = head->next; nd != tail; nd = nd->next)
		{
			if (nd->data == data)
			{
				//삭제할 데이터를 찾았습니다. 삭제합니다
				return Remove(nd);
			}
		}

		//삭제할 데이터를 찾지 못했습니다
		return false;
	}

	//모든 데이터를 삭제합니다
	void RemoveAll()
	{
		while (RemoveFront()) {}
	}

RemoveData(): 동일한 데이터를 찾아 삭제.

RemoveAll(): 모든 데이터를 삭제.

RemoveData()에서 노드의 순회을 볼 수 있다.

head->next노드부터 시작해서 tail이 아닌 노드면 계속 순회한다.

역순회도 다르지 않다.

for (Node* nd = tail->prev; nd != head; nd = nd->prev)

논리적으로 거꾸로 돌아가게 하면된다.

프로그래밍 처음 공부했을때 꽤 어려웠던 연결리스트였는데 지금 다시 보니까 구현자체는 어렵지 않았다.

데이터의 삽입,삭제시 노드연결만 신경써주면된다.

https://github.com/ForestBird1/MyContainer

연결리스트는 여러개의 노드로 구성되어 있기 때문에 노드 구조체를 먼저 만들어보자

	//template <typename Data>
    struct Node
	{
		Data data = NULL;
		Node* next = nullptr;
		Node* prev = nullptr;
	};

노드는 대단한건 없고, 데이터를 저장하기위한 변수와, 앞 뒤 노드를 가리키는 변수2개가 필요하다.

처음 프로그래밍을 공부할 때 이해가 어려웠던 부분이

Node구조체안에 왜 똑같은 노드가 2개가있지? 그리고 왜 포인터지?

노드는 노드를 가리켜야 하니까 저렇게 한건 알겠는데 논리적으로 이해를 못하니까 두루뭉술하게 이해했고,

왜 포인터로 저장하는지도 이해를 못했다.

노드 구조체안에 노드변수를 가져야하는것은 구현하면 알게되니 넘어가고

포인터로 저장하는 이유는 노드를 '복사'해서 가지지 않으려고 그런것이다.

call by value, call by address, call by reference라는 개념이 있는데 

여기서 이것까지 설명하면 길어지기 때문에 이 부분은 넘어가고 여기선 일단

노드구조체안의 노드변수는 앞 뒤 노드의 정보를 원본으로 가지고 있어야하기 때문이라고 이해하자

	MyLinkedList()
	{
		head = new Node;
		tail = new Node;

		head->next = tail;
		tail->prev = head;
	}
	~MyLinkedList()
	{
		//모든 노드 삭제
		RemoveAll();

		delete head;
		delete tail;
	}

	Node* head = nullptr;
	Node* tail = nullptr;
	size_t size = 0;

생성자에선 헤드와 테일을 미리 생성하고 서로 연결시켜 놓습니다.

소멸자에선 모든 데이터를 제거및해제 하고, 헤드와 테일도 해제합니다. 항상 포인터같은 할당된 변수는 꼭 해제를 해야합니다.

RemoveAll()은 다음 포스팅에서 나옵니다

내가 구현한 이중연결리스트는 헤드와 테일에 데이터가 없습니다

	//데이터를 추가합니다
	void AddFront(const Data& data)
	{
		Add(head->next, data);
	}
	void AddBack(const Data& data)
	{
		Add(tail, data);
	}
    
    private:
	void Add(Node* nd_next, const Data& data)
	{
		//노드를 새로생성합니다
		Node* nd = new Node;
		nd->data = data;

		//생성한 노드의 앞, 뒤 노드를 연결합니다.
		nd->next = nd_next;
		nd->prev = nd_next->prev;

		//앞, 뒤 노드도 생성한 노드에 연결합니다
		nd_next->prev->next = nd;
		nd_next->prev = nd;

		++size;
	}

AddFront(), AddBack()은 앞 혹은 뒤에 데이터를 추가하겠는 함수고 실제 로직은 Add()에 들어있다.

Add()를 보면 생성된 노드와 앞,뒤의 노드를 연결하는 부분이 헷갈릴수 있다.

하지만 하나씩 하나씩 나눠서 보면 이해가 될것이다.

그래도 이해가 안되면 직접 그려보자.

https://github.com/ForestBird1/MyContainer

연결리스트는 데이터끼리 순서대로 연결된 형식이다.

벡터(vector)의 경우 메모리의 인접한 순서대로 데이터가 존재하지만,

연결리스트는 각 데이터가 메모리에서 인접하지 않더라도 데이터는 다음 데이터의 위치를 저장하고 있다.

벡터는 데이터를 중간위치에서 삽입,삭제시 데이터가 밀리거나, 땡겨지게 되는 이슈가 있는데,

연결리스트는 메모리가 인접하지 않아도 되기 때문에 삽입,삭제에서 자유롭다.

단점은 벡터는 인덱스로 데이터에 빠르게 접근할 수 있지만, 연결리스트는 꼭! 순차적으로 검색후 데이터에 접근하게 된다. 그래서 검색의 최후방에 있는 데이터는 가장늦게 찾게 된다.

벡터는 중간위치에 삽입,삭제 하려면 인덱스를 알아야 하지만,

연결리스트는 앞 혹은 뒤의 노드를 알아야한다.

여기선 어떻게 데이터끼리 위치를 저장하고있는지 알아봐야한다

1. 단일연결리스트

데이터는 다음데이터의 위치를 저장한다

각 네모아이콘은 데이터를 입력할 수 있는 노드(Node)를 의미하고, 그중 가장 앞에있는 노드를 Head 또는 Header라고 한다.

나는 헤드(Head)에 데이터를 넣지않고 빈 공간으로 표현했지만, 구현에 따라서 헤드에도 데이터를 넣어도 된다. 어차피 헤드도 노드의 종류여서 문제없다.

화살표를 보면 각 노드는 다음 노드를 가리키고 있고, 마지막 노드는 다음 노드가 없기 때문에 아무것도 가리키지 않는다.

단일연결리스트의 이름에서 볼 수 있듯이 한쪽방향으로만 데이터가 연결되어 있다 

3번 노드의 데이터를 가져오려면 헤드 혹은 1번 노드부터 순차적으로 검색한다.

1번 노드야 너 3번이니? 아니

2번 노드야 너 3번이니? 아니

3번 노드야 너 3번이니? 응 

...

마지막 위치에 데이터를 추가하려면 마지막 노드를 찾아야하는 긴 여정이 필요하다.

그렇기 때문에 맨 앞에 데이터를 추가하는것이 여러모로 이롭다.

이미지가 선형적으로 되어 있어 마치 메모리에서도 인접해 보이고 정렬된 느낌이지만 이렇게 표현할 수도 있다

노드의 위치는 신경쓰지 않아도 된다.

그저 노드와 노드끼리의 연결만 신경쓰자.

2번 노드를 삭제해보자

벡터와 다르게 중간의 데이터를 삭제해도 각 데이터(노드)의 위치는 변하지 않는다

다만 2번 노드를 가리킨 1번 노드는 이제 2번이 아니라 2번의 다음 노드인 3번 노드를 가리키게 된다.

어렵지 않다. 그냥 가리키는것만 신경쓰자!!

2. 원형연결리스트

마지막 노드는 다시 첫 데이터(노드)를 가리킨다

단일연결리스트는 빈 헤드가 없는것이 기본적이다.

단일연결리스트에서 딱 하나 추가된 기능이 있는데

마지막노드가 빈 공간을 가리키지않고 첫 데이터를 가리킨다.

나는 원형연결리스트를 써본적이 없어서 그런지... 단일연결리스트보다 좋은 점을 잘 모르겠다.

굳이 따지면 마지막 노드가 nullptr을 가리키지않아 크래쉬가 날 확률이 적어지지만,

무한루프에 빠질수도 있는 단점도 가지고 있다

3. 이중연결리스트

모든 노드가 앞뒤로 연결되어 있어 역순환을 할 수 있다.

헤드와 동일한 개념의 테일(Tail)노드가 새로 생긴다.

단일, 원형연결리스트의 단점인 마지막노드검색이 훨씬 수월해진다.

단점은 이전 노드를 기억해야하는 변수를 만들고, 테일노드까지 생성해야해서 메모리를 좀 더 쓰게되지만, 

단점에 비해 장점이 크다.

나는 이중연결리스트만 구현했고 단일,원형연결리스트는 따로 구현하지 않았기 때문에

이중연결리스트만 소개하겠다.

https://github.com/ForestBird1/MyContainer

구글링으로 원형큐 구현을 보면 이상하게 원형큐의 사이즈가 정해져있고, 꽉차면 원형큐의 크기가 커지지않고 채울수 없는 구현만 봤다. 내가 못본걸수도 있지만,,,

이건 너무 이상해서 언제든 크기조절이 가능한 큐를 구현해보았다.

기존 원형큐의 단점은 위에 설명했듯이 큐에 데이터가 꽉차면 더이상 값을 넣을 수 없고, 그렇다고 큐의 사이즈를 키울 수도 없고, 빈공간을 효율적으로 관리하지만, 큐의 사이즈를 초기값설정후 다시 늘릴 수 없는 것이다.

분명 개발중 큐의 크기를 추정하기 애매할 때가 있을 거라 생각하고 원형큐의 장점인 빈 공간활용을 살리되, 언제든 벡터(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

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

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

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

https://github.com/ForestBird1/MyContainer

이전 포스팅에서 구현했던 '동적 배열 큐'(선형큐)의 단점을 보완한 '원형 큐'.

원형큐는 선형큐의 단점인 '빈 공간 낭비'를 해결해서, 비교적 효율적으로 빈 공간을 관리한다.

원형큐를 간단하게 설명하면 데이터를 추가할 때 뒷 공간이 꽉차면 다시 비어있는 앞공간을 메꾸는 원리이다.

선형큐처럼 front와 rear변수로 데이터의 입출력위치를 관리한다

front: Dequeue()호출 시 꺼낼 데이터의 위치를 가리킴.(큐에 데이터가 없다면 빈 공간을 가리킴.)

rear: Enqueue()호출 시 데이터를 추가할 빈 공간을 가리킴.(큐에 데이터가 꽉차면 빈 공간이 아니라 데이터를 가리킴)

나는 front는 꺼내야할 데이터의 위치를, rear는 데이터가 추가될 빈공간의 위치를 가리키게 했는데,

구현하는 사람에 따라서 다르게 작성할 수도있다. 

여기서 데이터를 En,Dequeue하게 되면...

rear는 항상 빈 공간을 가리켜야하고, front는 항상 데이터를 가리켜야한다.

rear가 데이터를, front가 빈공간을 가리키는것은 큐에 데이터가 꽉차있거나 비었다는 뜻이다.

여기서 데이터를 3개이상 추가한다고 했을 때, 선형큐같은 경우 큐의 크기가 커져야 한다.

원형큐라면?

숫자 7데이터가 큐의 처음 위치로 오게 되었다.

이 모양을 선형으로 표현하면 아래의 모습으로 나온다

여기서 데이터를 하나 더 추가하면?

이런 모습이 되고 front와 rear가 같은곳을 가리키고 있다.

이렇게 front와 rear가 같은곳을 가리킨다면 큐가 비어있거나, 꽉찼다는 의미이다

꽉 차게 되면 Enqueue를 할 수 없다.

https://github.com/ForestBird1/MyContainer

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

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

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

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

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

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

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

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

큐(Queue)는 FIFO(First-In First-Out)형식으로 먼저들어온 데이터가 먼저 빠져나가게 된다.

스택을 구현해봤다면 큐도 쉽게 만들 수 있다.

하지만 이런식으로 구현하면 Dequeue를 할 때마다 앞공간이 비워지게 되고 데이터는 계속 쌓이게 된다.

시간이 지나면 데이터는 1개밖에 없는데 큐의 크기는 훨씬 커져 있어서 빈 공간을 낭비하고 있게 된다.

빈 공간을 채울려면 Pop할 때마다 모든 데이터를 앞 쪽으로 한칸씩 옮겨야 하는데 데이터가 무수히 많다면 성능에 좋지 않을것이다.

그래서 나온 것이 원형 큐(circular queue)이다.

간단하게 설명하면 원형 큐에 데이터를 넣을 때 뒷공간에 빈자리가 없다면, 앞 공간의 빈자리에 데이터를 채워넣게 되서 빈 공간을 낭비없이 사용하게 된다.

여기서 내가 추가로 구현한 것은 '동적 원형 큐'이다.

원형 큐를 구글링해보니까 대부분 fixed array를 사용하던데, fixed array를 사용하면 원형큐의 모든 공간이 꽉차면 데이터를 추가할 수 없게된다. 

동적 원형 큐는 벡터(vector)처럼 언제든 큐의 크기를 재할당을 해서 빈공간을 만드는 방법이다.

결국 3개의 큐를 구현하게 되었다

1. 기존방식의 동적배열을 이용한 큐

https://forestbird0.tistory.com/44

2. 원형 큐

https://forestbird0.tistory.com/45

3. 동적 원형 큐

https://forestbird0.tistory.com/47

생성자와 소멸자는 이전에 포스팅한 벡터와 동일합니다.

PushBack()

스택은 당연히 뒤에 값을 추가하는건데 굳이 Back이라는 단어를 사용한 이유는 명확성 때문에 사용했습니다.

	//마지막 위치에 원소를 추가합니다
	void PushBack(const Data& data)
	{
		//컨테이너에 비어있는 자리가 있는지 확인
		if (this->my_size == this->my_capacity)
		{
			//빈자리 없음. 재할당을 시도합니다
			this->Reserve(this->my_capacity + this->additive_capacity);
		}

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

1. 스택에 빈자리 체크

2. 추가

Reserve()에 대해선 여기를 봐주세요

https://forestbird0.tistory.com/38

스택도 벡터처럼 내부적으로 '동적 배열'을 사용하기 때문에 벡터와 크게 차이가 없습니다. 구현이 더 쉬운편에 속하죠.

언제든 마지막 위치에 원소를 추가하기 때문에 순서가 꼬이는 걱정도 하지 않아도 됩니다.

PopBack()

Top()

	Data& PopBack()
	{
		this->CheckValidIndex(this->my_size - 1);
		return this->my_base[this->my_size-- - 1];
	}

	Data& Top()
	{
		this->CheckValidIndex(this->my_size - 1);
		return this->my_base[this->my_size - 1];
	}

정말 간단하죠?

1. 인덱스 유효성 검사

2. 값 반환.

그저 둘 함수의 차이가 있다면, PopBack()은 반환하면서 원소를 삭제합니다. 삭제라고 표현했지만 원소자체가 삭제되지는 않고, 스택 원소개수 카운팅을 1개 줄입니다. 그러면 다음에 PushBack()으로 원소를 채우면 기존 원소값을 덮어씌워버리게 됩니다.

Top()은 마지막 원소를 반환만 할 뿐 삭제하진 않습니다.

스택 구현은 어렵지 않습니다. 구현자체에 목적을 두지 말고

내부적으로 '동적 배열'이 어떻게 활용되는지를 봐야 합니다. 

https://github.com/ForestBird1/MyContainer

스택은 LIFO(Last-in First-Out)규칙을 가지고 있어서 스택원소를 반환할 때 마지막에 들어온 데이터를 반환하게 됩니다.

마치 차곡차곡 쌓인 무언가와 비슷합니다. 가장 먼저들어간 물체는 제일 밑에 있어서 가장 마지막에 꺼내야하죠. 그리고 당연히 중간에 있는 원소를 가져올 수도 없습니다.

이런 방법은 함수를 호출할 때와 동일합니다.

함수가 호출되면 스택메모리영역에 쌓이게 되고 모든 함수의 호출이 완료되었으면 마지막(가장 최근)에 호출했던 함수부터 차례대로 반환하게 됩니다.

스택은 LIFO규칙만 생각하고 만들면 굉장히 쉽게 구현할 수 있습니다.

벡터처럼 모든원소에 접근할 필요가 없고, 반복자도 필요없습니다.

물론 필요에 의해서 구현할 수는 있지만, 필수는 아닙니다.

1. PushBack()

원소를 추가할 때 사용되는 유일한 함수입니다.

2. PopBack()

마지막으로 추가된 원소를 반환하고 삭제합니다.

3. Num()

스택의 원소개수입니다. 원소가 0개라면 1,2번 함수를 호출하면 런타임에러를 발생하기 때문에

해당 함수로 원소개수를 체크해야할 상황이 생깁니다.

이 정도의 함수면 스택을 구현할 수 있습니다. 빡 조이면 3번을 빼고 1번과 2번함수만으로 구현할 수 있죠.

그러나 편의성을 위해서 몇개 더 구현하겠습니다.

4. Top()

마지막으로 추가된 원소를 반환하지만, 원소를 삭제하지 않습니다.

5. IsEmpty()

스택이 비어있으면 true, 1개 이상의 원소가 있으면 false를 반환합니다

예제코드에서는 5번함수가 구현되어있지 않습니다. 한번 직접 구현해보세요.

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 = 32;
public:
	//컨테이너의 공간을 새로 생성합니다
	void Reserve(size_t capacity)
	{
		//기존 캐퍼시티가 더 크다면 재할당을 하지 않습니다
		if (my_capacity >= capacity)
			return;

		Data* temp = new Data[capacity];
		my_capacity = capacity;

		//컨테이너에 원소가 있다면 새로 할당한 주소로 옮겨줍니다
		if (my_size >= 1)
		{
			for (size_t i = 0; i < my_size; i++)
			{
				temp[i] = my_base[i];
			}
			delete[] my_base;

		}

		my_base = temp;
	}

	//배열의 원소를 삭제하지않고
	//사이즈를 0으로 만듭니다
	//Clear()함수후에 원소룰 추가하면 기존에 있던 원소를 덮어씌웁니다
	void Clear()
	{
		my_size = 0;
	}

	//컨테이너의 원소개수입니다
	size_t Num()
	{
		return my_size;
	}

	//컨테이너의 캐퍼시티개수입니다
	size_t Max()
	{
		return my_capacity;
	}
	
	//인덱스 유효성검사를 합니다
	//유효하지 않으면 throw
	bool CheckValidIndex(const size_t index)
	{
		if ((index >= 0) && (index < this->my_size))
		{
			return true;
		}
		else
		{
			throw printf("범위를 벗어난 인덱스를 사용하였습니다. 접근하려는 인덱스: %d, 배열크기: %d", index, this->Num());
		}
	}
};

#include "Container_Master.h"

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

};

이전에 포스팅했던 벡터와 중복되는 함수는 부모클래스에서 다룹니다.

내부적으론 벡터와 동일하게 '동적 배열'을 사용합니다.

다만 중간삽입, 삭제가 없이 마지막위치에서 삭제, 삽입을 하기 때문에 당연히 모든 원소가 메모리에서 인접해 있고, 원소의 순서가 보장되어 있습니다.

https://github.com/ForestBird1/MyContainer