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

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

구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 자료구조의 특성들과 어떤 Operations들이 있는지를 설명하는 자료구조의 한가지 형태. 즉, 일종의 '규칙'들의 나열이라고 쉽게 이해할 수 있다. ADT의 가장 대표적 예로는 스택(Stack)과 큐(Queue)가 있다. 

 

스택(Stack) 이란? 

 

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

 

▼ 스택(Stack) 의 특징

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

 

▼ 스택(Stack) 의 Methods (java)

 

Method	Description
Boolean empty()	stack이 비어있는지 확인하는 함수
peek()	stack의 최상단 데이터를 삭제하지 않고 해당 데이터 반환하는 함수
pop()	stack의 최상단 데이터를 삭제하고 해당 데이터 반환하는 함수
push(E item)	stack의 최상단 부분에 데이터를 입력하는 함수
int search(Object o)	stack의 최상단에서부터 찾고자 하는 데이터가 몇번째에 존재하는지 반환

 

+ )) Stack Underflow : 비어있는 스택에 pop()을 해 top의 값이 0보다 작아지는 경우.

+ )) Stack Overflow : 꽉 차있는 스택에 push()를 하여 스택의 최대 용량을 벗어나는 경우. 실제로 해킹에 Stack Overflow 기법을 활용하는 경우가 많다. 

 

▼ 스택(Stack) 의 활용 예시 

• 브라우저의 뒤로가기  
• 실행 취소
• 후위 표기법 계산

 

 

큐(Queue)란? 

 

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

 

▼  큐(Queue) 의 특징

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

 

 ▼ 큐(Queue) 의 Methods (java)

 

Method	Description
Boolean add(E e)	Queue의 최끝단에 데이터를 삽입하고 true 반환, 만약 Under/Overflow 발생시 예외 발생
element()	Queue의 제일 앞쪽 데이터를 삭제하지 않고 해당 데이터를 반환하는 함수
Boolean offer(E e)	Queue의 최끝단에 데이터를 삽입하고 true 반환, 만약 Under/Overflow 발생시 null/false 반환
peek()	Queue의 제일 앞쪽 데이터를 삭제하지 않고 해당 데이터를 반환하는 함수지만 큐가 비어있으면 null 반환
poll()	stQueue의 제일 앞쪽 데이터를 삭제하고 해당 데이터를 반환하는 함수지만 큐가 비어있으면 null 반환
remove()	stQueue의 제일 앞쪽 데이터를 삭제하고 해당 데이터를 반환하는 함수지만 만약 Under/Overflow 발생시 예외 발생

 

+ )) Queue Underflow : 큐가 비어 있는데, 데이터를 꺼내려고 할 때 발생. 

+ )) Queue Overflow : 큐의 크기만큼 데이터가 꽉 차있는데 추가로 데이터를 삽입할 때 발생

 

 

▼ 큐(Queue) 의 활용 예시 

• 프로세스 관리
• 윈도우 시스템 메세지 처리기
• 캐시
• 너비 우선 탐색

 

 

Abstract Data Type vs Data Structure

 

지금까지 위에서 말한 스택과 큐에대한 설명은 ADT로써 스택과 큐를 설명한 것이다. 즉 어떻게 구현하는지에 대한 방법에 대한 언급 없이, 단순히 각각의 특징들을 설명한 것이다. 여기서 실제로 어떻게 구현하는지가 추가되면 DS로써 스택과 큐를 설명하게 되는 것이다. 결국 큐와 스택이란 것은 Array 또는 Linked List에 규칙을 설정한 모습이기 때문이다. 

추가적인 예로 Java애 빗대어 설명하자면,

 

java  - interface  -> ADT

          - class  -> DS 

 

자바의 인터페이스는 ADT라고 할 수 있으며 이를 실제로 구현한 class를 DS라고 볼 수 있다는 것이다.  이렇듯 ADT에 대한 이해도는 실무에서 설계작업할 때, 의사소통적인 면에서 중요하므로 꼭 개념을 이해하는 것이 중요하다.  

 

ex) 스택이 어쩌고 저쩌고 -> ADT적 관점 

ex) 그래서 스택을 어떤 구현체를 써서 구현했어 -> DS적 관점