스택이란?
스택(Stack)은 후입선출(LIFO, Last In First Out) 원칙을 따르는 자료구조입니다. 가장 나중에 넣은 데이터가 가장 먼저 나옵니다.
접시를 쌓아올리는 것을 생각해보세요. 새 접시는 맨 위에 올리고, 사용할 때도 맨 위부터 꺼냅니다. 이것이 바로 스택의 동작 원리입니다.
왜 중요한가?
스택은 프로그래밍의 가장 기본적인 자료구조이며, 놀라울 정도로 많은 곳에서 사용됩니다.
- •함수 호출 스택: 프로그램의 함수 호출과 복귀가 스택으로 관리됨
- •DFS 구현: 깊이 우선 탐색을 반복문으로 구현할 때 스택 사용
- •코딩 테스트 필수: 괄호 검사, 히스토그램 최대 직사각형, 주식 가격 등
주요 연산
| 연산 | 설명 | 시간복잡도 |
|---|---|---|
| push(item) | 스택 맨 위에 원소 추가 | O(1) |
| pop() | 스택 맨 위 원소 제거 후 반환 | O(1) |
| peek() / top() | 맨 위 원소 확인 (제거 안 함) | O(1) |
| isEmpty() | 스택이 비어있는지 확인 | O(1) |
모든 연산이 O(1)입니다. 항상 맨 위(top)에서만 작업하기 때문입니다.
실전 활용 예제
1. 괄호 검사
프로그래밍에서 가장 흔한 스택 활용입니다. 여는 괄호를 만나면 push, 닫는 괄호를 만나면 pop하여 짝이 맞는지 확인합니다.
- •
(),[],{}— 올바른 괄호 - •
([)]— 올바르지 않은 괄호
2. 브라우저 뒤로가기/앞으로가기
뒤로가기 스택과 앞으로가기 스택 2개를 사용합니다. 새 페이지 방문 시 현재 페이지를 뒤로가기 스택에 push하고, 뒤로가기 시 앞으로가기 스택에 push합니다.
3. 실행 취소 (Undo)
텍스트 편집기의 Ctrl+Z가 스택입니다. 모든 작업을 스택에 push하고, 취소할 때 pop합니다.
4. DFS (깊이 우선 탐색)
재귀 대신 명시적 스택을 사용하여 DFS를 구현할 수 있습니다. 스택에서 노드를 꺼내고, 인접 노드를 push하는 방식입니다.
스택 vs 큐
| 비교 | 스택 | 큐 |
|---|---|---|
| 원리 | LIFO (후입선출) | FIFO (선입선출) |
| 비유 | 접시 쌓기 | 줄 서기 |
| 추가 | push (맨 위) | enqueue (맨 뒤) |
| 제거 | pop (맨 위) | dequeue (맨 앞) |
| 활용 | DFS, 괄호 검사, Undo | BFS, 프린터 대기열, 캐시 |
코딩 테스트에서 자주 나오는 스택 문제 유형
모노톤 스택 — 스택에 원소를 단조 증가/감소 순으로 유지하면서 O(n)에 "다음으로 큰 원소"나 "이전에 작은 원소"를 찾는 기법입니다.
- •주식 가격: 가격이 떨어지지 않은 기간 계산
- •히스토그램: 최대 직사각형 면적
- •다음 큰 수: 각 원소의 오른쪽에서 처음으로 큰 수 찾기
자주 하는 실수
- •빈 스택에서 pop이나 peek을 호출하여 에러 발생 → isEmpty 체크 필수
- •괄호 문제에서 여는 괄호만 남았는데 확인하지 않고 통과 처리
- •모노톤 스택에서 push/pop 조건을 반대로 설정
알고노트에서 직접 확인하세요
push, pop이 실행될 때 스택이 어떻게 변화하는지, 알고노트에서 한 단계씩 시각적으로 확인할 수 있습니다. 다양한 연산 시퀀스를 직접 입력하고 실험해보세요.