우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)Java2022. 12. 20. 23:28@mag1c

Table of Contents

728x90

Priority Queue

기본 큐의 구조(FIFO : First In First Out)를 가지면서 데이터의 우선순위를 정해 우선순위가 높은 순서대로 나간다
우선순위 힙을 기반으로 구현된다
사용되는 생성자에 따라 자연 순서에 따라 또는 큐 생성 시 제공되는 Comparator에 따라 순서가 지정된다
데이터를 삽입할 때 우선순위의 최대, 최소를 구성하여 데이터가 빠지면 중간을 계속해서 채워넣는 방식

특징

높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다
비교할 수 없는 객체는 큐를 만들 수 없다 (비교 가능한 기준이 있어야한다)
우선순위 큐는 값을 비교해야하므로 null을 허용지 않는다
내부구조는 이진트리 힙으로 구성되어있다 (내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)이다)
AbstractQueue , AbstractCollection , Collection 및 Object클래스에서 메서드를 상속한다

선언하기

import java.util.Collections;
import java.util.PriorityQueue;

//낮은 숫자가 우선 순위인 int형 큐 선언
PriorityQueue<Integer> queue = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int형 큐 선언
PriorityQueue<Integer> queue2 = new PriorityQueue<>(Collections.reverseOrder());

같은 기능의 메서드지만 예외를 던지거나, null또는 false가 반환될 수도 있다

	예외 발생	값 리턴
추가(enqueue)	add(e)	offer(e)
삭제(dequeue)	remove()	poll()
검사(peek)	element()	peek()

추가하기

// 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생

//add, offer로 삽입
queue.add(1);
queue.add(2);
queue.offer(3);

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

Queue에 데이터를 추가 했을 때, 아래 그림과 같은 과정을 통해 즉시 정렬된다

출처 : https://coding-factory.tistory.com/603

삭제하기

// 첫번째 값을 반환하고 제거한다
// 비어있다면 null을 반환
queue.poll();

// 첫번째 값을 제거한다
// 비어있다면 예외 발생
queue.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
queue.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
queue.element();

// 초기화시킨다
queue.clear();