[C++ Data Structure] 스택

스택

스택(Stack)은 LIFO(Last In First Out)의 구조를 가진 자료구조입니다.
가장 나중에 삽입된 요소가 가장 먼저 제거됩니다.

대표적으로 모바일 앱을 사용하면 뒤로 가기 버튼에 활용하는 자료구조가 스택입니다.

함수의 호출 스택을 관리할 때 사용됩니다.
문자열을 역순으로 뒤집는 알고리즘에서 스택을 사용할 수 있습니다.
프로그래밍 언어에서 괄호가 제대로 닫혔는지 검사하는 알고리즘에서 사용됩니다.
비선형 자료 구조에서 깊이 우선 탐색(DFS)알고리즘 구현에 사용됩니다.
Undo/Redo의 최근 작업을 저장하거나 되돌리는 기능에 사용됩니다.

스택은 컨테이너 어댑터(Container Adapter)로 다른 컨테이너를 기반으로 동작합니다.
기본적으로 std::deque를 사용하지만, std::vector, std::list같은 다른 컨테이너를 기반으로 사용할 수 있습니다.

삽입, 제거, 최상단 요소 접근, 비어 있는지 확인하는 모든 시간 복잡도는 $O(1)$입니다.

배열 기반 스택은 고정된 크기를 가지며, 초과할 경우 오버플로우가 발생합니다.

스택 구현

벡터를 사용해서 구현한 방법은 다음과 같습니다.

class Stack {
private:
    // 벡터를 이용해 관리
    std::vector<int> stack; 
public:
    Stack() = default; // 기본 생성자 자동 생성

    // 스택의 맨 위 데이터를 반환
    int top() {
        if (stack.empty()) {
            throw std::out_of_range("스택이 비어있어요!");
        }

        return stack.back();
    }

    // 스택에 데이터를 추가
    void push(int value) {
        stack.push_back(value);
    }

    // 스택의 맨 위 데이터를 제거
    void pop() {
        if (stack.empty()) {
            throw std::underflow_error("스택이 비어서 꺼낼게 없어요!");
        }
        stack.pop_back();
    }
};