1. Stack의 정의 및 핵심 원리
- LIFO (Last In First Out): 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 방식의 자료구조.
- 특징: 데이터의 삽입과 삭제가 한쪽 끝(Top)에서만 일어나는 논리적 구조.
- 재귀적 특성: 함수 호출 등의 재귀적 문제를 해결할 때 자주 활용되는 구조.
2. 주요 연산 및 시간 복잡도
데이터의 추가와 삭제가 스택의 ‘Top’에서만 발생하므로 매우 효율적임.
| 연산 (Operation) | 설명 | 시간 복잡도 |
|---|---|---|
| Push | 스택의 맨 위(Top)에 새로운 데이터를 추가하는 작업. | O(1) |
| Pop | 스택의 맨 위(Top)에 있는 데이터를 추출하고 삭제하는 작업. | O(1) |
3. 실제 활용 사례
스택의 후입선출 특성은 역순 처리가 필요한 다양한 알고리즘과 시스템에서 사용.
- 수식 및 검사: 후위 표기법(Postfix) 연산, 괄호 유효성 검사.
- 시스템 관리: 함수 호출을 관리하는 Call Stack 구현.
- 데이터 탐색: 그래프의 깊이 우선 탐색(DFS) 알고리즘.
- 사용자 인터페이스: 웹 브라우저의 방문 기록 관리(뒤로 가기 기능).
정리
- Stack: 나중에 들어온 데이터가 먼저 나가는 LIFO 구조를 가짐.
- 연산 효율: Push와 Pop 연산 모두 O(1)의 상수 시간 복잡도를 보장.
- Queue(선입선출)와의 차이점을 명확히 인지하고, DFS나 괄호 검사 등 실제 스택이 필수적으로 활용되는 알고리즘 사례를 연관 지어 설명하는 것이 중요.
출처
- Pat Morin, Open Data Structures - Array-Based Lists https://opendatastructures.org/versions/edition-0.1e/ods-java/2_Array_Based_Lists.html
- Pat Morin, Open Data Structures - Linked Lists https://opendatastructures.org/versions/edition-0.1e/ods-java/3_Linked_Lists.html