[자료구조] Priority Queue는 뭔가요?

Queue만 쓰면 안되나요?

Queue도 List처럼 LinkedList(조회 보다는 수정에 효율이 좋은 자료 구조), 기본 구조(FIFO)를 바탕으로 특수한 상황에 맞춰 사용할 수 있도록 추가적인 자료구조를 찾아 볼 수 있습니다.

• ArrayBlockingQueue
• LinkedBlockingQueue
• PriorityBlockingQueue
• DelayQueue
• LinkedTransferQueue
• SynchronousQueue
• ConcurrentLinkedQueue
• ...

여러가지가 있겠지만 제가 주로 사용하던 자료구조를 들고 왔습니다. -> PriorityQueue

사용 이유는 즉슨 데이터가 들어가는 순간 Queue 내부에서 기본 우선순위(작은값 >>> 큰값)를 따라 정렬이 이루어 집니다.

PriorityQueue<Integer> integerQueue = new PriorityQueue<>();

integerQueue.add(9);
integerQueue.add(2);
integerQueue.add(4);

int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();

// 2, 4, 9 순으로 출력됩니다!

배열의 크기가 고정되어 있는 경우에는 배열을 정렬해서 쉽게 처리 가능합니다.

그와 반대로 자료구조의 크기가 빈번하게 수정이 이루어질때마다 정렬하는 경우엔 PriorityQueue가 좀더 나은 선택이 될 수 있습니다.