큐(Queues) 란?
먼저 집어넣은 데이터가 가장 먼저 나오는 FIFO(First In First Out)의 구조로 데이터를 저장하는 형식
큐의 추상적 자료구조 구현
1. 배열(array)을 이용하여 구현
- python 리스트와 메서드들을 이용
2. 연결 리스트(linked list)를 이용하여 구현
- 이전 강의에서 마련한 양방향 연결 리스트 이용
연산의 정의
- size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함 (복잡도: O(1))
- isEmpty() - 현재 큐가 비어 있는지를 판단 (복잡도: O(1))
- enqueue(x) - 데이터 원소 x를 큐에 추가 (복잡도: O(1))
- dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거 (또한, 반환) (복잡도: O(n))
- peak() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음) (복잡도: O(1))
큐 (Queue)의 활용
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
- 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우
* 환형 큐 (Circular Queue): 정해진 개수의 저장 공간을 빙 돌려가며 이용
큐가 가득 차면? 더이상 원소를 넣을 수 없음 (큐 길이를 기억하고 있어야 함!!)
연산의 정의
큐와 동일하나 아래의 연산만 추가됨
- isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단
우선순위 큐 (Priority Queue)
- 큐가 FIFO (First-in First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
우선순위 큐의 구현
- 서로 다른 두 가지 방식이 가능할 듯:
- Enqueue 할 때 우선순위 순서를 유지하도록 - 이게 더 유리
- Dequeue 할 때 우선순위 높은 것을 선택
- 서로 다른 두 가지 재료를 이용할 수 있음:
- 선형 배열 이용
- 연결 리스트 이용
트리(Trees) 란?
정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조
이진 트리 (Binary Trees)
트리에 포함되는 모든 노드의 차수가 2 이하인 트리, 모든 노드는 자식이 없거나 (리프노드의 경우), 하나만 있거나, 아니면 둘 있는 세 경우 중 하나에 해당
연산의 정의
- size() - 현재 트리에 포함되어 있는 노드의 수를 구함
- depth() - 현재 트리의 깊이 (또는 높이)를 구함
- 순회(traversal)
이진 트리의 순회 (Traversal)
- 깊이 우선 순회 (depth first traversal)
- 중위 순회: left subtree -> 자기 자신 -> right subtree
- 전위 순회: 자기 자신 -> left subtree -> right subtree
- 후위 순회: left subtree -> right subtree -> 자기 자신
- 넓이 우선 순회 (Breadth First Traversal) : 수준(level)이 낮은 노드를 우선으로 방문
- 수준 (level)이 낮은 노드를 우선으로 방문
- 같은 수준의 노드들 사이에는, 부모 노드의 방문 순서에 따라 방문 + 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
단, 재귀적 (recursive) 방법은 적합하지 않음
이진 탐색 트리
모든 노드에 대해서, (중복되는 데이터 원소는 없는 것으로 가정)
- 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
- 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리
반응형
