데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 한다. ADT중 널리 쓰이는 큐, 스택,트리에 대해 알아보자
큐(Queue)
- 데이터를 집어넣을 수 있는 선형(linear) 자료형이다.
- 먼저 집어넣은 데이터가 먼저 나온다. (FIFO, First In First Out)
- 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue
- 큐는 순서대로 처리해야 하는 작업을 임시적으로 저장해주는 버퍼(buffer)로 많이 사용
쓰임
- 대기열 예) 프린터에서 인쇄 작업을 처리하는데 사용되는 대기열
- 네트워크 통신 예) 인터넷 라우터는 패킷을 수신하면 해당 패킷을 대기열에 추가하여 다음 목적지로 전송
스택(Stack)
- 큐와 같이 데이터를 집어넣을 수 있는 선형(linear)자료형이다.
- 나중에 집어넣은 데이터가 먼저 나온다. (LIFO, Last In First Out)
- 데이터를 집어 넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek
- 스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 사용
쓰임
- 함수호출 : 함수가 호출될 때마다 해당 함수의 정보가 스택에 저장되고, 함수가 반환될 때 스택에서 해당정보가 제거된다. 이를 통해 프로그램은 함수의 실행 흐름을 추적할 수 있다.
- 웹 브라우저의 뒤로가기 기능 : 각 방문한 웹 페이지의 URL은 스택에 저장되고, 뒤로가기 버튼을 클릭할 때마다 스택에서 해당 URL이 제거되어 이전 페이지로 이동한다.
따라서 큐와 스텍은 둘 다 데이터를 저장하고 꺼내는 자료구조이지만,
저장과 꺼내는 방식이 다르기 때문에 언제 사용하는지에 따라 선택적으로 사용한다.
트리(Tree)
용어정리
| 노드(Node) | 트리 안에 있는 각 항목 |
| 자식 노드(Child) | 노드는 여러 자식 노드를 가질 수 있다. |
| 부모 노드 (Parent) | 자식 노드의 부모 노드 |
| 뿌리 노드(Root) | 트리의 가장 상층부에 있는 노드 |
| 잎 노드(Leaf) | 자식 노드가 없는 노드 |
| 조상 노드(Ancestor) | 노드 A의 자식을 따라 내려갔을 때 노드 B에 도달할 수 있다면 노드 A를 B의 조상 노드라고 부른다. |
| 자손 노드(Descendant) | 노드 A가 노드B의 조상 노드일 때 노드B를 노드A의 자손노드라고 부른다. |
| 형제 노드(Sibling) | 같은 부모를 갖는 다른 노드를 보고 형제 노드라고 부른다. |
- 트리는 계층 구조를 나타내기 위해, 계층 구조를 통해 효율을 높이고자 할 때 사용한다.
쓰임
- 파일시스템 : root 디렉토리부터 하위 디렉토리와 파일들이 계층적으로 연결
- HTML문서 : <html>요소 아래로 하위 요소들이 계층적으로 연결
- 조직도 : ceo 노드를 시작으로 하위 부서 노드와 직원 노드들이 계층적으로 연결
'Algorithm > 개념정리' 카테고리의 다른 글
| DFS(Depth First Search) (2) | 2023.04.25 |
|---|---|
| 정렬에 관하여 (0) | 2023.04.22 |
| 메모이제이션 (피보나치, 타일링) (2) | 2023.04.20 |
