[자료구조] ADT(Abstract Data Type)란?: 배열, 스택, 큐, 집합, 맵, 트리, 우선순위 큐의 ADT와 자바에서 구현한 자료구조

반응형

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 

💋 ADT(Abstract Data Type)

✔️ 개념

ADT(추상 데이터 타입)는 데이터의 논리적 모델이다.

자료구조를 추상적(수학적)으로 정의하며, 컴퓨터에서 구체적으로 구현하는 방법은 정의하지 않고, 해당 모델이 제공해야 하는 주요 동작에 대해서만 정의한다. 

 

ADT는 데이터와 연산에 대한 명세를 제공하면서 내부 구현은 숨기고, 사용자에게는 데이터와 연산의 인터페이스만 제공한다. ⇒ 자료구조의 추상화!

 

 

학습할 때, 추상화와 구현을 분리해서 생각하는 것이 좋다.

 

✔️ 예시를 통한 설명

 

Array의 ADT에 대해서 살펴보자!

 

 

<index, value></index,> 의 집합이 Array ADT이다.

주요 기능들만 정의해 놓았는데, 기본적으로 배열을 만들고, 인덱스 기반으로 아이템을 찾고, 인덱스 기반으로 아이템을 저장할 수 있다면 Array ADT를 만족한다.

int[] 와 같은 개념들은 Array ADT를 구현한 구현체이다.

 

 

✔️ 종류

ADT의 종류로는 리스트, 스택, 큐, 집합 등이 있다.

 

예를 들어, 리스트 ADT는 데이터의 순서 있는 모음을 나타내고, 요소 추가, 삭제, 검색 등의 연산을 정의한다. 하지만 ADT로의 리스트는 단지 추상화된 개념일 뿐, 리스트의 실제 구현은 프로그래밍 언어별로 매우 다양하다.

 

 

종류에 대해 간단히 살펴보자!

 

 

 

1. 배열 (Array) ADT
   • 설명: 순서대로 나열된 항목들의 집합으로, 각 항목은 고유한 인덱스를 가지며, 인덱스를 통해 항목에 접근 가능한 자료구조.
   • 자바에서의 구현: Java에서는 java.util.ArrayList나 기본 배열을 사용하여 배열 ADT를 구현할 수 있습니다.
2. 스택 (Stack) ADT
   • 설명: 후입선출(LIFO, Last In First Out) 원칙에 따라 데이터를 저장하고 접근하는 자료구조로, 데이터는 맨 위에만 추가 또는 삭제됨.
   • 자바에서의 구현: java.util.Stack, java.util.Deque 
3. 큐 (Queue) ADT
   • 설명: 선입선출(FIFO, First In First Out) 원칙에 따라 데이터를 저장하고 접근하는 자료구조로, 데이터는 맨 뒤에 추가되고 맨 앞에서 제거됨.
   • 자바에서의 구현:  java.util.LinkedList, java.util.ArrayDeque 
4. 집합 (Set) ADT
   • 설명: 고유한 원소들로 이루어진 컬렉션으로, 중복된 원소를 허용하지 않는 자료구조.
   • 자바에서의 구현: java.util.HashSet, java.util.TreeSet 
5. 맵 (Map) ADT
   • 설명: 키-값 쌍으로 이루어진 자료구조로, 각 키는 고유하며, 키를 통해 연관된 값을 찾을 수 있음.
   • 자바에서의 구현: java.util.HashMap, java.util.TreeMap 
6. 트리 (Tree) ADT
   • 설명: 계층적인 구조로 이루어진 자료구조로, 노드들이 트리 구조를 형성하며 부모-자식 관계가 있음.
   • 자바에서의 구현: java.util.TreeMap, java.util.TreeSet 등 (직접 구현이 필요하다면 TreeNode 등을 사용하여 트리를 구현할 수 있음)
7. 우선순위 큐 (Priority Queue) ADT
   • 설명: 각 요소에 우선순위가 지정된 자료구조로, 가장 높은 우선순위를 가진 요소가 먼저 나오는 큐.
   • 자바에서의 구현: java.util.PriorityQueue 

 

 

 

💋 참고자료

• https://www.geeksforgeeks.org/abstract-data-types/

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!