스택(Stack)이란?
- 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출(LIFO: Last-In First-Out) 구조를 가진 자료구조.
- 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다.
스택(Stack)의 주요 메서드
- push(): 스택에 데이터 추가
- pop(): 스택 가장 위에 있는 데이터를 삭제
- Top = peek(): 스택 가장 위에 있는 데이터를 의미(가장 최근에 들어온 데이터)
- isEmpty(): 스택이 비어있으면 True, 비어있지 않다면 False를 반환
- size(): 스택의 크기 반환
스택(Stack) 사용 사례
- 재귀 알고리즘
- 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
- 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
- 스택은 이런 일련의 행위를 직관적으로 가능하게 해준다.
- 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
- 웹 브라우저 방문기록 (뒤로가기)
- 실행 취소 (undo)
- 역순 문자열 만들기
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
- Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
- 후위 표기법 계산
스택(Stack)의 장단점
- 장점
- 구조가 단순하여 구현이 쉬움
- 데이터 접근 속도가 빠름(스택 포인터 ptr을 이용하여 데이터에 저장, 삭제, 읽기가 빠름)
- 단점
- 데이터 메모리 크기를 미리 지정해야함
- 저장 공간의 낭비가 발생할 수 있음
스택(Stack)의 시간복잡도
삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가집니다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가집니다.
복습해보기
