1) 배열
2) 연결리스트
- 추가할 때 링크로 끼워넣으면 되지만, 전체와 하나하나 비교해야하는 상황도 생기기때문에 enqueue가 O(N)을 가진다
3) 힙
- 자바 내부적으로는 우선순위 큐를 힙으로 구현했음
// 연결 리스트를 이용한 우선순위 큐
// 자바 기본 PriorityQueue
import java.util.*;
public class Main {
//우선순위 큐(낮은 숫자 순)
public static void enqueue(LinkedList<Integer> list, int data) {
int idx = list.size(); //집어넣을 맨 마지막 인덱스
for (int i = 0; i < list.size(); i++) { //우선순위 큐(리스트)를 돌면서
if(list.get(i) > data){ //data보다 큰수(우선순위가 낮은 수)를 만나면 그 인덱스를 가져옴
idx = i;
break;
}
}
list.add(idx, data); //위에 인덱스에다가 data 삽입
}
public static Integer dequeue(LinkedList<Integer> list) {
if(list.size() == 0 ){
return null;
}
int data = list.get(0);
list.remove(0); //가장 첫번째 수 제거
return data; //반환
}
public static void main(String[] args) {
// 연결리스트를 이용한 우선순위 큐
System.out.println("== 연결리스트 방식의 우선순위 큐 ==");
LinkedList<Integer> pqList = new LinkedList();
enqueue(pqList, 5);
enqueue(pqList, 7);
enqueue(pqList, 3);
enqueue(pqList, 1);
enqueue(pqList, 9);
System.out.println(pqList);
System.out.println(dequeue(pqList));
System.out.println(dequeue(pqList));
System.out.println(pqList);
System.out.println();
// 자바 기본 PriorityQueue 사용
System.out.println("== 자바 기본 우선순위 큐 ==");
// 우선순위: 낮은 숫자 순
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(7);
pq.add(3);
pq.add(1);
pq.add(9);
System.out.println(Arrays.toString(pq.toArray()));
// 우선순위: 높은 숫자 순
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
pq2.add(5);
pq2.add(7);
pq2.add(3);
pq2.add(1);
pq2.add(9);
System.out.println(Arrays.toString(pq2.toArray()));
}
}
// 나이 순으로 오름차순 또는 내림차순 출력
import java.util.Arrays;
import java.util.PriorityQueue;
class Person implements Comparable<Person>{
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person o) {
//1: 변경 안함
//-1: 변경
//this.age가 추가하는 데이터
//추가하는 데이터가 더 작을 때 변경(작은 값이 위로 올라감, 오름차순)
// return this.age >= o.age? 1 : -1;
return this.name.compareTo(o.name);
//새롭게 추가하는 데이터가 더 클 때 변경(큰 값이 위로 올라감, 내림차순)
//return this.age <= o.age? 1: -1;
}
}
public class Practice1 {
public static void solution(String[] name, int[] age) {
PriorityQueue<Person> pq = new PriorityQueue<>();
for (int i = 0; i < name.length; i++) {
pq.offer(new Person(name[i], age[i]));
}
System.out.println("== 내부 힙 구조 =="); //내부구조는 꼭 우선순위대로 이루어져있지는 않다
pq.stream().forEach(x -> System.out.println(x.name + " " + x.age));
System.out.println();
System.out.println("== 실제 출력 순서 ==");
while(!pq.isEmpty()){
Person p = pq.poll(); //우선순위대로 뽑아낸다
System.out.println(p.name + " " + p.age);
}
}
public static void main(String[] args) {
String[] name = {"A", "B", "C", "D", "E"};
int[] age = {30, 20, 45, 62, 35};
solution(name, age);
//람다를 이용한 비교 방식
System.out.println();
//p1이 추가되는 데이터
PriorityQueue<Person> pq2 = new PriorityQueue<>((Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1);
for (int i = 0; i < name.length; i++) {
pq2.offer(new Person(name[i], age[i]));
}
while(!pq2.isEmpty()){
Person p = pq2.poll();
System.out.println(p.name + " " + p.age);
}
}
}
// 문자열 사전식 오름차순
import java.util.PriorityQueue;
class Person2 {
String name;
int age;
public Person2(String name, int age) {
this.name = name;
this.age = age;
}
}
public class Practice2 {
public static void solution(String[] name, int[] age) {
PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p1.name.compareTo(p2.name)); //문자열 오름차순
// PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p2.name.compareTo(p1.name)); //문자열 내림차순
//참고용
//A가 더 작기때문에 -1이 나온다
System.out.println("A".compareTo("B"));
for (int i = 0; i < name.length; i++) {
pq.offer(new Person2(name[i],age[i]));
}
while(!pq.isEmpty()){
Person2 p = pq.poll();
System.out.println(p.name + " " + p.age);
}
}
public static void main(String[] args) {
PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p1.name.compareTo(p2.name));
String[] name = {"A", "B", "C", "D", "E"};
int[] age = {30, 20, 45, 62, 35};
solution(name, age);
}
}