PriorityQueue는 우선순위에 따라 객체를 처리해야 할 때 사용됩니다. 다음과 같은 것으로 알려져 있습니다. 대기줄 선입선출(First-In-First-Out) 알고리즘을 따르지만 때로는 우선순위에 따라 대기열의 요소를 처리해야 하는 경우가 있는데, 이때 PriorityQueue가 작동하게 됩니다.
PriorityQueue는 우선순위 힙을 기반으로 합니다. 우선순위 큐의 요소는 사용되는 생성자에 따라 자연 순서에 따라 또는 큐 생성 시 제공되는 비교기에 따라 정렬됩니다.
아래 우선순위 큐에서는 최대 ASCII 값을 가진 요소가 가장 높은 우선순위를 갖습니다.
선언:
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
클래스가 구현합니다. 직렬화 가능 , 반복 가능 , 수집 , 대기줄 인터페이스.
몇 가지 우선순위 대기열의 중요 사항 다음과 같다:
- PriorityQueue는 null을 허용하지 않습니다.
- 비교할 수 없는 객체의 PriorityQueue를 생성할 수 없습니다.
- PriorityQueue는 바인딩되지 않은 대기열입니다.
- 이 큐의 헤드는 지정된 순서와 관련하여 가장 작은 요소입니다. 여러 요소가 최소 값에 연결되어 있으면 머리가 해당 요소 중 하나입니다. 연결은 임의로 끊어집니다.
- PriorityQueue는 스레드로부터 안전하지 않기 때문에 Java는 Java 멀티스레딩 환경에서 사용할 BlockingQueue 인터페이스를 구현하는 PriorityBlockingQueue 클래스를 제공합니다.
- 큐 검색 작업은 큐의 헤드에 있는 요소에 폴링, 제거, 픽 및 요소 액세스를 수행합니다.
- add 및 poll 메소드에 O(log(n)) 시간을 제공합니다.
- 이는 다음의 메소드를 상속받습니다. 추상큐 , 추상컬렉션 , 수집, 그리고 물체 수업.
생성자:
1. 우선순위큐(): 자연 순서에 따라 요소를 정렬하는 기본 초기 용량(11)을 사용하여 PriorityQueue를 생성합니다.
PriorityQueue pq = new PriorityQueue();
2. PriorityQueue(컬렉션 c): 지정된 컬렉션의 요소를 포함하는 PriorityQueue를 만듭니다.
PriorityQueue pq = new PriorityQueue(컬렉션 c);
3. PriorityQueue(intinitialCapacity) : 자연 순서에 따라 요소를 정렬하는 지정된 초기 용량을 사용하여 PriorityQueue를 생성합니다.
PriorityQueue pq = new PriorityQueue(intinitialCapacity);
4. PriorityQueue(intinitialCapacity, 비교기 비교기): 지정된 비교자에 따라 요소의 순서를 지정하는 지정된 초기 용량을 사용하여 PriorityQueue를 만듭니다.
PriorityQueue pq = new PriorityQueue(intinitialCapacity, Comparator 비교기);
5. 우선순위큐(우선순위큐c) : 지정된 우선순위 큐의 요소를 포함하는 PriorityQueue를 생성합니다.
PriorityQueue pq = new PriorityQueue(PriorityQueue c);
6. PriorityQueue(SortedSet c) : 지정된 정렬 세트의 요소를 포함하는 PriorityQueue를 생성합니다.
PriorityQueue pq = new PriorityQueue(SortedSet c);
7. PriorityQueue(비교기 비교기): 기본 초기 용량을 사용하고 지정된 비교기에 따라 요소가 정렬된 PriorityQueue를 만듭니다.
PriorityQueue pq = new PriorityQueue(비교기 c);
예:
아래 예에서는 우선순위 큐의 다음과 같은 기본 동작을 설명합니다.
SDLC
- boolean add(E 요소): 이 메소드는 지정된 요소를 이 우선순위 큐에 삽입합니다.
- public peek(): 이 메서드는 이 큐의 헤드를 검색하지만 제거하지는 않으며, 이 큐가 비어 있는 경우 null을 반환합니다.
- public poll(): 이 메소드는 이 대기열의 헤드를 검색 및 제거하거나, 이 대기열이 비어 있으면 null을 반환합니다.
자바
// Java program to demonstrate the> // working of PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue =>new> PriorityQueue();> >// Adding items to the pQueue using add()> >pQueue.add(>10>);> >pQueue.add(>20>);> >pQueue.add(>15>);> >// Printing the top element of PriorityQueue> >System.out.println(pQueue.peek());> >// Printing the top element and removing it> >// from the PriorityQueue container> >System.out.println(pQueue.poll());> >// Printing the top element again> >System.out.println(pQueue.peek());> >}> }> |
>
>산출
10 10 15>
PriorityQueue에 대한 작업
우선순위 대기열 클래스에서 자주 사용되는 몇 가지 작업을 수행하는 방법을 살펴보겠습니다.
1. 요소 추가: 우선순위 큐에 요소를 추가하려면 add() 메소드를 사용할 수 있습니다. 게재 신청서는 PriorityQueue에 유지되지 않습니다. 요소는 기본적으로 오름차순인 우선순위에 따라 저장됩니다.
자바
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >for>(>int> i=>0>;i<>3>;i++){> >pq.add(i);> >pq.add(>1>);> >}> >System.out.println(pq);> >}> }> |
>
>산출
[0, 1, 1, 1, 2, 1]>
PriorityQueue를 인쇄하여 정렬된 요소를 얻지 않습니다.
자바
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> > >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> > >System.out.println(pq);> >}> }> |
>
>산출
[For, Geeks, Geeks]>
2. 요소 제거: 우선순위 큐에서 요소를 제거하려면 제거() 메소드를 사용할 수 있습니다. 그러한 객체가 여러 개 있는 경우 해당 객체의 첫 번째 발생이 제거됩니다. 그 외에도, 헤드를 제거하고 반환하는 데에도 poll() 메서드가 사용됩니다.
자바
자바스크립트 하위 문자열 자르기
// Java program to remove elements> // from a PriorityQueue> import> java.util.*;> import> java.io.*;> public> class> PriorityQueueDemo {> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'Initial PriorityQueue '> + pq);> >// using the method> >pq.remove(>'Geeks'>);> >System.out.println(>'After Remove - '> + pq);> >System.out.println(>'Poll Method - '> + pq.poll());> >System.out.println(>'Final PriorityQueue - '> + pq);> >}> }> |
>
>산출
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. 요소에 액세스: Queue는 First In First Out 원칙을 따르기 때문에 큐의 선두에만 접근할 수 있습니다. 우선순위 큐의 요소에 액세스하려면 peek() 메서드를 사용할 수 있습니다.
자바
// Java program to access elements> // from a PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String[] args)> >{> >// Creating a priority queue> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'PriorityQueue: '> + pq);> >// Using the peek() method> >String element = pq.peek();> >System.out.println(>'Accessed Element: '> + element);> >}> }> |
>
>산출
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. PriorityQueue 반복: PriorityQueue를 반복하는 방법에는 여러 가지가 있습니다. 가장 유명한 방법은 대기열을 배열로 변환하고 for 루프를 사용하여 순회하는 것입니다. 그러나 큐에는 큐를 반복하는 데 사용할 수 있는 내장 반복자가 있습니다.
자바
// Java program to iterate elements> // to a PriorityQueue> import> java.util.*;> public> class> PriorityQueueDemo {> >// Main Method> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >Iterator iterator = pq.iterator();> >while> (iterator.hasNext()) {> >System.out.print(iterator.next() +>' '>);> >}> >}> }> |
>
>산출
For Geeks Geeks>
예:
자바
import> java.util.PriorityQueue;> public> class> PriorityQueueExample {> >public> static> void> main(String[] args) {> > >// Create a priority queue with initial capacity 10> >PriorityQueue pq =>new> PriorityQueue(>10>);> > >// Add elements to the queue> >pq.add(>3>);> >pq.add(>1>);> >pq.add(>2>);> >pq.add(>5>);> >pq.add(>4>);> > >// Print the queue> >System.out.println(>'Priority queue: '> + pq);> > >// Peek at the top element of the queue> >System.out.println(>'Peek: '> + pq.peek());> > >// Remove the top element of the queue> >pq.poll();> > >// Print the queue again> >System.out.println(>'Priority queue after removing top element: '> + pq);> > >// Check if the queue contains a specific element> >System.out.println(>'Does the queue contain 3? '> + pq.contains(>3>));> > >// Get the size of the queue> >System.out.println(>'Size of queue: '> + pq.size());> > >// Remove all elements from the queue> >pq.clear();> > >// Check if the queue is empty> >System.out.println(>'Is the queue empty? '> + pq.isEmpty());> >}> }> |
>
>산출
Priority queue: [1, 3, 2, 5, 4] Peek: 1 Priority queue after removing top element: [2, 3, 4, 5] Does the queue contain 3? true Size of queue: 4 Is the queue empty? true>
실시간 예시:
우선순위 큐(Priority Queue)는 요소가 우선순위에 따라 정렬되어 있으며, 우선순위가 가장 높은 요소가 큐의 맨 앞에 나타나는 데이터 구조입니다. 다음은 우선순위 큐를 사용할 수 있는 실제 사례입니다.
- 작업 예약 : 운영 체제에서 우선 순위 대기열은 우선 순위 수준에 따라 작업을 예약하는 데 사용됩니다. 예를 들어 중요한 시스템 업데이트와 같은 우선순위가 높은 작업은 백그라운드 백업 프로세스와 같은 우선순위가 낮은 작업보다 먼저 예약될 수 있습니다. 응급실: 병원 응급실에서는 상태의 중증도에 따라 환자를 분류하고, 심각한 상태의 환자를 먼저 치료합니다. 우선순위 대기열을 사용하여 의사와 간호사가 환자를 진료하는 순서를 관리할 수 있습니다. 네트워크 라우팅: 컴퓨터 네트워크에서 우선순위 큐는 데이터 패킷의 흐름을 관리하는 데 사용됩니다. 음성 및 비디오 데이터와 같이 우선순위가 높은 패킷은 이메일 및 파일 전송과 같이 우선순위가 낮은 데이터보다 우선순위가 부여될 수 있습니다. 교통 : 교통 관리 시스템에서는 우선순위 대기열을 사용하여 교통 흐름을 관리할 수 있습니다. 예를 들어, 구급차와 같은 긴급 차량은 목적지에 신속하게 도달할 수 있도록 다른 차량보다 우선순위가 부여될 수 있습니다. 작업 스케줄링: 작업 스케줄링 시스템에서는 우선순위 큐를 사용하여 작업이 실행되는 순서를 관리할 수 있습니다. 중요한 시스템 업데이트와 같은 우선순위가 높은 작업은 데이터 백업과 같은 우선순위가 낮은 작업보다 먼저 예약될 수 있습니다. 온라인 마켓플레이스: 온라인 마켓플레이스에서는 우선순위 대기열을 사용하여 고객에게 제품 배송을 관리할 수 있습니다. 특급 배송과 같이 우선순위가 높은 주문은 표준 배송 주문보다 우선적으로 처리될 수 있습니다.
전반적으로 우선순위 대기열은 다양한 실제 시나리오에서 우선순위 수준에 따라 작업과 리소스를 관리하는 데 유용한 데이터 구조입니다.
PriorityQueue 클래스의 메서드
| 방법 | 설명 |
|---|---|
| 추가(그리고) | 지정된 요소를 이 우선순위 큐에 삽입합니다. |
| 분명한() | 이 우선순위 큐에서 모든 요소를 제거합니다. |
| 비교기() | 이 큐에 있는 요소의 순서를 지정하는 데 사용되는 비교기를 반환하거나, 이 큐가 해당 요소의 자연스러운 순서에 따라 정렬된 경우 null을 반환합니다. |
| 포함되어 있습니까?(객체 o) | 이 큐에 지정된 요소가 포함되어 있으면 true를 반환합니다. |
| forEach?(소비자 행동) | 모든 요소가 처리되거나 작업에서 예외가 발생할 때까지 Iterable의 각 요소에 대해 지정된 작업을 수행합니다. |
| 반복자() | 이 큐의 요소에 대한 반복자를 반환합니다. |
| 제안?(E e) | 지정된 요소를 이 우선순위 큐에 삽입합니다. |
| 제거하시겠습니까?(객체 o) | 지정된 요소가 있는 경우 이 큐에서 해당 요소의 단일 인스턴스를 제거합니다. |
| RemoveAll?(컬렉션 c) | 지정된 컬렉션에도 포함되어 있는 이 컬렉션의 모든 요소를 제거합니다(선택적 작업). |
| RemoveIf?(조건자 필터) | 주어진 조건을 만족하는 이 컬렉션의 모든 요소를 제거합니다. |
| keepAll?(컬렉션 c) | 지정된 컬렉션에 포함된 이 컬렉션의 요소만 유지합니다(선택적 작업). |
| 분할기() | 이 큐의 요소에 대해 지연 바인딩 및 빠른 실패 Spliterator를 만듭니다. |
| toArray() | 이 큐의 모든 요소를 포함하는 배열을 반환합니다. |
| toArray?(T[] a) | 이 큐의 모든 요소를 포함하는 배열을 반환합니다. 반환된 배열의 런타임 유형은 지정된 배열의 런타임 유형입니다. |
클래스 java.util.AbstractQueue에 선언된 메소드
| 방법 | 설명 |
|---|---|
| addAll(컬렉션 c) | 지정된 컬렉션의 모든 요소를 이 큐에 추가합니다. |
| 요소() | 이 큐의 헤드를 검색하지만 제거하지는 않습니다. |
| 제거하다() | 이 큐의 헤드를 검색하고 제거합니다. |
클래스 java.util.AbstractCollection에 선언된 메소드
| 방법 | 설명 |
|---|---|
| containAll(컬렉션 c) | 이 컬렉션에 지정된 컬렉션의 모든 요소가 포함되어 있으면 true를 반환합니다. |
| 비었다() | 이 컬렉션에 요소가 없으면 true를 반환합니다. |
| toString() | 이 컬렉션의 문자열 표현을 반환합니다. |
인터페이스 java.util.Collection에 선언된 메소드
| 방법 | 설명 |
|---|---|
| containAll(컬렉션 c) | 이 컬렉션에 지정된 컬렉션의 모든 요소가 포함되어 있으면 true를 반환합니다. |
| 같음(객체 o) | 지정된 개체가 이 컬렉션과 동일한지 비교합니다. |
| 해시 코드() | 이 컬렉션의 해시 코드 값을 반환합니다. |
| 비었다() | 이 컬렉션에 요소가 없으면 true를 반환합니다. |
| 병렬스트림() | 이 컬렉션을 소스로 사용하여 병렬 스트림을 반환합니다. |
| 크기() | 이 컬렉션의 요소 수를 반환합니다. |
| 개울() | 이 컬렉션을 소스로 사용하여 순차 스트림을 반환합니다. |
| toArray(IntFunction 생성기) | 제공된 생성기 함수를 사용하여 반환된 배열을 할당하여 이 컬렉션의 모든 요소를 포함하는 배열을 반환합니다. |
인터페이스 java.util.Queue에 선언된 메소드
| 방법 | 설명 |
|---|---|
| 몰래 엿보다() | 이 큐의 헤드를 검색하지만 제거하지는 않습니다. 또는 이 큐가 비어 있으면 null을 반환합니다. |
| 투표() | 이 큐의 헤드를 검색하고 제거하거나, 이 큐가 비어 있으면 null을 반환합니다. |
응용 :
- Dijkstra 및 Prim의 알고리즘 구현.
- K개의 부정 후 배열 합계 최대화
관련 기사 :
- Java의 Java.util.PriorityQueue 클래스
- Java의 Comparator를 통해 PriorityQueue 구현