알고리즘
Stack
다른 이름: 스택 , LIFO
정의
Last-In-First-Out (LIFO) 자료구조. 가장 나중에 넣은 것이 먼저 나옴. push(삽입), pop(제거), peek(조회) O(1). 배열 또는 연결 리스트 구현. 함수 호출 스택, 괄호 검사, DFS, 되돌리기(Undo), 계산기 구현에 사용
상세 설명
기술 스펙
- push: 맨 위에 삽입 O(1)
- pop: 맨 위에서 제거 O(1)
- peek/top: 맨 위 조회 (제거 안 함) O(1)
- 구현: 배열 (고정 크기) 또는 연결 리스트 (동적)
- Python: list 사용 (append, pop)
- C++: std::stack, Java: Stack (deprecated) → Deque
실무 활용
- 함수 호출 스택: 지역 변수, 반환 주소 저장
- 괄호 검사: ({[]}) 짝 맞는지 확인
- DFS: 깊이 우선 탐색 (재귀 또는 명시적 스택)
- 되돌리기(Undo): 작업 히스토리
- 계산기: 후위 표기법, 연산자 우선순위
장점
- 단순 구조: 구현 10줄 내외
- 빠른 연산: push/pop O(1)
- 메모리 효율: 필요한 만큼만 사용
- 재귀 대체: 명시적 스택으로 스택 오버플로우 방지
단점 및 제약
- 순차 접근만: 중간 요소 접근 불가
- 크기 제한: 배열 구현 시 오버플로우
- 캐시 미스: 연결 리스트 구현 시 성능 저하
호환성
C++ std::stack, Python list, Java Deque, JavaScript Array
표준 정보
표준화 기구: 자료구조 교과서 표준
출시 연도: 1946년