[자료구조] Queue의 구현체 (우선순위 큐)

 

- 말하기에 앞서 Queue는 interface 형태로 Collection 클래스를 상속하고 있다 

- 자료구조 중에서 선형구조인 큐는 일반 큐와 우선순위 큐로 나뉘어진다

 

 

선형구조(Linear Structure), 큐(Queue)

💡 선형 구조

 

- 데이터를 저장하기 위한 기본적인 형태로 데이터가 일렬로 나열 되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미한다

 

💡 큐

 

- 큐는 선입선출의 특성을 가지고 있다

큐에 대해서 좀 더 자세하게 알고 싶으면 아래 포스팅을 확인하면 된다 

 

https://hyeonni.tistory.com/24

Queue란? from java

 

큐의 구현체

 

LinkedList(연결 리스트)

 

- 일단 Java에서 제공하는 Queue는 interface 형태로 연결 리스트(LinkedList)를 통해서 생성한다

- 그래서 사이즈가 가변적이고 쉽게 데이터를 삭제, 추가 할 수 있다

import java.util.Queue;
import java.util.LinkedList;
Queue<T> queue = new LinkedList<>(); // T 타입 queue 선언

 

💡연결 리스트 (LinkedList)

 

- ArrayList처럼 데이터들을 연속적으로 배열 시키지 않고 임의의 기억공간에 기억시키되 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결 시킨 구조이다

 

list

 

Priority Queue(우선순위 큐)

 

- 우선 순위 큐는 이름 처럼 큐의 성질을 가졌다

- 하지만 각 데이터가 우선순위를 가지고 있어 우선순위가 높은 순서대로 데이터를 처리를 해주는 큐이다

- 만약에 우선순위가 동일하다고 하면 그땐 순서에 의해 처리된다

 

- 우선 순위 큐는 null을 저장하면 NullPointException이 발생한다

 

- 위 사진 처럼 PriorityQueue는 저장 공간으로 배열을 사용한다 

- 그리고 각 요소를 heap(힙) 이라는 자료구조의 형태로 저장한다

- 어떤 객체의 내부 속성에 대해서 어떤 기준으로 정렬하고 싶으면 Comparable 인터페이스의 compareTo 메소드를 구현 하면 된다

Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

 

- 정렬 기준의 순서대로 poll() 하는 경우 즉, 데이터를 빼는 경우 우선순위가 높은 것 부터 나오게 된다

- 즉,  작은 숫자가 더 높은 우선순위를 갖도록 설정되어 있다 -> 작은 숫자가 먼저 추출된다

- 만약! 우선순위를 역순으로 하여 정렬하고 싶으면 아래 코드 처럼 하면 된다

Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

 

 

💡힙(heap)

 

- 최대 혹은 최솟값을 빠르게 찾기 위한 자료구조

- Heap 은 특정한 순서에 따라 정렬된 요소들을 저장하는 트리 기반의 자료구조이다

- Heap 은 일반적으로 binary heap 으로 구현되고 위 처럼 Priority Queue 의 구현에 주로 사용된다

 

 

사용법

---

선언

import java.util.PriorityQueue;

//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

 

값 추가 

priorityQueue.add(3);
priorityQueue.offer(1);
priorityQueue.add(2);

System.out.println(priorityQueue) // 출력결과 -> 1,3,2

while (!priorityQueue.isEmpty()) {
	System.out.println(priorityQueue.poll());
}

// 출력 결과 
// 1
// 2
// 3

 

- 추가 하려면 일반적인 큐의 메서드 add(), offer()를 사용하면 된다

- 위 코드를 보면 출력 결과가 다르다 큐의 내부를 보려고 System.out.println 으로 출력하면 결과가 1,3,2 가 되고 poll() 함수로 데이터를 꺼내면 출력 순서가 1, 2, 3이된다 

 

이 이유는 무엇일까? 

 

- 이유는 우선순위 큐는 힙 구조로 완전 이진 트리의 일종이다

 

아래 그림 순서를 보고 설명하겠다

- 처음에는 그림 처럼 3이 추가가 되었다

- 그리고 1이 추가 되었을때는 일단 끝에다가 추가를 한다 

그 후에 부모노드 즉, 루트 노드와 비교를 한다 

- 1이 3 보다 우선순위가 높으니 swap

- 2가 추가 되었다 이번에도 마찬가지로 제일 뒤쪽에 추가를 한다

그리고 2도 루트노드와 비교를 한다

-> 2는 1보다 우선순위가 낮으므로 교체가 되지 않고 그대로 둔다

 

이런 이유로 큐 내부에서는 print()문을 사용해 보면 [1, 3, 2]가 출력이 된다

 

이렇게 해서 우선순위 큐의 내부 데이터가 어떤식으로 추가가 되는지 알 수 있었다.

 

 

값 제거

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

 

우선순위가 가장 높은 값 출력

priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1