추상 데이터 타입(ADT)이란 무엇이며, 왜 구현과 분리하나요?

**추상 데이터 타입(abstract data type)**은 값들의 집합과 그 위에서 허용되는 연산을 정의하며, 코드가 아니라 순수하게 동작으로 기술됩니다. 구현은 그 동작을 실현하는 구체적인 구조(array, linked list, tree)입니다.

같은 ADT, 다른 구현

ADT "Queue":  enqueue, dequeue, peek  (FIFO 계약)

구현 A: array + 두 개의 인덱스 (ring buffer)
구현 B: head/tail 포인터를 가진 doubly linked list
둘 다 같은 계약을 지키지만, 비용 프로파일이 다름.

왜 분리하는가

# 호출 측은 내부 구현이 아니라 계약에 의존함
class Stack:
    def push(self, x): ...
    def pop(self): ...
    def peek(self): ...
# 내부적으로 list를 linked list로 교체해도 — 호출 측은 절대 바뀌지 않음.

흔한 ADT와 전형적인 구현

왜 중요한가

ADT(인터페이스)를 기준으로 프로그래밍하면 코드가 유연하게 유지됩니다. 나중에 호출 측을 깨뜨리지 않고 구현을 최적화할 수 있습니다.

또한 추론을 날카롭게 만듭니다. 먼저 어떤 동작이 필요한지 결정한 뒤, 그것을 제공하는 가장 저렴한 구조를 고르게 됩니다.