[Java] 우선순위 큐 사용하기

go_go_·2022년 7월 6일
0

Java

목록 보기
4/4
post-custom-banner

✔목차

  • 선언
  • 삽입
  • 삭제
  • 접근
  • 기타
  • 우선순위 지정

선언

new PriorityQueue

  • new PriorityQueue<[type]>()
    • Min heap으로 동작
    • Max heap은 Collections 필요
	//오름차순
	PriorityQueue<Integer> pq = new PriorityQueue<>();
    
    //내림차순
	PriorityQueue<Integer> pqHightest = new PriorityQueue<>(Collections.reverseOrder());

삽입

  • add
  • offer
  • add(E element)
    • 큐 공간 없어 삽입 실패 시 exception터짐
  • offer(E element)
    • 큐 공간 없어 삽입 실패 시 null 반환
	pq.add(3);
	pq.add(1);
	pq.offer(2); //pq: [1, 3, 2]

삭제

  • poll
  • remove
  • removeIf
  • removeAll
  • clear
  • poll()
    • front에 위치한 원소 제거 후 반환
    • 큐 비었다면 null 반환
  • remove()
    • front에 위치한 원소 제거 후 반환
    • 큐 비었다면 exception 터짐
	pq.poll();
	pq.remove();
  • removeIf(Predicate<? super E> filter)
    • 람다 표현식으로 파라미터 전달 가능
    • 필터링 조건
	//pq: [1, 2, 3, 4, 5]
	pq.removeIf(n -> (n % 2 == 0)); //pq: [1, 3, 5]
  • remove(E element)
    -반환형: boolean
    • 특정 원소 제거
    • 삭제하려는 원소 큐에 없으면 false 반환
  • removeAll(Collection<?>)
    • 파라미터로 준 컬렉션의 겹치는 원소들 제거
	//pq1: [1, 2, 3, 4, 5]
    //pq2: [1, 3, 5]
    pq1.removeAll(pq2); //p1: [2, 4]
    pq1.remove(9); //false

접근

  • peek
  • iterator
  • peek()
    -반환형: E, queue의 형식
    • 첫 번째 데이터 반환
    • 큐 비어있다면 null 반환
	int i = pq.peek();
  • iterator()
    -반환형: Iterator
    • 데이터 지우지 않고 순회할 경우 사용
	//pq: [1, 3, 2]
	Iterator<Integer> iter = pq.iterator();
	while(iter.hasNext()) {
		Integer i = iter.next();
		System.out.print(i + " ");
	}
	출력
    1 3 2

기타

  • size
  • toArray
  • contains
  • size()
    -반환형: int
	int size = pq.size()
  • toArray()
    -반환형: Object[]
    • 큐에 저장된 데이터 배열로 가져옴
	for(Object i : pq.toArray()) {
		System.out.println(i);
	}
	출력
    1 3 2

우선순위 지정

특정 기준으로 정렬하고 싶거나 큐에 저장된 객체의 어떤 속성으로 정렬하고 싶을 때 다음을 이용한다.
1. implements Comparable
2. Comparator 생성

	예제 클래스
    public class People {
		String name;
		int age;
		int height;
	}
    
  • Comparable
    • 클래스에 Comparable 상속받음
    • compareTo 오버라이딩
    public class People implements Comparable<People>{
	String name;
	int age;
	int height;

	@Override
	public int compareTo(People o) {
    // 키로 오름차순 정렬
    // 현재 객체가 o보다 작으면 -1, 크면 1 반환
    // 동일하면 0 반환
		return (this.height > o.height ? 1 : -1);
        }
    }
    
  • Comparator
    • 선언할 때 우선순위 지정해줌
    • compare 함수를 오버라이딩
	PriorityQueue<People> pq = new PriorityQueue<>(new Comparator<People>() {
    	@Override
		public int compare(People o1, People o2) {
    		return o1.height > o2.height ? 1 : -1;
        	}
    	});
profile
개발도 하고 싶은 클라우드 엔지니어
post-custom-banner

0개의 댓글