개념
스택은 LIFO(Last In First Out) 원칙을 따르는 자료구조이다. 가장 나중에 삽입된 요소가 가장 먼저 삭제된다.
- 한쪽 끝(top)에서만 삽입과 삭제가 일어난다
- push: 요소 삽입
- pop: 요소 삭제
- top/peek: 맨 위 요소 확인
- 함수 호출 스택, 수식 계산, 괄호 검사 등에 활용된다
핵심 연산 & 시간복잡도
| 연산 | 시간복잡도 | 설명 |
|---|
| push | O(1) | 맨 위에 삽입 |
| pop | O(1) | 맨 위 삭제 |
| top | O(1) | 맨 위 확인 |
| empty | O(1) | 비어있는지 확인 |
| size | O(1) | 크기 확인 |
구현 (No-STL)
배열 기반 스택
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| const int MAX_SIZE = 100001;
int stack[MAX_SIZE];
int top_idx = -1;
void init() {
top_idx = -1;
}
bool isEmpty() {
return top_idx == -1;
}
bool isFull() {
return top_idx == MAX_SIZE - 1;
}
void push(int x) {
if (isFull()) return; // 오버플로우 방지
stack[++top_idx] = x;
}
void pop() {
if (isEmpty()) return; // 언더플로우 방지
top_idx--;
}
int top() {
if (isEmpty()) return -1; // 에러 처리
return stack[top_idx];
}
int size() {
return top_idx + 1;
}
|
구조체로 캡슐화
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| const int MAX_SIZE = 100001;
struct Stack {
int data[MAX_SIZE];
int top_idx;
void init() {
top_idx = -1;
}
bool isEmpty() {
return top_idx == -1;
}
void push(int x) {
data[++top_idx] = x;
}
void pop() {
if (!isEmpty()) top_idx--;
}
int top() {
if (isEmpty()) return -1;
return data[top_idx];
}
int size() {
return top_idx + 1;
}
};
Stack st;
|
연결 리스트 기반 스택
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| const int MAX_NODE = 100001;
struct Node {
int data;
int next;
} node[MAX_NODE];
int nodeCnt;
int top_idx;
void init() {
nodeCnt = 0;
top_idx = -1;
}
void push(int x) {
node[nodeCnt].data = x;
node[nodeCnt].next = top_idx;
top_idx = nodeCnt++;
}
void pop() {
if (top_idx == -1) return;
top_idx = node[top_idx].next;
}
int top() {
if (top_idx == -1) return -1;
return node[top_idx].data;
}
bool isEmpty() {
return top_idx == -1;
}
|
STL
std::stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <stack>
// 선언
std::stack<int> st;
std::stack<int, std::vector<int>> st2; // 내부 컨테이너 지정
// 주요 메서드
st.push(10); // 삽입
st.pop(); // 삭제 (반환값 없음)
st.top(); // 맨 위 요소 반환
st.empty(); // 비어있는지 확인
st.size(); // 크기 반환
st.emplace(10); // 생성자 직접 호출하여 삽입
// 주의: pop()은 void 반환
int val = st.top(); // 먼저 값 저장
st.pop(); // 그 다음 삭제
// 스택 비우기
while (!st.empty()) {
st.pop();
}
// 또는
st = std::stack<int>(); // 새 스택으로 교체
|
vector를 스택처럼 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <vector>
std::vector<int> st;
st.push_back(10); // push
st.pop_back(); // pop
st.back(); // top
st.empty(); // empty
st.size(); // size
// vector 사용 시 장점: 인덱스 접근, 순회 가능
for (int i = 0; i < st.size(); i++) {
// st[i] 접근 가능
}
|
사용 예시
괄호 매칭
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| bool isValid(const std::string& s) {
std::stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
char top = st.top();
st.pop();
if (c == ')' && top != '(') return false;
if (c == '}' && top != '{') return false;
if (c == ']' && top != '[') return false;
}
}
return st.empty();
}
|
후위 표기법 계산
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int evalPostfix(const std::string& expr) {
std::stack<int> st;
for (char c : expr) {
if (isdigit(c)) {
st.push(c - '0');
} else {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
switch (c) {
case '+': st.push(a + b); break;
case '-': st.push(a - b); break;
case '*': st.push(a * b); break;
case '/': st.push(a / b); break;
}
}
}
return st.top();
}
|
히스토그램에서 가장 큰 직사각형
스택을 이용한 O(N) 풀이의 대표 문제이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| long long largestRectangle(std::vector<int>& heights) {
std::stack<int> st; // 인덱스 저장
long long maxArea = 0;
int n = heights.size();
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!st.empty() && heights[st.top()] > h) {
int height = heights[st.top()];
st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxArea = std::max(maxArea, (long long)height * width);
}
st.push(i);
}
return maxArea;
}
|
단조 스택 (Monotonic Stack)
다음으로 큰 원소(Next Greater Element) 찾기에 활용된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| std::vector<int> nextGreater(std::vector<int>& arr) {
int n = arr.size();
std::vector<int> result(n, -1);
std::stack<int> st; // 인덱스 저장
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.top()] < arr[i]) {
result[st.top()] = arr[i];
st.pop();
}
st.push(i);
}
return result;
}
|
DFS (재귀 대신 스택 사용)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void dfsIterative(int start, std::vector<std::vector<int>>& adj) {
int n = adj.size();
std::vector<bool> visited(n, false);
std::stack<int> st;
st.push(start);
while (!st.empty()) {
int cur = st.top();
st.pop();
if (visited[cur]) continue;
visited[cur] = true;
// cur 처리
for (int next : adj[cur]) {
if (!visited[next]) {
st.push(next);
}
}
}
}
|
주의사항 / Edge Cases
빈 스택에서 pop/top
1
2
3
4
5
6
7
8
9
10
11
| std::stack<int> st;
// 위험: Undefined Behavior
// st.pop(); // 빈 스택에서 pop
// st.top(); // 빈 스택에서 top
// 안전한 코드
if (!st.empty()) {
int val = st.top();
st.pop();
}
|
스택 오버플로우 (재귀)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| // 위험: 깊은 재귀로 인한 스택 오버플로우
void recursiveDFS(int depth) {
if (depth == 0) return;
recursiveDFS(depth - 1); // depth가 크면 스택 오버플로우
}
// 해결: 반복문 + 명시적 스택 사용
void iterativeDFS(int depth) {
std::stack<int> st;
st.push(depth);
while (!st.empty()) {
int d = st.top();
st.pop();
if (d > 0) st.push(d - 1);
}
}
|
pop() 반환값 주의
1
2
3
4
5
6
7
8
9
| std::stack<int> st;
st.push(10);
// 잘못된 코드
// int val = st.pop(); // 컴파일 에러: pop()은 void
// 올바른 코드
int val = st.top();
st.pop();
|
배열 기반 스택 크기 초과
1
2
3
4
5
6
7
8
9
10
11
12
| const int MAX_SIZE = 1000;
int stack[MAX_SIZE];
int top_idx = -1;
// push 전에 크기 체크
void push(int x) {
if (top_idx >= MAX_SIZE - 1) {
// 오버플로우 처리
return;
}
stack[++top_idx] = x;
}
|
추천 문제