[자료구조] 스택 (Stack)

push(val): val을 스택의 최상위에 삽입한다.
pop(): 스택의 top에 있는 객체를 스택에서 제거한다. 만약 빈(empty) 스택이라면 오류를 발생한다.
top(): 스택의 최상위 원소를 반환한다. 만약 빈(empty) 스택이라면 오류를 발생한다.
size(): 스택 내의 객체의 개수를 반환한다.
empty(): 스택이 비어 있는지 여부를 bool형으로 반환한다.

개념

스택(stack)은 어떤 리스트에서 모든 입력과 출력이 한쪽 끝에서만 일어나는 구조이다. 즉, 새로운 항목을 리스트 안으로 입력하는 것(삽입)과 리스트 내에 이미 들어 있는 항목을 출력하는 것(삭제)이 모두 리스트의 한쪽 끝(top)에서만 일어나는 항목들의 순서 집합을 의미한다. 이러한 방식을 후입선출(LIFO, Last In First Out)이라 한다.

스택은 재귀 호출, 후위 표현식의 계산, 백트래킹, 트리와 그래프의 깊이 우선 탐색 등에 사용된다.