[Java] Queue와 PriorityQueue 정리

Queue

• 먼저 넣은 객체가 먼저 빠져나가는 FIFO(First In First Out) 구조
• 그래프 넓이 우선 탐색(BFS)에서 사용
• 대표적인 예로 스레드풀(ExecutorService)의 작업 큐, 컴퓨터의 버퍼에 사용

• Queue 인터페이스를 구현한 대표적인 클래스는 LinkedList
• LinkedList는 List 인터페이스를 구현했기 때문에 List 컬렉션이기도 함

import java.util.LinkedList;
import java.util.Queue;
// E: 리턴타입
Queue<E> queue = new LinkedList<E>();

메소드	설명	정상 실행	실패
add	객체를 추가	true 반환	예외 발생
offer	객체를 추가	true 반환	flase 반환
remove	Dequeue	맨 앞의 객체 반환 후 삭제	예외 발생
poll	Dequeue	맨 앞의 객체 반환 후 삭제	null 반환
clear	비우기	비우기
element	Enqueue	맨 앞의 객체 반환	예외 발생
peek	Enqueue	맨 앞의 객체 반환	null 반환

 

PriorityQueue

• 높은 우선순위의 객체를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 객체는 비교가 가능한 기준이 있어야함)
• 내부 객체는 힙으로 구성되어 이진트리 구조
• 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)

import java.util.PriorityQueue;

// E: 리턴 타입
PriorityQueue<E> priorityQueue = new PriorityQueue<>(); //우선순위가 낮은 순

PriorityQueue<E> priorityQueue = new PriorityQueue<>(Collections.reverseOrder()); //우선순위가 높은 순

 

메소드는 Queue와 동일