스택 - Stack (C++ 코드구현, 소스코드, 개념)

 

스택 (STACK)

스택은 데이터 구조로, LIFO(Last In, First Out) 원칙에 따라 동작되는 선형 자료구조입니다. 한마디로 가장 최근에 추가된 항목이 가장 먼저 제거되는 방식으로 작동하는 것을 의미합니다.

 

작동 원리

스택은 PUSH와 POP이라는 연산을 통해 동작되는 자료구조입니다. 앞서말한 LIFO라는 원칙에 따라 동작되어, PUSH 연산은 테트리스와 같이 한곳에 계속 쌓이는 형태입니다. 마찬가지로, POP 연산은 가장 최근에 추가된 데이터를 제거하는 역할을 합니다. 아래사진에서 작동방식을 확실하게 이해할 수 있습니다.

사진출처 : en.wikipedia.org

 

 

이후 스택을 C++언어로 구현한 코드와 함께 설명하도록 하겠습니다.

 

 

WIKIPEDIA

Stack (abstract data type) - Wikipedia

---

#include <iostream>

#define MAX_STACK_SIZE 100 // 스택의 최대 크기를 100으로 임의지정했습니다

class Stack {
private:
    int top = -1;
    int data[MAX_STACK_SIZE];

public:
    // 스택이 비어있는지 확인
    bool is_empty()
    {
        return this->top == -1;
    }

    // 스택이 가득 차 있는지 확인
    bool is_full()
    {
        return this->top == MAX_STACK_SIZE - 1; // top이 스택의 최대 크기인 99인덱스를 가리키고 있는지 확인
    }

    // 스택에 데이터를 푸시 (삽입)
    bool push(int value) {
        // 스택이 가득 차있으면 푸시할 수 없기 때문에 오류문구 출력
        if (this->is_full()) 
        {
            std::cout << "스택이 가득 차 있습니다" << std::endl;
            return false;
        }
        // 스택에 데이터를 푸시하고 top을 1 증가시킵니다
        this->data[++this->top] = value;
        return true;
    }
    
    // 스택에 데이터를 팝 (삭제)
    bool pop(int* result)
    {
        if (this->is_empty())
        {
            std::cout << "스택이 비어있습니다" << std::endl;
            return false;
        }
        *result = this->data[this->top--];
        return true;
    }
};

 

위 코드에서 메소드들을 각각 설명하도록 하겠습니다.

 

bool is_empty()

이 메소드는 스택이 비어 있는지 확인하는 데 사용됩니다. Stack 클래스를 구현할 때, top이라는 스택의 데이터 위치를 가리키는 private 멤버 변수를 선언하였습니다. 이 변수는 객체가 생성될 때 -1로 초기화됩니다. 따라서, top 변수가 -1의 값을 가질 경우, 스택에 데이터가 없다는 것을 의미합니다. 이 메소드를 통해 pop 연산을 수행할 때, 스택이 비어 있으면 pop 연산을 수행하지 않고 거짓값을 반환하여 오류를 방지할 수 있습니다.

 

bool is_full()

이 메소드는 스택이 가득 차 있는지 확인하는 데 사용됩니다. 스택 데이터의 최대 크기를 100으로 설정하였고, data라는 배열을 private 멤버 변수로 선언하였습니다. 배열에 100의 크기를 선언하면, 이 배열의 인덱스는 0부터 99까지 생성됩니다. 그래서, is_full() 메소드에서 데이터의 최대 크기에 -1을 한 값이 top의 값과 동일한지 확인하고, 동일하면 true를 반환하도록 구현하였습니다. 이 메소드는 스택이 가득 차 있으면 push 연산을 수행하지 않고 거짓값을 반환하여 오류를 방지할 수 있습니다.

 

bool push(int value)

이 메소드는 스택의 push 연산을 수행합니다. 데이터가 이미 최대 크기에 도달했는지 확인하는 작업이 필요하기 때문에, is_full() 메소드를 사용하여 이를 확인하고, 오류를 방지하였습니다. 그리고 나서 top을 1 증가시키고, data[top] 위치에 매개변수로 받은 value를 저장합니다.

 

bool pop(int* result)

이 메소드는 스택의 pop 연산을 수행합니다. pop 메소드는 데이터를 삭제하므로, 데이터가 없으면 오류가 발생할 수 있습니다. 따라서, is_empty() 메소드를 사용하여 오류를 방지하였습니다. 그리고 나서 포인터를 매개변수로 선언하여, 해당 포인터에 값을 저장하고, top의 값을 1 감소시킵니다.