스택은 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
GitHub - ForestBird1/MyContainer
Contribute to ForestBird1/MyContainer development by creating an account on GitHub.
github.com
'C++ 자료구조' 카테고리의 다른 글
| [C++] 나만의 Queue만들기 (0) - 기초 (0) | 2023.08.27 |
|---|---|
| [C++] 나만의 Stack만들기 (2) - Push,Pop,Top 함수 구현 (0) | 2023.08.25 |
| [C++] 나만의 Vector만들기 (4) - 이터레이터(iterator), operator (0) | 2023.08.25 |
| [C++] 나만의 Vector만들기 (3) - 원소 삽입, 삭제 (0) | 2023.08.25 |
| [C++] 나만의 Vector만들기 (2) - 생성자, 소멸자, 캐퍼시티, Reserve (0) | 2023.08.24 |
