[C++] STL 컨테이너 - Stack

 

 

• STL 컨테이너란?
  • Standard Template Library
  • 템플릿 기반으로 모든 컨테이너에 적용되는 표준 인터페이스
  • 메모리 자동관리 -> 메모리 단편화

---

💡 std::stack

• 스택이란?
  • LIFO (Last-in First-out)
  • 후입선출 자료구 - 마지막에 들어온 데이터가 가장 먼저 나가는 구조
  • 연속적인 메모리를 사용하지 않고 동적 크기 조절이 가능하다.

• 시간복잡도 - O(1)
• stack의 주요 연산
  • s.push(x) - 스택의 맨 위에 x 삽입
  • s.pop() - 스택의 맨 위 요소 제거
  • s.top() - 스택의 맨 위 요소 반환
  • s.empty() - 스택이 비어있는지 확인 (boolean)
  • s.size() - 스택의 현재 크기 반환
• C++에서 스택 사용법

#include <iostream>
#include <stack>  // stack 라이브러리

using namespace std;

int main() {
    stack<int> s;  // int형 스택 선언

    // 값 추가 (Push)
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Top element: " << s.top() << "\n"; //30 출력

    s.pop();

    cout << "New top: " << s.top() << "\n";  // 20 출력

    return 0;
}

 

📌 스택 활용 예시

1) 수열 역순 출력

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;
    int n;

    cout << "Enter numbers (0 to stop): ";
    while (true) {
        cin >> n;
        if (n == 0) break;
        s.push(n);
    }

    cout << "Reversed order: ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}

🔹 입력 예시: 1 2 3 4 5 0
🔹 출력 예시: 5 4 3 2 1

---

2) 올바른 괄호 문자열 판단 (( ) { } [ ] 체크)

#include <iostream>
#include <stack>

using namespace std;

bool isValid(string str) {
    stack<char> s;
    for (char ch : str) {
        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 input;
    cout << "Enter a string of brackets: ";
    cin >> input;
    
    if (isValid(input))
        cout << "Valid parentheses\n";
    else
        cout << "Invalid parentheses\n";
    
    return 0;
}

🔹 입력 예시: {[()()]}
🔹 출력 예시: Valid parentheses

---

 3) DFS (깊이 우선 탐색) 구현

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            cout << node << " ";
            visited[node] = true;

            // 인접 노드들을 스택에 넣음 (역순으로 넣어야 작은 노드부터 탐색 가능)
            for (int i = graph[node].size() - 1; i >= 0; i--) {
                int next = graph[node][i];
                if (!visited[next])
                    s.push(next);
            }
        }
    }
}

int main() {
    int n = 6;  // 노드 개수
    vector<vector<int>> graph(n + 1);
    vector<bool> visited(n + 1, false);

    // 무방향 그래프 입력
    graph[1] = {2, 3};
    graph[2] = {4, 5};
    graph[3] = {6};
    graph[4] = {};
    graph[5] = {};
    graph[6] = {};

    cout << "DFS traversal: ";
    dfs(1, graph, visited);
    return 0;
}

🔹 출력 예시: 1 3 6 2 5 4

---

📍 스택과 벡터(vector) 차이점

자료구조접근 방식삽입/삭제사용 목적

stack	LIFO (후입선출)	push(), pop() (O(1))	백트래킹, DFS, 괄호 검사
vector	임의 접근 가능	push_back(), erase()	동적 배열, 정렬

 

---

✅ 스택을 활용하는 알고리즘

• DFS (깊이 우선 탐색)
• 백트래킹 (Backtracking)
•  올바른 괄호 검사 (괄호 짝 맞추기 문제)
•  수식 계산 (후위 표기법, 중위 -> 후위 변환)
•  최대 히스토그램 문제 해결 (Largest Rectangle in Histogram, O(n) 해결)