java priority queue tutorial implementation examples
이 자습서에서는 Java Priority Queue 및 Comparator, Min 및 Max Priority Queue와 같은 관련 개념과 함께 구현 예를 설명합니다.
Priority Queue 데이터 구조는 요소가 FIFO 순서가 아니라 대기열 생성 중에 사용되는 자연 요소 또는 사용자 정의 비교기에 따라 존재하는 특수 대기열입니다.
=> 여기에서 Java Beginners Guide를 살펴보십시오.
학습 내용 :
Java의 우선 순위 대기열
Priority Queue에서 대기열의 앞쪽은 자연스러운 순서에 따라 최소한의 요소를 가지며 뒤쪽은 대기열에서 가장 큰 요소를 가리 킵니다.
숫자로 구성된 우선 순위 대기열의 예는 다음과 같습니다.
모바일 테스트 인터뷰 질문 및 답변 pdf
따라서 위에 표시된 우선 순위 대기열에서 요소가 제거되면 최소 요소가됩니다.
마찬가지로 알파벳 우선 순위 대기열의 경우 ASCII 값이 고려되고 대기열 요소는 ASCII 값에 따라 정렬됩니다.
다음은 PriorityQueue의 주요 특성 중 일부입니다.
- PriorityQueue는 바인딩되지 않은 대기열입니다.
- PriorityQueue는 null 값을 허용하지 않습니다.
- 비교할 수없는 개체의 경우 우선 순위 대기열을 만들 수 없습니다.
- PriorityQueue는 AbstractQueue, AbstractCollection, Collection 및 Object와 같은 클래스에서 상속됩니다.
- 대기열의 머리 또는 앞쪽에는 자연 순서에 따라 최소 요소가 포함됩니다.
- Priority Queue 구현은 스레드로부터 안전하지 않습니다. 따라서 동기화 된 액세스를 원하면 PriorityBlockingQueue를 사용해야합니다.
PriorityQueue 클래스는 Java 큐 인터페이스를 상속하며 java.util 패키지의 일부입니다.
PriorityQueue 클래스의 일반적인 선언은 다음과 같습니다.
public class PriorityQueue extends AbstractQueue implements Serializable아래 다이어그램은 PriorityQueue 클래스의 클래스 계층 구조를 보여줍니다.
우선 순위 대기열의 시간 복잡성
- 삽입 (인큐) 및 삭제 (디큐) 메서드에 대한 우선 순위 대기열의 시간 복잡도는 O (log (n))입니다.
- Priority Queue에는 제거 및 포함 메서드에 대한 선형 시간 복잡성이 있습니다.
- Priority Queue의 요소를 검색하는 메서드는 일정한 시간 복잡도를 갖습니다.
Java의 우선 순위 대기열 예
아래 프로그램은 Java의 간단한 PriorityQueue를 보여줍니다. PriorityQueue 클래스의 객체를 만들고 여기에 값을 추가 한 다음 Iterator를 사용하여 Queue의 내용을 표시합니다.
import java.util.*; class Main{ public static void main(String args()){ PriorityQueue cities_queue=new PriorityQueue(); //initialize the PriorityQueue with values cities_queue.add('Sydney'); cities_queue.add('Venice'); cities_queue.add('New York'); cities_queue.add('California'); cities_queue.add('Melbourne'); //print the head of the PriorityQueue System.out.println('PriorityQueue Head:'+cities_queue.element()); //Define the iterator for PriorityQueue and print its elements System.out.println('
PriorityQueue contents:'); Iterator iter=cities_queue.iterator(); while(iter.hasNext()){ System.out.print(iter.next() + ' '); } } } 산출:
Java Priority Queue API 메서드
생성자 :
| 생성자 프로토 타입 | 기술 | |
|---|---|---|
| 몰래 엿보다 | E 엿보기 () | 요소를 삭제하지 않고 큐의 헤드를 반환합니다. |
| PriorityQueue () | 초기 용량이 1 인 PriorityQueue 개체를 만드는 기본 생성자입니다. | |
| PriorityQueue (컬렉션 c) | 지정된 컬렉션의 초기 요소를 사용하여 PriorityQueue 개체를 만듭니다. c. | |
| PriorityQueue (int initialCapacity) | 주어진 'initialCapacity'로 PriorityQueue 개체를 만듭니다. 요소는 자연 순서대로 정렬됩니다. | |
| PriorityQueue (int initialCapacity, Comparator comparator) | 주어진 'initialCapacity'로 PriorityQueue 개체를 만듭니다. 요소는 주어진 비교기에 따라 정렬됩니다. | |
| PriorityQueue (PriorityQueue c) | c에서 제공하는 다른 PriorityQueue 개체에서 PriorityQueue 개체를 만듭니다. | |
| PriorityQueue (SortedSet c) | c에 의해 제공된 SortedSet에서 PriorityQueue 개체를 만듭니다. |
행동 양식
| 방법 | 방법 프로토 타입 | 기술 |
|---|---|---|
| 더하다 | 부울 추가 (E e) | PriorityQueue에 요소 e를 추가합니다. |
| 맑은 | 무효 clear () | 모든 요소를 삭제하여 PriorityQueue를 지 웁니다. |
| 비교기 | Comparatorcomparator () | 큐에서 요소의 순서에 사용되는 사용자 지정 비교기를 반환합니다. |
| 포함 | 부울 contains (Object o) | PriorityQueue에 주어진 요소 o가 포함되어 있는지 확인합니다. 그렇다면 true를 반환합니다. |
| 반복자 | Iteratoriterator () | 지정된 PriorityQueue에 대한 반복기를 가져 오는 메서드입니다. |
| 제공 | 부울 제공 (E e) | 주어진 요소 e를 PriorityQueue에 삽입합니다. |
| 투표 | E 투표 () | 큐의 헤드를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다. |
| 없애다 | 부울 제거 (Object o) | 큐에있는 경우 주어진 요소 o의 인스턴스를 제거합니다. |
| 크기 | int 크기 () | 이 PriorityQueue에있는 요소의 크기 또는 수를 반환합니다. |
| toArray | Object () toArray () | 주어진 PriorityQueue의 배열 표현을 반환합니다. |
| toArray | T () toArray (T () a) | 지정된 배열 a와 동일한 런타임 유형을 사용하여 지정된 우선 순위 큐에 대한 배열 표현을 반환합니다. |
자바 구현
Java 프로그램을 사용하여 위의 PriorityQueue 메서드를 설명해 보겠습니다.
import java.util.*; class Main { public static void main(String args()) { // Creating empty priority queue PriorityQueue numQueue = new PriorityQueue(); // add elements to numQueue using add() numQueue.add('Five'); numQueue.add('One'); numQueue.add('Seven'); numQueue.add('Three'); numQueue.add('Eleven'); numQueue.add('Nine'); // Print the head element using Peek () method System.out.println('Head element using peek method:' + numQueue.peek()); // Printing all elements System.out.println('
The PriorityQueue elements:'); Iterator iter1 = numQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); // remove head with poll () numQueue.poll(); System.out.println('
After removing an element' + 'with poll function:'); Iterator iter2 = numQueue.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); // Remove 'Three' using remove () numQueue.remove('Three'); System.out.println('
Element 'Three' with' + ' remove function:'); Iterator iter3 = numQueue.iterator(); while (iter3.hasNext()) System.out.print(iter3.next() + ' '); // Check if an element is present in PriorityQueue using contains() boolean ret_val = numQueue.contains('Five'); System.out.println('
Priority queue contains 'Five' ' + 'or not?: ' + ret_val); // get array equivalent of PriorityQueue with toArray () Object() numArr = numQueue.toArray(); System.out.println('
Array Contents: '); for (int i = 0; i 산출:
소프트웨어 테스트에서 테스트 데이터 생성
Java 8의 우선 순위 대기열
Java 8은 PriorityQueue 클래스에 'spliterator ()'와 같은 메서드를 하나 더 추가합니다.
이 방법에 대한 자세한 내용은 다음과 같습니다.
방법 이름 : 쪼개는 도구
방법 프로토 타입 : 공개 최종 분할기 분할기 ()
방법 설명 : 이 메서드는 PriorityQueue 요소에 대한 분할자를 만듭니다. 이 스플리터는 늦게 바인딩되고 실패하지 않습니다.
우선 순위 큐 비교기
이미 언급했듯이 PriorityQueue 요소는 자연스럽게 정렬됩니다. 순서를 변경하려면 비교기를 지정하고 PriorityQueue 개체를 만드는 동안 사용해야합니다. 그런 다음 PriorityQueue는이 비교기를 사용하여 요소를 정렬합니다.
아래 Java 프로그램은 요소 순서 지정을 위해 사용자 정의 비교기를 사용하는 방법을 보여줍니다. 이 프로그램에서는 '비교'방법을 재정의하는 새로운 맞춤 비교기를 정의합니다. 비교 메소드는 길이에 따라 PriorityQueue의 요소를 정렬하는 데 사용됩니다.
import java.util.*; public class Main { public static void main(String() args) { // A custom comparator that compares two Strings by their length. Comparator customComparator = new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } }; // Create a Priority Queue with a custom Comparator PriorityQueue colorsPriorityQueue = new PriorityQueue(customComparator); // Add items to a Priority Queue colorsPriorityQueue.add('Red'); colorsPriorityQueue.add('Green'); colorsPriorityQueue.add('Blue'); colorsPriorityQueue.add('Cyan'); colorsPriorityQueue.add('Magenta'); colorsPriorityQueue.add('Yellow'); // Printing all elements System.out.println('
The PriorityQueue elements with custom Comparator:'); Iterator iter1 = colorsPriorityQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); } } 산출:
Java의 최소 우선 순위 대기열
Priority Queue의 자연스러운 순서는 대기열의 헤드에 최소 또는 최소 요소를 가지므로 순서가 오름차순입니다. 이를 요소의 오름차순으로 '최소 우선 순위 대기열'이라고합니다.
아래의 Java 프로그램은 Java에서 Min Priority Queue의 구현을 보여줍니다.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with default ordering PriorityQueue pq = new PriorityQueue(); //add element to the PriorityQueue pq.add(8); pq.add(6); pq.add(4); pq.add(2); pq.add(12); pq.add(10); //display the min PriorityQueue System.out.println('The min Priority Queue (natural ordering) contents:'); Integer val = null; while( (val = pq.poll()) != null) { System.out.print(val + ' '); } } } 산출:
Java의 최대 우선 순위 대기열
최소 우선 순위 큐에는 오름차순 요소가 있지만 최대 우선 순위 큐에는 내림차순으로 요소가 있습니다. 즉, 최대 우선 순위 큐의 헤드가 큐에서 가장 큰 요소를 반환합니다.
아래의 Java 프로그램은 Java의 Max Priority Queue를 보여줍니다.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with custom comparator to generate max PQ PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(Integer lhs, Integer rhs) { if (lhs 산출:
위의 프로그램에서 볼 수 있듯이 우선 순위 큐에서 요소의 자연스러운 순서를 변경하려면 사용자 지정 비교기를 정의해야합니다.
자주 묻는 질문
Q # 1) Java의 Priority 대기열은 무엇입니까?
대답: 대기열의 모든 요소가 자연 순서에 따라 또는 사용자 지정 비교기를 사용하여 정렬되는 특수 대기열을 우선 순위 대기열이라고합니다. FIFO 순서를 따르지 않습니다.
Q # 2) Java에서 Max Priority 대기열을 어떻게 설정합니까?
대답: 큐의 헤드가 큐에서 가장 큰 요소를 반환하도록 사용자 지정 비교기를 사용하여 Java에서 Max Priority Queue를 설정할 수 있습니다.
Q # 3) Priority 대기열은 중복 Java를 허용합니까?
대답: 예. Priority Queue는 중복 값을 허용합니다.
Q # 4) Java Priority 대기열은 최대 또는 최소입니까?
대답: 기본적으로 Java의 우선 순위 대기열은 자연스러운 순서를 가진 최소 우선 순위 대기열입니다. 최대로 만들려면 큐의 헤드가 큐에서 가장 큰 요소를 반환하도록 사용자 지정 비교기를 사용해야합니다.
Q # 5) 우선 순위 대기열이 정렬되어 있습니까?
대답: 기본적으로 큐의 헤드가 정렬되고 Priority 큐의 헤드 요소가 가장 적습니다. 나머지 요소는 필요할 때 주문됩니다.
결론
이것으로 Java의 Priority Queues에 대한 자습서를 마쳤습니다. Priority Queue는 대기열 인터페이스를 구현하며 요소가 자연 순서대로 정렬되는 특수 대기열입니다. FIFO 순서를 따르지 않습니다. 우선 순위 대기열의 자연스러운 순서를 변경하려면 사용자 지정 비교기를 사용할 수 있습니다.
우선 순위 대기열은 주로 프린터 예약, CPU 작업 예약 등에 사용됩니다. 힙 (최소 또는 최대)도 우선 순위 대기열을 사용하여 구현됩니다.
C ++ 버블 정렬 기능
추천 도서
