정의
스택(Stack)은 후입선출(LIFO, Last In First Out) 방식의 자료구조입니다. 마치 접시를 쌓아놓은 것처럼, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내게 됩니다.
핵심 특성
- ✓LIFO (Last In, First Out) - 마지막에 넣은 것을 먼저 꺼냄
- ✓push와 pop 연산이 O(1) 시간복잡도
- ✓top으로 맨 위 요소를 확인
- ✓재귀 호출, 되돌리기(Undo) 등에 자주 활용
활용 사례
이런 상황에서 사용됩니다:
◀️
브라우저 뒤로가기
웹 브라우저에서 방문한 페이지를 스택에 저장하고, 뒤로가기 버튼을 누르면 가장 최근 페이지부터 꺼냅니다.
↩️
실행 취소 (Ctrl+Z)
문서 편집기에서 작업 내역을 스택에 저장하고, 취소할 때마다 가장 최근 작업부터 되돌립니다.
()
괄호 검사
코드의 괄호가 올바르게 닫혔는지 검사할 때, 여는 괄호를 스택에 넣고 닫는 괄호가 나오면 꺼내서 비교합니다.
🔄
재귀 → 반복 변환
재귀 함수를 반복문으로 바꿀 때, 함수 호출 상태를 스택에 저장하여 재귀와 같은 동작을 구현합니다.
주요 연산
주요 연산들:
push
O(1)스택의 맨 위에 요소를 추가합니다.
pop
O(1)스택의 맨 위 요소를 제거하고 반환합니다.
peek / top
O(1)스택의 맨 위 요소를 제거하지 않고 확인만 합니다.
isEmpty
O(1)스택이 비어있는지 확인합니다.
복잡도
시간 복잡도
최선
O(1)
평균
O(1)
최악
O(1)
공간 복잡도
O(n)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기