[자료구조] 스택(Stack) - 배열을 이용한 구현

스택 이란?

• 가장 마지막에 들어간 데이터가 제일 먼저 나온다 (Last In - First Out) LIFO
• 가장 먼저들어간 데이터는 가장 나중에 나온다 (First In - Last Out) FILO
• 변수를 선언 후 수명주기가 끝나면 자동으로 제거해주는 메모리도 스택으로 구현되어 있다.

스택의 주요 기능

• 삽입
• 제거

배열 형 스택 클래스 

class MyStack
{
public:
    MyStack();
private:

    int Capacity;
    int* Data;
    int Top;

public:

    int Pop();
    void Push(const int& NewData);
    bool IsEmpty();
    void Create(const int& Size);
    void Show();
};

배열 형 스택 초기화

MyStack::MyStack()
{
    Capacity = 0;
    Data = nullptr;
    Top = -1;
}

스택의 생성자를 통해 변수들을 초기화 해준다.

 

배열 형 스택 생성

void MyStack::Create(const int& Size)
{
    Capacity = Size;
    Data = new int[Capacity];
}

외부로부터 사이즈를 받고 그 사이즈만큼 배열형 스택을 만들어 준다.

 

배열 형 스택 삽입

void MyStack::Push(const int& NewData)
{
    if (Top < Capacity - 1)
    {
        Data[++Top] = NewData;
    }
}

외부로부터 데이터를 받고 그 데이터를 배열형 스택에 저장해준다.

처음의 Top은 -1이기에 전위증감연산자를 통해 0을 만들고 0의 위치에 데이터를 넣어준다.

그다음에 들어오는 데이터는 Top이 1이 될거고 1의 위치에 데이터를 넣게 된다.

배열 형 스택 확인

bool MyStack::IsEmpty()
{
    return Top == -1 ? true : false;
}

비어있는지 확인하는 코드이다.

Top이 -1이면 true를 반환하고 0이상이면 false를 반환한다.

bool MyStack::IsFull()
{
    return Top == Capacity - 1 ? true : false;
}

꽉차있는지 확인하는 코드이다.

Top이 Capacity-1 과 같다면  true를 반환하고 아니면 false를 반환한다.

배열 형 스택 제거

int MyStack::Pop()
{
    if (!IsEmpty())
    {
        return Data[Top--];
    }
    std::cout << "꺼낼 데이터가 없습니다" << std::endl;
    return -1;
}

비어있는지 확인 후 Top의 위치의 인덱스에 접근하여 데이터를 반환 후 Top의 위치를 -1만큼 감소시킨다.

 

메인 코드

int main()
{
    MyStack* Stack = new MyStack();
    Stack->Create(5);
    Stack->Pop();
    Stack->Push(1);
    Stack->Push(2);
    Stack->Pop();
    Stack->Push(3);
    Stack->Push(4);
    Stack->Push(5);
    Stack->Push(6);
    Stack->Show();
}

먼저 Create함수를 통해 5의 크기를 만들어 주고

Pop함수로 데이터를 꺼내옵니다. 이때 데이터가 없기에 무시되며

Push함수를 통해 1,2 를 집어 넣고 Pop함수를 실행하면 2가 제일 마지막에 들어왔기에 2가 빠져나가고

다시 Push함수를 통해 3,4,5,6을 집어 넣으면 1,3,4,5,6 이 스택배열에 존재 할 것이다.