자료data와 자료들에 대한 연산operation을 명기한 것. 추상 자료형은 구현 방법을 명시하고 있지 않다. 즉, 구현체에 대한 내용이 없이 껍데기만 존재한다고 생각하면 된다.
왜 ADT가 필요할까
구현체가 되는 자료구조의 인터페이스 역할을 한다. 아래 네 가지의 이점이 따라온다.
- 모듈화 / 추상화
- 다형성 / 유연성 확보
- 표준화
구현체가 되는 자료구조는 개발자가 직접 구현하든, 아니면 미리 구현 되어 있는 라이브러리를 사용하든 어떤 언어를 사용하더라도 ADT의 스펙사항을 만족해야 한다.
따라서 개발자는 ADT만 알아도 자료구조의 세부구현과 관계 없이 데이터가 어떤 식으로 구축될지 개략적인 데이터 설계를 할 수 있게 된다.
ADT는 자료형의 수학적 모델링이다. 데이터가 어떻게 표현되는지에 대한 세부 사항, 즉 알고리즘과 알고리즘을 표현하는 프로그래밍 언어를 추상화하여, 데이터에 어떤 연산(operation)들을 적용할 수 있는지에 대해 정의를 해 놓은 것이다.
DS는 ADT에 정의된 operation들을 알고리즘과 특정 프로그래밍 언어를 사용해 정의한 것이다.
구조에 따라 아래와 같은 분류가 가능하다.
선형Linear :
1. stack :
LIFO
push : 스택에 원소를 집어 넣는다.
pop : 스택에서 원소를 꺼낸다.
peek : stack pointer가 가리키는 값을 확인한다.
isEmpty : 스택이 비어 있나 확인한다.
2. queue :
FIFO
enqueue : 큐에 항목을 추가
dequeue : 큐에서 항목 제거 후 반환
* isEmpty : 큐가 비어있는지 확인
3. list :
- 순서가 강제 된다. (extrinsic)
- 중복이 허용된다.
비선형Non-Linear :
1. graph
2. tree
- binary tree
- heap
위의 자료형들은 전부 세부 구현이 누락 되어 있지만, 어떻게 동작하는지에 대한 특성과 operation들이 정의 되어 있다.
