우선 순위 대기 열: PriorityQueue

Priority Queue 는 JDK 1.5 부터 제공 하 는 새로운 데이터 구조 인터페이스 로 우선 순위 더 미 를 기반 으로 하 는 큰 우선 순위 대기 열 입 니 다.우선 순위 대기 열 은 먼저 대기 열 을 나 가 는 다른 대기 열 과 다르다.매번 대기 열 에서 꺼 내 는 것 은 최고 우선권 을 가 진 요소 이다.Comparator 를 제공 하지 않 으 면 우선 대기 열 에 있 는 요 소 는 기본적으로 자연 순서대로 배열 되 어 있 습 니 다. 즉, 숫자 는 기본적으로 작은 대기 열 에 있 고 문자열 은 사전 순서에 따라 배열 되 어 있 습 니 다 (Comparable 참조). Comparator 에 따라 지정 할 수 있 습 니 다. 이것 은 어떤 구조 법 을 사용 하 느 냐 에 달 려 있 습 니 다.우선 순위 대기 열 에 서 는 null 요 소 를 허용 하지 않 습 니 다.자연 정렬 에 의존 하 는 우선 순위 대기 열 은 비교 할 수 없 는 대상 을 삽입 할 수 없습니다. (이렇게 하면 ClassCastException 을 초래 할 수 있 습 니 다) 우선 순위 대기 열 은 무한 하지만 내부 용량 이 있어 대기 열 요 소 를 저장 하 는 배열 크기 를 제어 합 니 다.그것 은 보통 적어도 대열 의 크기 와 같다.우선 순위 대기 열 에 요 소 를 계속 추가 하면 서 용량 이 자동 으로 증가 합 니 다.용량 증가 정책 의 세부 사항 을 지정 할 필요 가 없습니다.
간단 한 응용:

package test;
import java.util.PriorityQueue;
public class PriorityQueueTest1 {
 @SuppressWarnings("unchecked")
 public static void main(String[] args) {
  PriorityQueue queue = new PriorityQueue();
  queue.add("AAAAA"); // Add      Obj，PriorityQueue  integer String         ，  new    ，            
  queue.add("BBBBB"); 
  queue.add("CCCCC"); 
  queue.add("DDDDD"); 
  
  System.out.println(queue.peek()); //            
  System.out.println(queue.poll()); //           
  System.out.println(queue.poll());
  
  queue.offer("ZZZZZ"); //               
  
  System.out.println(queue.poll());
  System.out.println(queue.poll());
  System.out.println(queue.poll());
  
  System.out.println(queue.poll()); //          ，  Null
 }
}

 
정의 비교 기:

package test;
import java.util.Comparator;
import java.util.PriorityQueue;
@SuppressWarnings("unchecked")
public class PriorityQueueTest2 {
 private static PriorityQueue queue = new PriorityQueue(10,new Comparators());
 public static void main(String[] args) {
  QueueObject queueObject = new QueueObject();
  queueObject.setId(4);
  queueObject.setObject("AAAAA");
  queue.add(queueObject);
  QueueObject queueObject1 = new QueueObject();
  queueObject1.setId(1);
  queueObject1.setObject("BBBBB");
  queue.add(queueObject1);
  QueueObject queueObject2 = new QueueObject();
  queueObject2.setId(3);
  queueObject2.setObject("CCCCC");
  queue.add(queueObject2);
  
  System.out.println(((QueueObject)queue.poll()).getObject());
  System.out.println(((QueueObject)queue.poll()).getObject());
  System.out.println(((QueueObject)queue.poll()).getObject());
 }
}
class QueueObject {
    private int id;
    private Object object;
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public Object getObject() {
        return object;
    }
    public void setObject(Object object) {
        this.object = object;
    }
}
@SuppressWarnings("unchecked")
class Comparators implements Comparator{
    public int compare(Object arg0, Object arg1) {
        int val1 = ((QueueObject)arg0).getId();
        int val2 = ((QueueObject)arg1).getId();
        return val1 < val2 ? 0 : 1;
    }
}

 
주의사항: 주의 1: 이 대기 열 은 배열 로 이 루어 지지 만 배열 의 크기 는 동적 으로 증가 할 수 있 고 용량 은 무한 합 니 다.주의 2: 이 실현 은 동기 화 되 지 않 습 니 다.스 레 드 안전 이 아 닙 니 다.여러 스 레 드 의 임의의 스 레 드 가 구조 적 으로 목록 을 수정 했다 면 이 스 레 드 는 Priority Queue 인 스 턴 스 를 동시에 방문 해 서 는 안 됩 니 다. 이 때 스 레 드 가 안전 한 Priority BlockingQueue 류 를 사용 하 십시오.주의 3: null 요 소 를 사용 할 수 없습니다.주의 4: 이 는 삽입 방법 (offer, poll, remove () 와 add 방법) 에 O (log (n) 시간 을 제공 합 니 다.reove (Object) 와 contains (Object) 방법 에 선형 시간 을 제공 합 니 다.검색 방법 (peek, element, size) 에 고정 시간 을 제공 합 니 다.주의 5: 방법 iterator () 에서 제공 하 는 교체 기 는 우선 순위 대기 열 에 있 는 요 소 를 질서 있 게 옮 겨 다 니 는 것 을 보장 하지 않 습 니 다.이 유 는 Priority Queue 의 내부 구현 을 참고 할 수 있 습 니 다. 순서대로 옮 겨 다 니 려 면 Arrays. sort (pq. toArray () 를 사용 하 는 것 을 고려 하 십시오.주의 6: 구조 함수 에서 정렬 방법 을 지정 할 수 있 습 니 다.예 를 들 어 Priority Queue () 는 기본 초기 용량 (11) 을 사용 하여 Priority Queue 를 만 들 고 자연 순서에 따라 요 소 를 정렬 합 니 다 (Comparable 사용).Priority Queue (int initialCapacity) 는 지정 한 초기 용량 으로 Priority Queue 를 만 들 고 자연 순서에 따라 요 소 를 정렬 합 니 다 (Comparable 사용).Priority Queue (int initialCapacity, Comparator comparator) 는 지정 한 초기 용량 으로 Priority Queue 를 만 들 고 지정 한 비교 기 comparator 에 따라 요 소 를 정렬 합 니 다.주의 7: 이러한 교체 기 는 Collection 과 Iterator 인터페이스의 모든 선택 방법 을 실현 합 니 다.Priority Queue 의 내 부 는 Priority Queue 가 요소 에 대해 쌓 기 정렬 을 사용 하고 머리 는 지정 한 정렬 방식 의 최소 요소 입 니 다.쌓 기 정렬 은 뿌리 가 최대 (최소) 일 뿐 전체 쌓 기 는 질서 가 있 는 것 이 아 닙 니 다.방법 iterator () 에서 제공 하 는 교체 기 는 전체 배열 을 순서대로 옮 겨 다 닐 수 있 습 니 다.배열 의 첫 번 째 요소 가 가장 작다 는 것 만 보장 할 수 있다. 
 
ITEYE 사이트 에서 자바 소 강 오리지널 을 보 세 요. 감사합니다!
http://cuisuqiang.iteye.com/  ！
자체 블 로그 주소: http://www.javacui.com/, 내용 은 ITEYE 와 동기 화 됩 니 다!