우선순위 대기열 자바

때때로 특정 순서로 대기열의 항목을 처리해야 합니다. 우선 순위 큐는 작업을 수행하는 데이터 구조입니다. Java 우선 순위 큐는 "일반\ 큐와 다릅니다. "선입선출\ 대신 우선순위에 따라 항목을 검색합니다.

우선순위 대기열 자바

Java PriorityQueue 생성자

PriorityQueue() - 기본 초기 용량(예: 11)으로 PriorityQueue를 생성합니다.
PriorityQueue(Collection c) - 지정된 컬렉션의 요소로 PriorityQueue를 생성합니다.
PriorityQueue(int initialCapacity) - 지정된 초기 용량으로 PriorityQueue 생성
PriorityQueue(int initialCapacity, Comparator comparator) - 제공된 초기 용량으로 PriorityQueue를 생성하고 해당 요소의 순서는 지정된 비교기에 따릅니다.
PriorityQueue(PriorityQueue c) - 지정된 우선 순위 대기열의 요소를 포함하는 PriorityQueue를 생성합니다.
PriorityQueue(SortedSet c) - 지정된 정렬 세트의 요소를 포함하는 PriorityQueue를 생성합니다.

Priority Queue 요소는 생성하는 동안 Comparator를 제공하지 않는 한 자연 순서대로 정렬됩니다. 요소는 기본적으로 오름차순으로 정렬되므로 큐의 헤드는 우선 순위가 가장 낮은 요소입니다. 동시에 머리가 될 수 있는 두 가지 요소가 있다면, 이런 종류의 관계는 임의로 끊어집니다.

Java PriorityQueue 예제

다양한 작업을 포함하는 PriorityQueue를 생성해 보겠습니다.

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

이렇게 하면 String의 자연스러운 순서로 정렬되는 작업의 PriorityQueue가 생성됩니다. 자연 순서의 역순으로 작업을 정렬하는 또 다른 PriorityQueue를 생성해 보겠습니다. 따라서 Comparator를 전달해야 합니다.

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

자바 PriorityQueue 메서드

이제 PriorityQueue에 사용할 수 있는 모든 메서드를 살펴보고 사용하겠습니다.

Boolean add(E e) - This method inserts the specified element in the queue. We have already added 5 tasks in our queue using this method.
Comparator comparator() - This method returns the Comparator used to order the elements in this queue. It returns null if no comparator was specified and the queue is sorted according to the natural ordering of its elements. So, if we do:
```
System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());
```
The output will be:
```
null
java.util.Collections$ReverseComparator@15db9742
```
boolean contains(Object o) - Returns true if the queue contains the specified element. Let’s check if “task3” belongs to the Priority queue tasks:
```
System.out.println(tasks.contains("task3"));
```
This prints:
```
true
```
boolean offer(E e) - Just like the add() method, this method also adds an element to the queue. The offer() and add() methods are actually a bit different for capacity constrained queues, but in case of PriorityQueue, both are same. Unlike add(), offer() does not throw an exception even if it fails to add the element in the queue.
E peek() - Retrieves the head of this queue, or returns null if this queue is empty. In other words, it returns the element with highest priority. So the following code:
```
System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());
```
Gives us:
```
task1
task5
```

E poll() - This method also retrieves the head of the queue(element with highest priority), or returns null if the queue is empty. But unlike peek(), it also removes the element. So, if we call poll():

System.out.println(“Poll on tasks: ”+tasks.poll());
System.out.println(“Poll on reverseTasks: ”+reverseTasks.poll());

And then peek:

System.out.println(“Peek on tasks: ”+tasks.peek());
System.out.println(“Peek on reverseTasks: ”+reverseTasks.peek());

We’ll have the following outptut:

Poll on tasks: task1
Poll on reverseTasks: task5
Peek on tasks: task2
Peek on reverseTasks: task4

int size() - Returns the number of elements in the queue.
boolean remove(Object o) - Removes the specified element from the queue, if it’s present. If two same elements are present, it only removes one of them.
Object[] toArray() - Returns an array containing all the elements in the queue.
T[] toArray(T[] a) - Returns an array containing all the elements in the queue, and the type of the returned array is that of the specified array.
Iterator iterator() - Returns an iterator for the queue.
void clear() - Removes all of the elements from the queue.

이 외에도 PriorityQueue는 Collection 및 Object 클래스에서 메소드를 상속합니다.

Java PriorityQueue 시간 복잡도

enqueing 및 dequeing 방법의 경우 시간 복잡도는 O(log(n))입니다.
remove(Object) 및 contains(Object) 메서드의 경우 시간 복잡도는 선형입니다.
검색 방법의 경우 일정한 시간 복잡도를 가집니다.

이 우선 순위 큐 구현은 스레드로부터 안전하지 않습니다. 따라서 동기화된 액세스가 필요한 경우 API Doc을 사용해야 합니다.