Queue

✏️ Queue

• 큐는 반대로 선입선출(First-in / First-out) 으로 이뤄진 자료구조이다.
  • 삽입과 삭제가 양방향 에서 이뤄진다.

📍 큐의 용어와 Method

• rear : 가장 나중에 추가된 인덱스
• front : 가장 처음에 추가된 인덱스
• add : rear 에 데이터를 추가하는 연산
• poll : front 의 데이터를 삭제하고, 확인하는 연산
• peek : front 의 데이터를 조회하는 연산

📍 큐를 사용하면 좋은 알고리즘

• 우선 탐색

✏️ Priority Queue

• 우선순위 큐도 일번적인 큐의 구조를 가지며,
  FIFO 가 아닌 우선순위를 정해 우선순위가 높은 data 먼저 나가는 자료구조이다.
  - 우선순위의 기준을 정해야되기 때문에 필수적으로 Comparable Interface 를 구현해야 한다.
  - 내부 구조는 힙으로 구성되고, 이진트리 구조로 이루어져 있다.
  - 내부구조가 힙이기 때문에 시간복잡도는 O(NLogN) 이다.

📍 선언 방법

• 오름차순 , 내림차순

// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> pq1 = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> pq2 = new PriorityQueue<>(
    Collections.reverseOrder()
);		

• 직접 커스텀 하기
  • return 값에 따라서 새롭게 추가된 인덱스의 위치를 결정시킬 수 있다.
  • o1, 과 o2 는 각각 새롭게 추가된 값과 그 갑과 비교할 기존 index 를 뜻한다.
    • 트리 구조를 갖고있기 때문에 하나의 값과 순차적으로 비교해나갈 수 있다.
  • return 값은 음수, 양수, 0 이렇게 3가지로 추가된 index 의 위치를 결장한다.
    • 양수 (+) : o1 의 우선순위 하락
    • 음수 (-) : o1 의 우선순의 증가
    • 0 : o1 과 o2 가 동등한 위치에 배치

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) ->{
    
    // 이곳에서 정렬 기준을 만들 수 있다.

});

• 예시
  • 두 index 의 절댓값을 비교해 더 적은 수를 높은 우선순위에 두는 로직
  • 만약 두 절댓값이 같다면 음수를 높은 우선순위로 한다.

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) ->{

        // 절댓값으로 변경//
        int fri = Math.abs(o1);
        int sec = Math.abs(o2);

        // 재배치 //
        if (fri == sec)
            // 더 큰 수의 우선순위를 낮춤
            return o1 > o2 ? 1 :-1;

        // 2번째가 더 클경우 음수가 반환됨 --> 음수의 우선순위가 높아짐
        return fri - sec;
    });

• 만약 String 타입을 비교해야 한다면 compareTo() 를 사용하면 된다.

PriorityQueue<File> Q = new PriorityQueue<>((a, b) -> {
    if (a.str.equals(b.str))
        return a.number - b.number;
    return a.str.compareTo(b.str);
});