추상 자료형(Abstract Data Type, ADT)란 무엇인가?

추상 자료형(Abstract Data Type)이란?

구현하고자 하는 구조에 대해 실제 구현 내용이 아닌 자료구조의 특성과 어떤 행동을 하는지 설명하는 타입(혹은 클래스)이다.

 

Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of values and a set of operations. The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view. 

 

구현-독립적인 관점에서 '추상적'으로 바라본다.

 

즉, 구현이 빠진 '규칙'들의 나열, 명세서라고 할 수 있다. ADT의 가장 대표적인 예로는 스택(Stack)과 큐(Queue)가 있다.

 

Abstract Data Types - GeeksforGeeks

 

스택(Stack) ADT

영어 단어 Stack이란 쌓아 올린다는 뜻이다. 영어와 마찬가지로 스택(Stack) 자료 구조는 밑바닥부터 탑을 쌓듯이 차곡차곡 데이터를 쌓아 올리는 자료 구조를 뜻한다.

 

• 같은 크기의 자료를 정해진 하나의 방향으로만 입력, 저장, 삭제가 가능하다.
• 스택 구조의 제일 윗부분을 가리켜 top이라고 하며, 실제로는 가장 최근에 들어온 데이터를 가리킨다.
• 스택의 자료를 빼낼 때도 탑을 가장 위층에서부터 하나씩 제거하듯이, 입력이 들어왔던 방향으로 데이터가 리턴된다.
• 이때, top은 자료가 리턴되고 삭제된 그 바로 직전 데이터를 가리키게 된다.
• 결론적으로, 후입선출(Last In First Out, LIFO) 구조로 가장 마지막에 들어온 데이터가 가장 먼저 리턴된다.

 

Clear() - stack에서 개체를 모두 제거

Contain(T) - stack에 요소가 있는지 여부를 확인

Peek() - stack 최상단 데이터를 삭제하지 않고 해당 데이터를 반환하는 함수

Pop() - stack 최상단 데이터를 삭제하고 해당 데이터를 반환하는 함수

Push(T) - stack 최상단에 데이터를 입력하는 함수

 

큐(Queue) ADT

영어 단어 Queue의 의미는 줄, 줄을 서서 기다리는 것을 의미한다. 이런 영어 뜻과 마찬가지로 큐(Queue) 자료구조는 버스를 기다리는 줄 또는 파이프와 같이 양 방향에서 입력과 출력이 진행되는 자료구조를 뜻한다.

 

• 큐는 양방향의 입구로 한쪽에서는 데이터의 입력만이 이루어지고 다른 쪽에서는 데이터의 출력만 이루어진다.
• 가장 먼저 입력된 데이터를 가리켜 front라고 하며, 이는 삭제 연산(Deqeue)만이 수행되는 곳이다.
• 가장 최근에 입력된 데이터를 가르키는 것은 rear라고 하며, 이는 삽입 연산(Enqueue)만이 수행되는 곳이다.
• 결론적으로, 선입선출(First In First Out) 구조로 가장 먼저 들어온 데이터가 가장 먼저 리턴, 출력된다는 뜻이다.

 

Clear() - queue에서 개체를 모두 제거

Contain(T) - queue에 요소가 있는지 여부를 확인

Enqueue(T) - queue의 최끝단에 데이터를 삽입

Dequeue() - queue의 제일 앞쪽 데이터를 삭제하고 해당 데이터를 반환

Peek() - queue의 제일 앞쪽 데이터를 삭제하지 않고 해당 데이터를 반환

 

추상 자료형(Abstract Data Type) vs 구체 자료형(Concrete Data Type)

지금까지 스택과 큐에 대한 설명은 ADT로써 스택과 큐를 설명한 것이다. 즉 어떻게 구현하는지에 대한 실제 방법이 아닌 각각의 행동에 대해서 설명한 것이다. 여기서 실제 구현이 추가된다면 CDT로써 스택과 큐를 설명하게 되는 것이다. 

 

인터페이스 - ADT

인터페이스를 구현한 실제 클래스 - CDT

 

 

참고 사이트

[자료구조] 추상 자료형(Abstract Data Type, ADT)이란? (feat. 스택 & 큐)

What are ADTs? (Abstract Data Types)