ForestBird

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

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