추상 자료형
추상 자료형(abstract data type, ADT)은 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명기한 것이다. 추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다. 비슷한 개념의 추상적 자료 구조는 각 연산의 시간 복잡도를 명기하고 있지만 추상적 자료형에서는 이것조차 명기하지 않는다.
추상 자료형은 인터페이스와 구현을 분리하여 추상화 계층을 둔 것이다. 예를 들어 전기 밥솥을 추상 자료형에 비유한다면 그 속에 들어가는 밥은 자료가 되고, 밥솥에 있는 취사, 예약취사 버튼들과 남은 시간을 표시하는 디스플레이에 어떤 내용들이 표시되어야 하는지를 명기한 것이다. 추상 자료형에서는 이것들이 어떻게 구성되는지 관심이 없고, 몇 와트의 전기를 소모하는지에 대해서도 관심이 없다.
자료에 대한 연산은 자료에 대하여 질의를 던지는 것과 자료를 변경하기 위한 연산으로 나뉜다. 유명한 자료구조인 스택에서 자료를 변경하기 위한 연산은 기본적으로 push와 pop이 있다. 여기에 자료에 대하여 질의를 던지는 연산으로 스택의 크기를 알 수 있는 size 연산, 스택이 가득차거나 비었는지를 알 수 있는 full, empty 연산이 있고, 추가적으로 pop을 하면 제거될 자료를 볼 수 있는 peek 연산 등을 정의할 수 있다. 만약 여기에 각 연산들은 모두 상수 시간 복잡도(즉, O(1))에 일어나야 한다고 명기한다면 이것은 '추상적 자료 구조'가 된다.
추상적 자료 구조
[편집]추상적 자료 구조는 이론 컴퓨터 과학 분야에서 자료에 대한 일련의 연산이 정의되며, 각각의 연산에 대한 연산 복잡도가 정의된 가상의 자료 저장 공간이다. 이는 자료 구조의 구체적인 구현 방식과는 관련이 없다.
추상적 자료 구조를 올바르게 선택하는 것은 효율적 알고리즘을 설계하고, 연산 복잡도를 추정함에 있어서 필수적이다. 반면, 구체적인 자료구조를 올바르게 선택하는 것은 알고리즘의 효과적인 구현에 중요하다.
이러한 추상화 개념은 프로그래밍 언어 이론에서의 추상 자료형(Abstract data type, ADT)과 매우 유사하다. 데이터 모델이라는 또 다른 유사한 추상화 개념은 데이터 요소 간의 상호 연관 패턴(이상하게 들리겠지만, 자료 구조의 구조 자체)을 나타낸다.
많은 추상적 자료 구조(그리고 추상 자료형)의 이름은 구체적 자료 구조의 이름과 동일하다.
추상 자료형의 예
[편집]잘 알려진 추상 자료형에는 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합 등이 있다.
내장형 추상 자료형
[편집]일부 프로그래밍 언어 사양에서는 내장된 ADT를 지원한다. 그 예로, Awk, 루아, 펄과 같은 수많은 스크립트 언어를 들 수 있으며 추상 리스트의 구현체로 간주된다.
같이 보기
[편집]외부 링크
[편집]
위키미디어 공용에 추상 자료형 관련 미디어 분류가 있습니다.
- (영어) Abstract data type in NIST Dictionary of Algorithms and Data Structures
