스택 (Stack)

스택 (Stack)

후입선출(LIFO, Last In First Out) 원칙을 따르는 선형 자료구조로, 한쪽 끝(top)에서만 삽입(push)과 삭제(pop)가 이루어지는 제한적 접근 구조

목적: LIFO 순서 유지, 함수 호출 관리, 역순 처리, 상태 저장

특징: LIFO, 제한적 접근(top만), 동적 크기, 단순 연산

연산

• •push(item): top에 삽입, O(1)
• •pop(): top 제거 및 반환, O(1)
• •peek()/top(): top 조회(제거 없음), O(1)
• •isEmpty(): 비어있는지 확인, O(1)
• •size(): 요소 개수, O(1)

구현: 배열(고정/빠름) 또는 연결 리스트(동적/유연)

시간 복잡도: push/pop/peek 모두 O(1)

공간 복잡도: O(n)

장점: 단순한 구현, 빠른 연산(O(1)), 명확한 LIFO 의미, 메모리 효율

단점: 제한적 접근(top만), 중간 요소 접근 불가, 스택 오버플로우 위험

적용사례

• •함수 호출 스택(Call Stack)
• •괄호 매칭 검사
• •후위 표기법(Postfix) 계산
• •DFS(깊이우선탐색)
• •브라우저 뒤로가기
• •Undo 기능
• •재귀 시뮬레이션

비교: 스택(LIFO/한쪽) vs 큐(FIFO/양쪽)

연관: 큐, 재귀, DFS, 후위 표기법, Call Stack