[데이터 구조 와 알고리즘 05] 우선 순위 대기 열

정의: 사실은 질서 있 는 대기 열 입 니 다.
연산 제한: 자동 정렬.자동 정렬 인 이상 먼저 나 온 문 제 를 고려 할 필요 가 없습니다. 정렬 한 후에 어 지 러 워 지기 때문에 정렬 방식 (최대 로 할 것 인지 최소 로 할 것 인지) 만 정의 해 야 합 니 다. 여 기 는 논 리 를 간소화 하기 위해 서 대기 열 이 저장 공간 을 순환 적 으로 사용 하 는 문 제 를 고려 해 야 합 니 다. 우 리 는 최대 치 를 아래 표 시 된 0 의 위치 에 영원히 두 고 대기 열 을 낼 때 최소 치 를 취해 야 합 니 다.물론 너 도 거꾸로 할 수 있다.
기본 연산:
                      1. 첨가.
                      2: 제거.
                      3: 최소 치 를 취한 다.

public class PriorityQueue {
	
	private Long[] queArray;
	
	private int maxSize ;//       
	
	private int nItems ;//        
	
	public PriorityQueue(int size){
		maxSize = size ;
		queArray = new Long[maxSize];
		nItems = 0 ;
	}

	//  ，     
	public void insert(long item){
		if(isFull()) throw new ArrayIndexOutOfBoundsException(maxSize);
		int j = 0 ;
		if(nItems==0){
			queArray[nItems++] = item ;
		}else{
			for(j=nItems-1 ;j>=0;j--){
				if(item>queArray[j]){
					queArray[j+1] = queArray[j];
				}else{
					break;
				}
			}
			queArray[j+1] = item;
			nItems++;
		}
	}
	public long remove(){
		if(isEmpty()) throw new NullPointerException();
		return queArray[--nItems];
	}
	
	public long min(){
		if(isEmpty()) throw new NullPointerException();
		return queArray[nItems-1];
	}
	
	public boolean isEmpty(){
		return (nItems==0);
	}
	public boolean isFull(){
		return (nItems==maxSize);
	}
	
	public static void main(String[] args) {
		PriorityQueue priorityQueue = new PriorityQueue(10);
		priorityQueue.insert(10);
		priorityQueue.insert(13);
		priorityQueue.insert(15);
		priorityQueue.insert(8);
		synchronized (System.out) {
			for(int i =0;i<10;i++){
				System.out.print(priorityQueue.queArray[i]+",");
			}
			System.out.println();
			System.out.println("min"+priorityQueue.min());
			System.out.println("remove"+priorityQueue.remove());
			System.out.println("remove"+priorityQueue.remove());
			System.out.println("remove"+priorityQueue.remove());
			System.out.println("remove"+priorityQueue.remove());
			//System.out.println("min"+priorityQueue.min());
			System.out.println("remove"+priorityQueue.remove());
		}
	}
}

실행 결과:

15,13,10,8,null,null,null,null,null,null,
min8
remove8
remove10
remove13
remove15
Exception in thread "main" java.lang.NullPointerException
	at data.queue.PriorityQueue.remove(PriorityQueue.java:47)
	at data.queue.PriorityQueue.main(PriorityQueue.java:80)

코드 가 너무 간단 해서 주석 을 달 지 않 습 니 다.
이것 은 배열 로 이 루어 진 우선 순위 대기 열 입 니 다. 사실은 여러 가지 실현 방식 이 있 습 니 다. 그 다음 에 나무의 사상 을 통 해 이 루어 진 우선 순위 대기 열 을 소개 할 것 입 니 다. 사실은 다른 이름 인 더미 가 있 습 니 다.