4.1 What is Stack?

stack은 LIFO/ (Last In, First Out) 구조를 따르는 데이터 컨테이너이다. 가장 나중에 삽입된 데이터가 가장 먼저 제거된다.

4.2 Stack 사용법

다음과 같은 작업이 지원된다.
- push: 데이터를 스택의 맨 위에 추가
- pop: 스택의 맨 위 데이터를 제거
- top: 스택의 맨 위 데이터를 조회
- empty: 스택의 공백 여부 확인
- size: 스택에 포함된 요소의 개수 반환

#include <iostream>
#include <stack>

using namespace std;                        

int main() {
    stack<int> s;

    // 데이터 추가 (push)
    s.push(10);
    s.push(20);
    s.push(30);

    // 맨 위 데이터 출력 (top)
    cout << "스택의 맨 위: " << s.top() << endl; // 30

    // 데이터 제거 (pop)
    s.pop();
    cout << "스택의 맨 위: " << s.top() << endl; // 20

    // 크기 확인
    cout << "스택 크기: " << s.size() << endl; // 2

    // 스택 비우기
    while (!s.empty()) {
        s.pop();
    }

    cout << "스택 비어 있음: " << (s.empty() ? "Yes" : "No") << endl;

    return 0;
}

4.3 Stack 내부 컨테이너

stack은 기본적으로 컨테이너 어댑터로, 다른 컨테이너를 기반으로 작동한다. 기본 컨테이너는 deque이며, 이를 vector 또는 list로 변경할 수도 있다.

#include <stack>
#include <vector>
#include <list>

using namespace std;

int main() {
    stack<int, vector<int>> s1; // vector 기반
    stack<int, list<int>> s2;   // list 기반

    s1.push(10);
    s2.push(20);

    return 0;
}

※ 주의
- deque는 양쪽에서 빠르고 효율적으로 요소를 추가 또는 삭제할 수 있다.
- vector는 동적 배열로 크기 조절이 필요할 때 성능 비용이 발생할 수 있다.
- list는 연속적인 메모리를 요구하지 않으며, 삽입/삭제가 항상 $O(1)$이다.

4.4 사용 예제

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool isBalanced(const string& expr) {
    stack<char> s;

    for (char ch : expr) {
        if (ch == '(' || ch == '{' || ch == '[') {
            s.push(ch);
        }
        else {
            if (s.empty()) return false;

            char top = s.top();
            if ((ch == ')' && top == '(') ||
                (ch == '}' && top == '{') ||
                (ch == ']' && top == '[')) {
                s.pop();
            }
            else {
                return false;
            }
        }
    }
    return s.empty();
}

int main() {
    string expr = "{[()]}";
    cout << (isBalanced(expr) ? "Balanced" : "Not Balanced") << endl;

    return 0;
}