[자료구조] ProrityQueue(우선순위큐) - Java Collections Framework

PriorityQueue(우선순위큐)

일반적으로 Queue(큐)는 선입선출(FIFO, First In First Out)의 성격을 가지고 있는 자료구조이지만,

 

우선순위 큐는 들어오는 순서에 상관없이 우선순위가 높은 원소부터 빠져나가는 자료구조이다.

 

운영체제의 CPU 스케줄링 중 우선순위 스케줄링이 우선순위 큐를 이용한 예이다.

 

java Collections Framework에서 우선순위큐의 자세한 사용법은 아래 코드를 참조하자

package algorithm;

import java.util.*;

public class priorityQueue {
	public static void main(String[] args) {
		PriorityQueue<Integer> q = new PriorityQueue<>();
		
		// 데이터 저장 
		q.add(4);
		q.add(3);
		q.add(7);
		q.add(9);
		
        // 데이터 조회
		System.out.println(q.peek());
		
		//데이터 출력
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}

 

저장된 순서와 상관없이 데이터가 오름차순으로 출력된 것을 확인할 수 있다.

 

package algorithm;

import java.util.*;

public class priorityQueue {
	public static void main(String[] args) {
		PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
		
		// 데이터 저장 
		q.add(4);
		q.add(3);
		q.add(7);
		q.add(9);
		
        // 데이터 조회
		System.out.println(q.peek());
		
		//데이터 출력
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}

 

우선순위를 반전시키는 방법은 객체 생성 시 Collections.reverseOrder()를 사용해 정렬 기준을 반전시킨다.

 

아래는 객체의 정렬기준에 따라 우선순위 큐에 저장하고 출력하는 예제이다.

 

package algorithm;

import java.util.*;

public class priorityQueue {
	public static class Process implements Comparable<Process>{
		int time;
		int priority;
		
		Process(int time, int priority){
			this.time = time;
			this.priority = priority;
		}
		
		@Override
		public int compareTo(Process p) {
			if(this.priority < p.priority) return 1;
			else return -1;
		}
	}
	public static void main(String[] args) {
		PriorityQueue<Process> q = new PriorityQueue<>(Collections.reverseOrder());
		
		// 데이터 저장 
		q.add(new Process(1, 4));
		q.add(new Process(2, 2));
		q.add(new Process(3, 1));
		q.add(new Process(4, 6));
		
		
		//데이터 출력
		while(!q.isEmpty()) {
			Process p = q.poll();
			System.out.println("priority : " + p.priority + " time " + p.time);
		}
	}
}