우선순위 큐
큐나 스택과 비슷한 자료형이지만
각 원소들은 우선순위를 갖고 있다.
우선순위 큐에서, 높은 우선순위를 가진 원소는
낮은 우선순위를 가진 원소보다 먼저 처리된다.
만약 두 원소가 같은 우선순위를 가진다면 그것들은
큐에서 그것들의 순서에 의해 처리된다.
스택 : 원소들은 후입선출(LIFO) 순으로 처리
큐 : 원소들은 선입선출(FIFO) 순으로 처리
내용 출처 - 위키백과 -
수정자 및 타입 | 메서드 설명 |
bollean | public boolean add(E e) 지정한 요소를 우선순위 큐에 삽입 Parameters : 추가할 요소 Returns : true Throws : ClassCastException : 지정된 요소가 우선순위 큐에 있는 요소와 비교할 수 없을 때 NullPointerException : 지정된 요소가 null인 경우 |
boolean | public boolean offer(E e) 지정한 요소를 우선순위 큐에 삽입 Parameters : 추가할 요소 Returns : true Throws : ClassCastException : 지정된 요소가 우선순위 큐에 있는 요소와 비교할 수 없을 때 NullPointerException : 지정된 요소가 null인 경우 |
E | public E peek() 이 큐의 맨앞을 검색하지만 제거X, 큐가 비어있으면 null을 반환 Returns : 이 큐의 맨앞, 큐가 비어 있을 경우 null |
boolean | public boolean remove(Object o) 이 큐에 o.equals(e)와 같은 요소가 하나 이상 있는 경우 제거 Parameters : 이 큐에서 제거할 요소(있는 경우) Returns : 메서드의 호출로 큐가 변경된 경우 true |
boolean | public boolean contains(Object o) 이 큐에 o.equals(e)와 같은 요소가 하나 이상 포함된 경우에만 true를 반환 Parameters : 이 큐에 포함되어 있는지 확인할 object Returns : 이 큐에 지정된 요소가 포함된 경우 true |
Object[] | public Object[] to Array() 이 큐의 모든 요소를 포함하는 배열로 반환, 그 요소들은 특별한 순서가 없다 이 매서드는 새로운 배열을 할당해야 함 반환된 배열은 자유롭게 수정가능 Returns : 이 큐의 모든 element를 포함하는 배열 |
<T> T[] | public <T> T[] toArray(T[] a) 이 큐의 모든 element를 포함하는 배열을 반환 반환되는 배열의 런타임 타입은 지정된 배열의 런타임 타입 반환된 배열의 요소는 특별한 순서가 없다 " 큐size > 배열 size " 일경우 배열의 남는 공간의 요소는 null로 설정됨 Parameters : 큐의 요소가 충분히 큰 경우 저장할 배열 그렇지않다면, 동일한 런타임 타입의 새 배열을 할당 Returns : 이 큐의 모든 요소를 포함하는 배열 Throws : ArrayStoreException : 지정한 배열의 런타임 타입이 이 큐에 있는 모든 요소의 런타임 타입의 super 타입이 아닌 경우 NullPointerException : 지정된 요소가 null인 경우 |
Iterator<E> | public Iterator<E> iterator() 이 큐의 요소에 대해 iterator를 반환 이 iterator는 특정한 순서가 없음 Returns : 이 큐의 요소에 대한 iterator |
int | public int size() 이 컬렉션의 element 수를 반환 만약 이 컬렉션에 int범위 이상이 포함된 경우, MAX_VALUE 요소를 반환 Returns : 이 컬렉션 요소의 수 |
void | public void clear() 이 우선순위 큐의 모든 요소를 제거 반환된 뒤 큐는 비어있게 된다 |
E | public E poll() 이 큐의 맨앞을 찾아 제거하거나, 이 큐가 비어있으면 null을 반환 Returns : 이 큐의 맨앞 또는 이 큐가 비어있는 경우 null |
Comparator<? super E> | public Comparator<? super E> comparator() 큐의 객체가 생성될때 Comparator객체가 명시되었다면, 해당객체를 반환 큐의 객체가 생성될대 Comparator객체가 명시되지 않았다면, 해당클래스에 구현된 compareTo 메서드를 사용하여 자연스러운순서(natural ordering)로 정렬, 이때 comparator 메서드는 null을 반환한다. Returns : 이 큐를 정렬하는데 사용되는 comparator 또는 이 큐가 요소의 자연스러운 순서에 따라 정렬된 경우 null |
예제
add(E e), offer(E e), isEmpty(), poll()
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// PriorityQueue 생성
PriorityQueue<String> pq = new PriorityQueue<>();
// add() 메서드를 사용하여 요소 추가
pq.add("banana");
pq.add("apple");
pq.add("orange");
// offer() 메서드를 사용하여 요소 추가
pq.offer("grape");
pq.offer("kiwi");
pq.offer("melon");
// 우선순위에 따라 출력
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}
------------------------------------------------------------------------------------
apple
banana
grape
kiwi
melon
orange
Process finished with exit code 0
isEmpty() : 이 큐가 비어있을 경우 true를 반환,
비어있지 않다면 false를 반환
poll()을 수행하면 우선순위
(지정해 주지 않아서 알파벳 오름차순)
에 따라 찾아서 제거한다.
remove(Object o)
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(3);
pq.add(8);
pq.add(1);
pq.add(10);
System.out.println("PriorityQueue: " + pq);
// 큐에서 가장 우선순위가 높은 요소 제거
int removedElement = pq.remove();
System.out.println("Removed Element: " + removedElement);
System.out.println("PriorityQueue after removal: " + pq);
}
}
-------------------------------------------------------------------------
PriorityQueue: [1, 3, 8, 5, 10]
Removed Element: 1
PriorityQueue after removal: [3, 5, 8, 10]
Process finished with exit code 0
contain()
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 우선순위 큐에 요소 추가
pq.add(10);
pq.add(20);
pq.add(15);
pq.add(5);
System.out.println("pq = " + pq);
// 15가 우선순위 큐에 있는지 확인
if (pq.contains(15)) {
System.out.println("우선순위 큐에 15가 있습니다.");
} else {
System.out.println("우선순위 큐에 15가 없습니다.");
}
}
}
---------------------------------------------------------------------
pq = [5, 10, 15, 20]
우선순위 큐에 15가 있습니다.
Process finished with exit code 0
toArray()
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// 우선순위 큐 생성
PriorityQueue<Integer> queue = new PriorityQueue<>();
// 우선순위 큐에 요소 추가
queue.add(3);
queue.add(1);
queue.add(2);
// toArray() 메소드를 사용하여 Object[] 배열로 복사
Object[] arr = queue.toArray();
// Object[] 배열 출력
System.out.print("toArray() 메소드를 사용한 배열 출력: ");
for (Object o : arr) {
System.out.print(o + " ");
}
System.out.println();
}
}
----------------------------------------------------------------------------
toArray() 메소드를 사용한 배열 출력: 1 3 2
Process finished with exit code 0
Object 타입으로 반환된다.
toArray(T[] a)
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// 우선순위 큐 생성
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(2);
pq.add(8);
pq.add(1);
pq.add(9);
// 배열 생성
Integer[] arr = new Integer[4];
// toArray() 메서드 사용
arr = pq.toArray(arr);
// 배열 출력
for (Integer num : arr) {
System.out.print(num + " ");
}
}
}
---------------------------------------------------------------
1 2 8 5 9
Process finished with exit code 0
toArray()와 차이라면
반환되는 배열의 타입과 길이를 직접 지정할수 있고,
반환되는 배열이 매개변수로 전달된 배열과 같은 타입을 갖는 것이 보장된다.
우선순위큐 크기 > 주어진 배열의 크기
=> //배열생성 부분처럼 새로운 배열이 할당되 요소들을 저장한다.
우선순위큐 크기 < 주어진 배열의 크기
=> 요소들이 배열의 앞부분에 저장되고 나머지는 null로 채워진다.
iterator()
import java.util.Iterator;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// 우선순위 큐 생성
PriorityQueue<Integer> queue = new PriorityQueue<>();
// 우선순위 큐에 요소 추가
queue.offer(5);
queue.offer(3);
queue.offer(7);
queue.offer(1);
queue.offer(9);
System.out.println("queue = " + queue);
// Iterator 객체 생성
Iterator<Integer> iterator = queue.iterator();
// Iterator를 사용하여 요소 반복
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
------------------------------------------------------------------------
queue = [1, 3, 7, 5, 9]
1
3
7
5
9
Process finished with exit code 0
순서대로 offer()를 해주지 않았지만,
우선순위에 따라 Iterator가 생성된다.
size(), clear()
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// 우선순위 큐 생성
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 데이터 추가
pq.add(5);
pq.add(1);
pq.add(3);
System.out.println("pq = " + pq);
// size() 메서드 사용
System.out.println("현재 우선순위 큐의 크기: " + pq.size());
System.out.println();
// clear() 메서드 사용
pq.clear();
System.out.println("pq = " + pq);
// size() 메서드 사용
System.out.println("clear() 메서드 수행 후 우선순위 큐의 크기: " + pq.size());
}
}
----------------------------------------------------------------------------------------
pq = [1, 5, 3]
현재 우선순위 큐의 크기: 3
pq = []
clear() 메서드 수행 후 우선순위 큐의 크기: 0
Process finished with exit code 0
comparator()
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// Integer를 저장하는 우선순위 큐 생성
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
// 큐에 값 추가
pq.add(3);
pq.add(1);
pq.add(2);
// Comparator 객체 얻기
Comparator<? super Integer> comparator = pq.comparator();
if (comparator == null) {
System.out.println("Comparator 없음");
} else {
System.out.println("Comparator 있음");
}
}
}
--------------------------------------------------------------------------------------------
Comparator 있음
Process finished with exit code 0
이부분에 Comparator가 생성되었기 때문에
Comparator가 있다고 출력이 된다.
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
만약 Comparator가 없다면
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
"Comparator가 없음" 으로 출력된다.
'자바 탐구' 카테고리의 다른 글
Intellij) 테마 바꾸기 (0) | 2023.04.03 |
---|---|
인터페이스) Comparator (0) | 2023.03.21 |
인터페이스) Comparable (0) | 2023.03.18 |
자료구조) 큐 (0) | 2023.03.13 |
자료구조) 스택 (0) | 2023.03.12 |