[Data Structure] Stack

스택은 너무나 기본적이지만 유용한 자료구조이다.

스택의 정의는 다음과 같다.

a linear data structure of ordered entries such that entries can be inserted and removed at only one end (called the top)

즉, top이라고 불리는 한쪽 끝을 통해 삽입과 삭제가 이루어지는 선형 자료구조이다.

그리고  스택은 ADT로써 어떠한 형태를 가지는(배열 혹은 리스트가 될수 있다) 데이터 엔트리를 가지고
push, pop, top과 같은 operation을 이용해서 해당 자료구조를 접근하고 조작한다.


기본적인 구조 자체는 워낙 간단하기 때문에 응용분야를 살펴보는 것이 중요할 것이다.
스택의 응용분야 중 가장 대표적인 것으로는 함수 호출시 메모리를 관리하는데 사용하는 것을 들 수 있다.
매번 함수 호출 시 메모리에 Activation Record 형태로 메모리에 올라가게 된다.
또한 회문 검사, 중위 연산을 후위연산으로 변환, 일반적인 사칙연산 계산 등등에 사용될 수 있다.

그리고 알고리즘에서 나오는 기법 중 하나인 Backtracking을 사용하는 데에도 스택을 사용한다.
스택은 아주 기본적인 자료구조이기에 사용예제는 수도없이 많다.