마지막에 넣은 것을 먼저 꺼내는(LIFO, Last-In-First-Out) 자료구조. 접시를 쌓았다가 위에서부터 빼는 것과 같다.
연산
| push(x) | — 맨 위에 넣기 | O(1) |
|---|---|---|
| pop() | — 맨 위에서 빼기 | O(1) |
| peek() | — 맨 위 보기(안 뺌) | O(1) |
한쪽 끝에서만 넣고 뺀다. 이 제약이 오히려 쓰임을 명확하게 만든다.
어디에 쓰이나 — 실제로 매일 쓰고 있다
① 함수 호출 스택
프로그램이 함수를 부를 때마다 스택 프레임이 쌓인다.
main() 호출 → [main]
main이 a() 호출 → [main][a]
a가 b() 호출 → [main][a][b]
b 반환 → [main][a] ← 가장 최근 것부터 정리
각 프레임에는 지역 변수, 매개변수, 돌아갈 주소가 들어 있다. "마지막에 부른 함수가 먼저 끝난다"는 성질이 정확히 LIFO다.
재귀가 깊으면 StackOverflowError 가 나는 이유가 이것이다 —
스택 영역(보통 1MB 내외)이 프레임으로 가득 찬 것이다.
② 되돌리기(Undo) — 최근 작업부터 취소 ③ 괄호 검사 — 여는 괄호를 push, 닫는 괄호에서 pop해 짝 확인 ④ DFS — 재귀가 곧 스택이고, 반복문으로 바꿀 때 명시적 스택을 쓴다 ⑤ 후위 표기식 계산 — 컴파일러의 수식 처리
자바에서 무엇을 쓰나 — 실무 포인트
Deque<Integer> stack = new ArrayDeque<>(); // ✅ 권장
stack.push(1);
stack.pop();
Stack<Integer> old = new Stack<>(); // ❌ 레거시
java.util.Stack은 쓰지 않는다.
Vector를 상속해 모든 메서드가 동기화되어 있다 → 단일 스레드에서도 느리다- 상속 때문에
get(0),add(0, x)같은 스택이 아닌 연산이 노출된다 - 반복 순서가 아래에서 위로라 직관과 반대다
ArrayDeque는 배열 기반이라 캐시 효율도 좋다.
스택 메모리와 힙 메모리
같은 "스택"이라는 말이 자료구조와 메모리 영역 둘 다를 가리켜 헷갈린다.
| 스택 영역 | 힙 영역 | |
|---|---|---|
| 담기는 것 | 지역 변수, 매개변수, 반환 주소 | new로 만든 객체 |
| 정리 시점 | 함수가 끝나면 자동 | GC가 수거 |
| 크기 | 작음(스레드당 1MB 내외) | 큼 |
| 속도 | 매우 빠름(포인터만 이동) | 상대적으로 느림 |
메모리 영역이 스택인 이유가 바로 이 자료구조 때문이다 — 함수 호출이 LIFO이므로 스택 포인터를 올렸다 내리는 것만으로 할당·해제가 끝난다.