[DataStructure] 우선순위 큐

안녕하세요:) 점냥입니다

 

Priority Queue는 Heap 자료구조를 구현한 클래스로 우선순위가 높은 요소가 먼저 나가는 Queue 자료구조라고 생각하시면 됩니다

따라서 요소들이 저장될 때 우선순위에 맞게 정렬되기 위해 Priority Queue의 Type들은 Comparable 인터페이스를 구현한 요소들만 저장할 수 있습니다

Priority Queue 주요 함수

반환값	함수	설명
boolean	add( E e )	요소 추가
boolean	contains( E e )	해당 요소가 있는지 확인
E	peek()	제거하지 않고 맨 위 요소 꺼내기
E	poll()	제거하면서 맨 위 요소 꺼내기
boolean	remove( E e )	해당 요소 삭제
int	size()	queue 크기 반환
<T>T[ ]	toArray( T[] a )	T 타입의 배열 반환

 

주요 함수를 보면 일반적인 리스트의 함수들과 큰 차이는 없습니다.

예제 코드

        PriorityQueue<Integer> queue = new PriorityQueue<>();

        queue.add(8);
        queue.add(3);
        queue.add(1);
        queue.add(10);

        while (queue.size() > 0) {
            System.out.println(queue.remove());
        }


    출력
    >> 1
    >> 3
    >> 8
    >> 10

java의 Integer는 Comparable이 기본적으로 구현되어 있는 것 알고 있으시겠죠? 따라서 8, 3, 1, 10 요소를 넣고 나서 remove() 함수로 요소를 삭제해 나가면서 그 값을 출력하면 정렬된 요소가 나옵니다!

 

Iterator는 정렬된 요소대로 출력되지 않는다.

        PriorityQueue<Integer> queue = new PriorityQueue<>();

        queue.add(8);
        queue.add(3);
        queue.add(1);
        queue.add(10);

        for (Integer value : queue) {
            System.out.println(value);
        }


        출력
        >> 8
        >> 3
        >> 1
        >> 10

 

주의할 점으로 Iterator의 순서는 우선순위와 상관없이 add() 호출한 순서대로 출력된 것을 알 수 있습니다. 주의하세요!