Queue 인터페이스
이전까지 List인터페이스의 구현체들을 살펴보았는데, 이번 포스팅부터는 Queue 인터페이스와 구현체들에 대해 다루어보겠습니다.
이러한 큐의 기본적인 특징은 선입선출(First-In-First-Out) 구조를 가집니다. 즉 처음 들어온 원소가 가장 먼저 나가게 됩니다.
Queue 인터페이스 구현체에는 List 인터페이스 또한 상속받는 LinkedList, 우선순위큐, Deque 등이 있습니다.
Heap
이후 배우게 될 우선순위 큐는 Heap이라는 자료구조를 이용하여 구현됩니다.그렇기에 우선 Heap 자료구조 기본적으로 어떻게 구현되고, 동작하는지 알아본 후, 우선순위큐에 대해 살펴보겠습니다.
힙은 최솟값 또는 최대값을 빠르게 찾아내기 위해 완전 이진트리 형태로 만들어진 자료구조입니다.
위 문장에서 중요한 키워드를 뽑아보자면, 최솟값 & 최대값 & 빠르게 & 완전이진 트리입니다.
이러한 키워드들을 이해하기 위해서는 우선 완전 이진 트리에 대한 이해가 필요합니다!
우선 기본적인 트리에 대해 잠시 짚고 가겠습니다
부모 노드(parent node) : 자기 자신(노드)과 연결된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B)
자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H)
루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다. 위 이미지에선 녹색이 루트노드다.
단말 노드(leaf node) : 리프 노드라고도 불리며 자식 노드가 없는 노드를 의미한다. 위 이미지에서 주황색 노드가 단말노드다.
내부 노드(internal node) : 단말 노드가 아닌 노드
형제 노드(sibling node) : 부모가 같은 노드를 말한다. (ex. D, E, F는 모두 부모노드가 B이므로 D, E, F는 형제노드다.)
깊이(depth) : 특정 노드에 도달하기 위해 거쳐가야 하는 '간선의 개수'를 의미 (ex. F의 깊이 : A→B→F 이므로 깊이는 2가 됨)
레벨(level) : 특정 깊이에 있는 노드들의 집합을 말하며, 구현하는 사람에 따라 0 또는 1부터 시작한다. (ex. D, E, F, G, H)
차수(degree) : 특정 노드가 하위(자식) 노드와 연결 된 개수 (ex. B의 차수 = 3 {D, E, F} ), 즉 자식의 개수
그리고 위 트리구조에서 모든 노드의 최대 차수를 2로 제한한 것을 이진트리라고 합니다. 위의 노드 중 B노드를 보면 자식을 3개 가지고 있죠?? 이는 이진트리가 아닌 것입니다!
이진트리 경우 다음과 같은 형태를 보입니다.
그렇다면 완전 이진트리(Complete binary tree)에서 완전?이라는 것은 무엇일까요??
완전 이진트리란 마지막 레벨을 제외한 모든 노드가 채워져 있으면서 모든 노드가 왼쪽부터 채워져 있어야 합니다. 즉 위의 이진트리의 경우 I가 D의 자식이 아니므로 완전 이진트리라고 볼 수 없습니다.
즉 이진트리 이면서 위의 두 조건을 만족해야 합니다.
그리고 완전 이진트리에서 마지막 레벨을 제외한 모든 노드는 두 개의 자식 노드를 갖는다는 조건을 추가하면 포화이진트리(perfect binary tree)가 됩니다.
그렇다면 Heap은 어떻게 구현되어 있기에, 최댓값 혹은 최솟값을 빠르게 찾아낼 수 있을까요??
예를 들어 리스트에 값을 넣었다가 뺄 때, 우선순위가 높은 것부터 빼내려고 한다면 대개 정렬을 떠올리게 됩니다.
쉽게 생각해서 숫자가 낮을수록 우선순위가 높다고 하면, 매번 새 요소가 들어올 때마다 이미 리스트에 있던 원소들과 비교를 하고 정렬해야 합니다.
위와 같은 방식을 비효율적이기에, 효율을 개선하기 위해 부모 노드는 항상 자식노드보다 우선순위가 높다는 조건을 붙이게 됩니다.
즉 모든 요소들을 고려하여 우선순위를 정할 필요 없이, 부모 노드는 자식노드보다 항상 우선순위가 높다는 조건만 만족시키며 완전 이진트리 형태로 채워나가는 것입니다.
위 조건을 조금만 돌려서 생각해 보면, 루트 노드란 항상 우선순위가 가장 높은 노드라는 것입니다. 이러한 원리로 인해 최댓값 혹은 최솟값을 빠르게 찾아낼 수 있다는 장점과 함께(시간복잡도 : O(1)) 삽입 및 삭제 연산 시에도 부모 노드가 자식 노드보다 우선순위만 높으면 되므로, 결국 트리의 깊이만큼만 비교를 하면 되기 때문에 O(logN)의 시간복잡도를 가져 매우 빠르게 수행할 수 있습니다.
그리고 위 이미지에서도 볼 수 있듯, 부모 자식 노드만의 관계만 신경 쓰고 형제간 우선순위는 고려되지 않습니다.(반 정렬 상태)
그러면 왜 형제간 대소비교가 필요 없다는 거죠?라고 한다면 이는 우선순위가 높은 순서대로 뽑는 것이 포인트입니다. 즉, 원소를 넣을 때도 우선순위가 높은 순서대로 나올 수 있도록 유지되야 하고 뽑을 때 우선순위가 높은 순서 차례대로 나오기만 하면 됩니다.
이러한 개념이 모호하다면 Heap을 직접 구현해 보시는 걸 추천드립니다!
이러한 트리는 보통 연결리스트나 배열을 활용하여 구현을 하는데, 힙을 구현할 때는 특정 인덱스에 바로 접근할 수 있는 배열이 더 효과적입니다.
배열로 힙을 구현하게 된다면 밑과 같은 특징을 가집니다.
1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2
2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 + 1
3. 부모 노드 인덱스 = 자식 노드 인덱스 / 2
PriorityQueue
우선순위 큐란 각 요소들이 각각의 우선순위를 가지고 있고, 요소들의 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조입니다.
이러한 우선 순위 큐를 구현하는 데 있어 가장 대표적인 방법은 앞서 저희가 살펴본 힙 자료구조를 활용하는 방식입니다.
각 구현 방식의 시간복잡도는 다음과 같습니다.
우선순위 큐는 값을 비교해야 하므로 null을 허용하지 않고, 비교할 수 없는 객체로는 큐를 만들 수 없습니다.
또한 내부구조가 힙(완전 이진트리)으로 구성되어 있어, add() 및 poll() 메서드 즉 추가 삭제에 O(log(n)) 시간이 걸립니다.
enqueue()
enqueue()는 우선순위 큐에 요소를 삽입하는 작업을 합니다. 시간복잡도(log N)
1. 힙 끝에 새로운 요소를 삽입합니다.
2. 부모 노드와 비교하여 힙 속성을 위배하는 경우 부모 노드와 값을 바꿉니다.
3. 힙 속성이 유지될 때까지 2의 작업을 반복합니다.
heapify()
heapify는 힙 속성을 유지하는 작업을 합니다. 위에서 아래로 내려가면서 작업을 합니다.
1. 자식 노드와 우선순위를 비교합니다.
2. 만약 자식 노드 우선순위가 높다면 왼쪽 오른쪽 자식 중 가장 우선순위가 높은 노드와 교환을 합니다.
3. 힙 속성이 유지될 때까지 1,2번 과정을 반복합니다.
dequeue()
dequeue()는 우선순위 큐에 최대 우선순위 요소를 삭제하고, 그 값을 반환하는 작업을 합니다.
삭제 작업은 다음과 같습니다.
1. 루트 노드에서 값을 추출합니다.
2. heap 마지막 요소를 루트 노드를 배치합니다.
3. 마지막 요소는 제거하고
4. 루트노드부터 heapify를 수행합니다.
Deque
Deque(Double-Ended Queue)는 양쪽으로 넣고 빼는 것이 가능한 큐를 말합니다.
이는 스택과 큐를 하나로 합쳐놓은 것과 같으며(LIFO, FIFO 특성 둘 다 가능), 스택으로 사용할 수도 있고, 큐로 사용할 수도 있습니다.
이러한 덱은 양끝 모두에서 삽입 삭제가 가능하기에 사용자에게 유연성을 제공하는 클래스입니다.
참고
지금까지 Heap, PriorityQueue,Deque에 대해 알아보았습니다!
혹시 틀린 내용이 있다면 지적 부탁드립니다. 긴글 읽어 주셔서 감사합니다 ^^
https://st-lab.tistory.com/205
https://inpa.tistory.com/entry/JCF-🧱-Collections-Framework-종류-총정리#priorityqueue_클래스
https://st-lab.tistory.com/219
'JAVA' 카테고리의 다른 글
| Collection Framework 완전 정복 5탄 - Set인터페이스 (HashSet, LinkedHashSet) (0) | 2023.05.28 |
|---|---|
| Hash, HashFunction, HashCollision 완벽 정복하기! (0) | 2023.05.26 |
| Collection Framework 정복 3탄 - LinkedList (0) | 2023.05.23 |
| Collection Framework 정복 2탄 - List 인터페이스와 ArrayList (0) | 2023.05.22 |
| Collection Framework 정복 1탄 - Collection Framework란? (0) | 2023.05.22 |
