ADT(Abstract Data Type)

집합, 리스트, 스택, 큐, 트리처럼 자료구조 과목에서 흔히 볼 수 있는 것들을 추상적 자료형(Abstract Data Type)이라고 부른다. 이들은 공통점이 한가지 있는데, 자료 자체의 형태와 그 자료에 관계된 연산들이 수학적으로만 정의되어 있다는 것이다.

• Stack은 삽입한 순서대로 쌓이는 값들의 모임이고, 스택의 제일 위에 값을 삽입하는 push와 제일 위의 값을 하나 빼서 반환하는 pop 연산이 있다. 스택이 비었는지 알아보는 empty 연산, 스택에 쌓인 값이 몇 개인지 알아보는 size 연산이 정의될 수 있다.

형태와 연산이 수학적으로만 정의되어 있다. 구현의 세부사항은 전혀 정의되지 않았다. 따라서 스택이 내부적으로 array로 구현되는지, linked list로 구현되는지, size 연산을 수행할 때 원소의 개수를 일일히 세는지, 아니면 개수를 따로 저장해 두는지와 같은 세부 사항들은 다뤄지지 않는다. 따라서, ADT는 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것이다. Java에서 추상 메소드의 집합인 interface와 비슷한 맥락이다.