추상자료형(Abstract Data Types, ADT)란?

추상자료형이란?

데이터와 그 데이터를 조작하는 함수들만 정의하고, 내부 구현은 숨기는 개념.
이를 통해 데이터 구조를 보다 추상적이고 일반적으로 다룰 수 있다.

ADT가 나온 이유

1. 구현 방식에 상관없이 일관된 사용 가능

• ADT는 "무엇을 할 것인가"만 정의하고, "어떻게 할 것인가"는 숨긴다.
• Ex) Stack을 사용할 때 내부적으로 배열로 구현되든, 연결 리스트로 구현되든 상관없이 push(), pop()을 사용하면 된다.
• 즉, 사용자가 내부 구현을 몰라도 일관된 방식으로 사용 가능

2. 코드 재사용성과 유지보수성 증가

• 만약 추상자료형 없이 직접 자료구조를 만들어야 한다면, 매번 다른 방식으로 구현될 수 있다.
• 자료구조형을 사용하면, 인터페이스만 정의하고 구현을 바꿔도 기존 코드와 호환 가능
• Ex) Queue 를 배열로 구현했다가 연결리스트로 바꿔도 사용하는 코드(enqueue(),dequeue())는 변하지 않는다.

3. 알고리즘과 자료구조를 분리하여 논리적으로 정리

• 추상자료형이 없으면, 자료구조(데이터 저장 방식)와 알고리즘(데이터 처리 방식)이 섞여서 복잡해 질수 있다.
• 추상자료형을 사용하면 이 데이터 구조가 제공하는 기능이 무엇인지 를 명확하게 정의할 수 있다.

어려운것 같지만, 핵심적으로는 사용자들이 쓰기 편하게 하려고 만들어 놓은 것이라고 이해하면 될 것 같다.
개발자가 자료구조를 직접 구현할 필요 없이 이미 만들어진(표준화된) ADT 기능을 사용하면 더 편하다.

아래에서 알아보겠지만, Stack은 추상 자료형(ADT) 중 하나로, 이를 통해 ADT 개념을 살펴보면 다음과 같다.

• Stack은 후입선출(LIFO,Last In First Out) 원칙을 따른다.
• Stack이 제공하는 기능

	push(x)   -> 값을 삽입
    pop()     -> 값을 제거하고 반환
    peek()    -> 최상위 값만 반환(제거 X)
    isEmpty() -> 비어있는지 확인

• 사용자는 push()가 내부적으로 배열을 사용하는지, 연결 리스트를 사용하는지 몰라도 되고, 그냥 push(10),push(20)하면 값이 쌓이는 것만 이해하면 된다.

추상자료형의 종류와 기능

리스트(List)

✅ 특징

• 순서가 있는 데이터 집합
• 중복 허용, 인덱스를 이용해 접근 가능
  

✅ 기능

insert(index, value)  -> 특정 위치에 값 삽입
delete(index)         -> 특정 위치의 값 삭제
get(index)            -> 특정 위치의 값 가져오기
size()                -> 리스트 크기 반환

✅ 활용예시

• 동적 배열(ArrayList), 연결 리스트(LinkedList) 등으로 구현 가능
• ArrayList<Integer> list = new ArrayList<>();
• 웹페이지 방문 기록 (뒤로/앞으로 이동)
• 음악 플레이리스트(순서대로 재생

스택(Stack)

✅ 특징

• 후입선출(LIFO, Last In First Out) 구조
• 마지막에 넣은 데이터가 먼저 나감

✅ 기능

push(value)  -> 값을 삽입
pop()        -> 값을 제거하고 반환
peek()       -> 최상위 값만 반환(제거 X)
isEmpty()    -> 비어있는지 확인

✅ 활용 예시

• 배열(Stack) OR 연결 리스트로 구현 가능
• Stack<Integer> stack = new Stack<>();
• 웹 브라우저 뒤로가기
• 함수 호출 스택(재귀 호출)
• 괄호 검사( (),{},[] 올바른지 확인)

큐(Queue)

✅ 특징

• 선입선출(FIFO, First In First Out) 구조
• 먼저 들어온 데이터가 먼저 나감
  ✅ 기능:

enqueue(value)  -> 값 삽입
dequeue()       -> 값 제거 및 반환
peek()          -> 맨 앞 값 조회 (제거 X)
isEmpty()       -> 비어있는지 확인

✅ 활용 예시

• 배열(Queue) 또는 연결 리스트로 구현 가능
  -Queue<Integer> queue = new LinkedList<>();
• 프린터 대기열 (문서 인쇄 순서대로 처리)
• 프로세스 스케줄링 (CPU 태스크 실행 순서)
• 메시지 큐 (이벤트 처리 시스템)

덱(Deque, Double-ended Queue)

✅ 특징

• 양쪽에서 삽입과 삭제가 가능한 큐

✅ 기능

addFront(value)  -> 앞쪽에 값 추가
addRear(value)   -> 뒤쪽에 값 추가
removeFront()    -> 앞쪽 값 제거
removeRear()     -> 뒤쪽 값 제거

✅ 활용 예시

• 이중 연결 리스트(Doubly Linked List)로 구현 가능
• Deque<Integer> deque = new LinkedList<>();
• 웹 브라우저 방문 기록 (앞뒤 이동)
• 슬라이딩 윈도우 알고리즘 (최대/최소 값 구하기)
• 캐시(LRU Cache)

우선순위 큐(Priority Queue)

✅ 특징

• 우선순위가 높은 데이터가 먼저 처리됨
  ✅ 기능

insert(value, priority)  -> 값 삽입 (우선순위와 함께)
deleteMax() / deleteMin() -> 가장 높은/낮은 우선순위 값 제거
peek()                    -> 우선순위가 가장 높은 값 조회

✅ 활용 예시

• 힙(Heap)으로 구현 가능
• PriorityQueue<Integer> pq = new PriorityQueue<>();
• 운영체제 프로세스 스케줄링 (높은 우선순위 작업 먼저 실행)
• 네트워크 패킷 스케줄링 (긴급 데이터 먼저 전송)
• 다익스트라 알고리즘 (최단 경로 탐색)

집합(Set)

✅ 특징

• 중복을 허용하지 않음
• 순서가 중요하지 않음
  ✅ 기능

add(value)          -> 값 추가
remove(value)       -> 값 제거
contains(value)     -> 값 포함 여부 확인
union(set2)         -> 합집합
intersection(set2)  -> 교집합
difference(set2)    -> 차집합

✅ 활용 예시

• 해시 테이블(Hash Table) 또는 트리(Tree)로 구현 가능
• Set<Integer> set = new HashSet<>();
• 중복 제거 (리스트에서 중복 요소 제거)
• 회원 ID 저장 (고유한 사용자 ID 보장)
• 관계형 데이터에서 유일한 키 저장

맵(Map) 또는 딕셔너리(Dictionary)

✅ 특징

• 키(Key)와 값(Value)의 쌍으로 이루어진 자료구조
• 키를 이용해 값을 빠르게 검색 가능
  ✅ 기능

plaintext
put(key, value)    -> 키-값 추가
get(key)           -> 키에 해당하는 값 반환
remove(key)        -> 특정 키 제거
containsKey(key)   -> 키 포함 여부 확인

✅ 활용 예시

• 해시 테이블(Hash Table) 또는 트리(Tree)로 구현 가능
• Map<String, Integer> map = new HashMap<>();
• 데이터베이스 인덱스 (키-값 매핑)
• 캐시(Cache) 저장 (빠른 데이터 접근)
• JSON 데이터 파싱 (키-값 형태의 데이터 저장)