[자료구조] 추상자료형(ADT, Abstract Data Type)과 자료구조(Data Structure)

 

추상자료형 (ADT, Abstract Data Type)

 

• 프로그래밍에서 “superType”이라고 불린다(인터페이스와 추상클래스처럼 파생된 하위형식에 자신의 특성을 제공함)
• 기본 동작(basic behavior)만을 정의한다(실제로 어떻게 구현되는지에 대한 세부사항은 제외하고 해당 데이터 타입이 제공해야 하는 기본 동작만을 정의한다)
• 종합해보면 추상자료형(ADT)은 자료구조를 위한 설계도라고 볼 수 있다.

 

종류

대표적인 추상자료형(ADT)은 스택(STACK)과 큐( QUEUE)를 들 수 있다. 이들은 데이터를 조직화하고 특정 동작만을 수행하기 위한 추상적인 모델을 제공한다.

 

스택(Stack)

Last In, First Out (LIFO) 방식을 따르는 자료구조로, 마지막에 추가된 항목이 가장 먼저 제거되는 특징이 있다.스택은 주로 후입선출(Last In, First Out)의 원리에 따라 데이터를 저장하고 검색하는 데 사용되며. 기본 동작으로는 push(데이터 추가)와 pop(데이터 삭제)이 있다.

가장 마지막에 추가된 항목이 가장 먼저 제거되었다. 접시를 쌓아놓고 제거하는 것과 비슷한 원리

큐(Queue)

큐는 First In, First Out (FIFO) 방식을 따르는 자료구조로, 먼저 추가된 항목이 먼저 제거되는 특징이 있다. 큐는 주로 선입선출(First In, First Out)의 원리에 따라 데이터를 저장하고 처리하는 데 사용되며, 기본 동작으로는 enqueue(데이터 추가)와 dequeue(데이터 삭제)가 있다.

가장 먼저 추가된 항목이 가장 먼저 제거되었다. 사람들이 줄을 서서 기다리는 형태와 비슷한 원리

 

 

자료구조(Data Structure)

 

스택(stack)과 큐(queue)의 추상적인 형태를 이용하여 array나 list 등을 이용해 실제로 구현하는 작업을 자료구조(data structure)라고 한다.

자료구조의 목적은 시간복잡도를 O(1)로 실행시키는 것에 있다. O(1)은 상수 시간 복잡도를 나타내며 입력의 크기가 증가하더라도 시간이 변하지 않는다는 것을 나타낸다.

O(1)은 알고리즘의 효율성 측면에서 매우 우수한 경우로 간주된다. 상수 시간 복잡도를 갖는 알고리즘은 입력이 어떻게 변하든 실행 시간이 일정하므로, 매우 빠른 알고리즘이라고 할 수 있으며 자료구조는 이를 목표로 두고 설계를 하고 있다.

 

 

 

 

추상자료형(ADT) VS 자료구조(Data Structure) 

추상자료형	자료구조
STACK / QUEUE / PRIORITY QUEUE ...	Array, List, Hash ...