[알고리즘/이론]스택

 

가장 최근에 삽입된 원소부터 삭제되는 동적 집합 자료 구조(후입선출, LIFO, Last in First out)

원소를 삽입하는 연산은 push, 원소를 추출하는 연산을 pop이라고 한다.

스택의 top은 가장 최근에 삽입된 원소를 가리킨다. top = 0 이면 스택을 비어있다는 것이며 이때 pop을 실행하면 스택 부족(underflow) 오류가 발생한다. 반대로 스택이 가득찬 상태에서 원소를 삽입하면 스택 포화(overflow) 오류가 발생한다.

push, pop의 수행시간

모두 O(1)의 수행시간이 걸린다.