자료구조) Stack 자료형

Stack

Stack(스택)은 LIFO(Last In, First Out)(후입선출) 원칙을 따르는 선형 자료구조다.

즉, 마지막에 들어간 요소가 가장 먼저 나오는 구조다.

흔히 접시를 쌓아 올리는 것과 유사한 개념으로 설명한다.

스택은 일반적으로 배열(Array) 또는 연결 리스트(Linked List) 로 구현된다. (이번에는 배열로 글을 작성)

주요 연산으로는 Push(삽입), Pop(삭제), Top(조회) 등이 있고, 보통 크기를 조절할 수 있는 Resize 기능이 포함 된다.

예시 코드

#include <iostream>
using namespace std;

template <typename T>
class Stack {
private:
    T* arr;       // 스택 요소를 저장할 동적 배열
    int capacity; // 스택의 최대 크기
    int top;      // 스택의 최상단 인덱스

public:
    // 생성자: 초기 크기 설정
    Stack(int size = 2) {
        capacity = size;
        arr = new T[capacity];
        top = -1;  // 스택이 비어있음을 의미
    }

    // 소멸자: 동적 할당 해제
    ~Stack() {
        delete[] arr;
    }

    // 1. 스택 크기 변경 (배열 크기 재할당)
    void Resize(int newSize) {
        if (newSize <= capacity) return; // 크기 증가만 허용

        T* newArr = new T[newSize]; // 새로운 배열 할당
        for (int i = 0; i <= top; i++) {
            newArr[i] = arr[i]; // 기존 요소 복사
        }
        // memcpy(new_stack, stack_, sizeof(T) * Size()); // memcpy로도 복사 가능

        delete[] arr; // 기존 배열 해제
        arr = newArr; // 새 배열 적용
        capacity = newSize;
    }

    // 2. 스택이 비어있는지 확인
    bool IsEmpty() {
        return top == -1;
    }

    // 3. 스택의 현재 크기 반환
    int Size() {
        return top + 1;
    }

    // 4. 최상단 요소 반환 (읽기)
    T& Top() const {
        if (IsEmpty()) {
            throw runtime_error("Stack is empty!");
        }
        return arr[top];
    }

    // 5. 요소 추가 (Push)
    void Push(const T& item) {
        if (top + 1 == capacity) {
            Resize(capacity * 2); // 공간 부족 시 크기 증가
        }
        arr[++top] = item;
    }

    // 6. 최상단 요소 제거 (Pop)
    void Pop() {
        if (IsEmpty()) {
            throw runtime_error("Stack is empty!");
        }
        top--; // 단순히 인덱스 감소 (메모리는 유지됨)
    }
};

int main() {
    Stack<int> stack(5); // 크기 5의 스택 생성

    stack.Push(10);
    stack.Push(20);
    stack.Push(30);
    
    cout << "Top Element: " << stack.Top() << endl; // 30
    stack.Pop();
    cout << "Top Element after Pop: " << stack.Top() << endl; // 20

    cout << "Stack Size: " << stack.Size() << endl; // 2
    cout << "Is Stack Empty? " << (stack.IsEmpty() ? "Yes" : "No") << endl; // No

    return 0;
}

Resize

• 스택의 크기를 i로 조정하는 함수

• 동적 배열을 사용하여 크기를 변경하는 경우 realloc 또는 new를 사용하여 메모리를 재할당할 수 있다.

• 크기를 줄이면 초과하는 요소들이 삭제될 수 있다.

IsEmpty

• 스택이 비어 있는지 여부를 반환하는 함수.
• 보통 size == 0인지를 확인하여 구현된다.
• 반환값:
  • true (스택이 비어 있음)
  • false (스택에 요소가 있음)

Size

• 현재 스택에 저장된 요소의 개수 반환.
• 내부적으로 size 변수를 관리하여 O(1)의 시간 복잡도로 반환하는 것이 일반적이다.

Top

• 스택의 가장 상단(top)에 있는 요소를 반환하는 함수.
• 요소를 삭제하지 않고 참조(reference) 또는 포인터로 반환.
• 주의: 스택이 비어 있을 경우 에러가 발생할 수 있으므로, IsEmpty() 검사를 먼저 수행하는 것이 일반적.

Push

• 새로운 요소 item을 스택의 최상단에 추가하는 함수.
• 내부적으로 배열을 사용할 경우, 스택 크기가 한계에 도달하면 Resize를 호출하여 크기를 증가시킬 수 있다.

Pop

• 스택의 최상단 요소를 제거하는 함수.
• 요소를 단순히 제거하는 것으로, 반환 값이 없다.
• 주의: 스택이 비어 있으면 호출 시 에러가 발생할 수 있으므로, IsEmpty()를 먼저 확인.