[C언어/C++] STL 스택(Stack) 총정리 - 개념, 사용법, 시간복잡도, 예제코드, 코딩테스트 활용, 주의점

STL Stack 사용법 총 정리

 

1. Stack 개념

Stack(스택)은 후입선출(LIFO, Last In First Out) 구조를 가지는 자료구조로, 가장 나중에 삽입된 요소가 가장 먼저 제거됩니다. 대표적인 활용 예로는 DFS(깊이 우선 탐색), 수식 계산(괄호 검사, 후위 표기법 변환) 등이 있습니다.

C++ STL에서는 stack을 제공하며, std::stack을 활용하여 쉽게 사용할 수 있습니다.

반응형

---

 

 

 

2. Stack 주요 연산 및 사용법

 

STL의 stack은 <stack> 헤더 파일을 포함하여 사용합니다. 주요 연산은 다음과 같습니다.

(1) Stack 선언 및 초기화

#include <stack>
#include <stdio.h>
using namespace std;

int main() {
    stack<int> s; // 정수형 스택 선언
    return 0;
}

 

(2) 요소 삽입 (push)

#include <stack>
#include <stdio.h>
using namespace std;

int main() {
    stack<int> s;
    s.push(10); // 10 삽입
    s.push(20); // 20 삽입
    s.push(30); // 30 삽입
    printf("스택의 크기: %d\n", s.size()); // 3
    return 0;
}

 

(3) 요소 제거 (pop)

#include <stack>
#include <stdio.h>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);

    s.pop(); // 30 제거
    printf("스택의 top: %d\n", s.top()); // 20
    return 0;
}

 

(4) 최상단 요소 확인 (top)

#include <stack>
#include <stdio.h>
using namespace std;

int main() {
    stack<int> s;
    s.push(100);
    s.push(200);
    printf("현재 top: %d\n", s.top()); // 200
    return 0;
}

 

(5) 스택이 비어있는지 확인 (empty)

#include <stack>
#include <stdio.h>
using namespace std;

int main() {
    stack<int> s;
    if (s.empty()) {
        printf("스택이 비어 있습니다.\n");
    }
    s.push(1);
    if (!s.empty()) {
        printf("스택에 요소가 있습니다.\n");
    }
    return 0;
}

 

(6) 스택의 크기 확인 (size)

#include <stack>
#include <stdio.h>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    printf("스택의 크기: %d\n", s.size()); // 2
    return 0;
}

---

 

 

3. Stack의 시간 복잡도

 

각 연산의 시간 복잡도는 다음과 같습니다:

• push: O(1)
• pop: O(1)
• top: O(1)
• empty: O(1)
• size: O(1)

STL stack은 내부적으로 deque을 기반으로 구현되어 있으므로, 모든 연산이 상수 시간(O(1)) 내에 수행됩니다.

---

 

 

4. Stack 활용 예제 (코딩 테스트에서 자주 쓰이는 패턴)

(1) 괄호 문자열 검사 (올바른 괄호 판단)

#include <stack>
#include <stdio.h>
using namespace std;

bool isValid(char *str) {
    stack<char> s;
    for (int i = 0; str[i]; i++) {
        if (str[i] == '(') {
            s.push(str[i]);
        } else if (str[i] == ')') {
            if (s.empty()) return false;
            s.pop();
        }
    }
    return s.empty();
}

int main() {
    char str1[] = "(())()";
    char str2[] = "(()";
    printf("str1: %s\n", isValid(str1) ? "올바른 괄호" : "잘못된 괄호");
    printf("str2: %s\n", isValid(str2) ? "올바른 괄호" : "잘못된 괄호");
    return 0;
}

 

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

#include <stack>
#include <stdio.h>
using namespace std;

void DFS(int start, int graph[][5], int visited[], int n) {
    stack<int> s;
    s.push(start);
    visited[start] = 1;

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        printf("%d ", node);
        
        for (int i = 0; i < n; i++) {
            if (graph[node][i] && !visited[i]) {
                s.push(i);
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int graph[5][5] = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 1, 1},
        {0, 1, 1, 0, 1},
        {0, 0, 1, 1, 0}
    };
    int visited[5] = {0};
    
    printf("DFS 탐색 순서: ");
    DFS(0, graph, visited, 5);
    return 0;
}

---

 

 

5. Stack 사용 시 주의할 점

• 스택 오버플로우(Stack Overflow): 스택이 너무 커지면 메모리 초과로 프로그램이 비정상 종료될 수 있습니다.
• empty()를 사용하여 pop() 전에 확인: 빈 스택에서 pop()을 호출하면 런타임 오류가 발생할 수 있습니다.

---

 

이번 포스팅에서는 stack의 개념과 사용법을 자세히 살펴보았습니다. stack은 DFS, 괄호 검사, 수식 계산 등 다양한 문제에서 활용되므로 코딩 테스트에서 반드시 익혀두어야 하는 자료구조입니다.