[Java] Collection에 대해 알아보기(3) - Queue

Erin Lee·2024년 3월 7일

Java

Queue Interface

Queue 인터페이스는 Stack 클래스와 반대로 선입선출(FIFO, First In First Out) 방식으로 데이터가 처리되는 인터페이스이다.

Queue 인터페이스를 구현하는 클래스로는 LinkedList와 PriorityQueue 클래스가 있다.

Queue의 구현체중 하나인 LinkedList

선입선출
데이터 저장된 순서 유지
데이터 중복 허용
노드로 이루어짐

Queue 인터페이스를 LinkedList로 구현함으로써 기존 LinkedList에 선입선출 기능을 추가한 구조로 볼 수 있다.

노드로 연결된 LinkedList에 새로운 데이터를 추가할 시 가장 마지막 노드에 연결된다.

그리고 제거 시에는 가장 앞에 있는 노드부터 제거된다.

생긴 궁금증!!

LinkedList 내부 코드를 보면 인덱스를 지정하지 않은 기본 add() 메서드는 linkLast()로 넘겨지면서 가장 마지막 노드로 연결되며 사이즈도 하나씩 커진다.

제거 시에도 poll() 메서드와 remove() 기본 메서드를 사용시에는 unlinkFirst(), removeFirst() 메서드를 통해 첫번째 노드의 연결이 해제되면서 삭제된다.

Queue의 구현체중 하나인 PriorityQueue(우선순위 큐)

데이터의 저장되는 순서를 유지하지 않음
Heap 구조
특정 우선순위 기반 정렬되어 우선순위가 높은 것부터 추출되는 구조
내부적으로 동기화를 구현하지 않음
null값을 허용하지 않음

PriorityQueue는 Comparator 비교 클래스를 사용하여 데이터가 정렬되는 구조이다.

PriorityQueue의 구조

PriorityQueue의 내부는 Heap을 기반으로 한 이진 탐색 트리 구조이다.

*Heap 자료구조
Heap이란 PriorityQueue를 구현하기 위한 자료구조로 이진 트리 형태를 가진다.
Heap은 두가지 종류로 분류된다.

Max Heap
최대 힙은 각 노드의 값이 자식 노드의 값보다 크거나 같은 형태이다.
Min Heap
최소 힙은 각 노드의 값이 자식 노드의 값보다 작거나 같은 형태이다.

PriorityQueue 처리 과정

추가
PriorityQueue의 add(), offer()을 통해 데이터를 추가하면 가장 마지막 위치에 추가된다.
부모 노드를 확인 후 부모 노드의 값과 비교하여 Heap 구조에 맞게 위치를 정렬하는 작업을 반복함으로써 데이터를 정렬시킨다.

Max Heap 기준 새로운 데이터가 추가되고 정렬되어가는 과정이다.
삭제
데이터를 삭제하는 경우에는 root 노드가 삭제되는 방식이다.

❓ 생긴 궁금증!

Queue 인터페이스를 구현한 클래스로 선입선출일줄 알았는데 아니다.

Max Heap은 root 노트부터 시작하여 가장 큰 값부터 점점 작아지는 정렬 구조이고 Min Heap은 root 노드 값이 가장 작고 점점 커지는 정렬 구조이다.

이때 PriorityQueue에서 값을 출력할 때 root 노드부터 자손 노드 순으로 값을 출력한다.

PriorityQueue에 데이터를 추가 후 출력해서 확인해보았다.

import java.util.Iterator;
import java.util.PriorityQueue;

public class QueueHeapTest {
    
    public static void main(String[] args) {
        
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.offer(1);
        minHeap.offer(9);
        minHeap.offer(2);
        minHeap.offer(5);
        minHeap.offer(4);
        minHeap.offer(3);
        minHeap.offer(6);

        Iterator<Integer> it = minHeap.iterator(); 

        while(it.hasNext()){
            System.out.println(it.next());
        } 
        //결과값
        // 1
        // 4
        // 2
        // 9
        // 5
        // 3
        // 6
    }
}

데이터를 추가한 순서대로 출력되는 것은 아니지만 가장 root 노드부터 순차적으로 출력되기 때문에 선입선출로 보는 것인가?

❓ Heap 구조는 max heap, min heap 두가지가 있는데 PriorityQueue는 두가지를 다 구현할 수 있다는 것인가?

→ 둘 다 구현이 가능하다.

Min Heap 구조
정렬 순서를 별도로 주지 않고 생성된 PriorityQueue 인스턴스는 기본적으로 Min Heap 구조를 가진다.
Max Heap 구조
PriorityQueue 인스턴스를 생성할 때 Comparator 타입의 인자를 받는 PriorityQueue 생성자를 호출하여 정렬 기준을 초기화 해주면 Max Heap 구조의 PriorityQueue 인스턴스가 생성된다.

MaxHeap 구조의 PriorityQueue 만들어 확인해보자

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;

public class MaxHeapTest {
    public static void main(String[] args) {
	        
		//기본적으로 maxHeap구조이기 때문에 정렬 기준을 반대로 해주는 reverseOrder() 기준을 사용했다.
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
		
		maxHeap.offer(1);
        maxHeap.offer(9);
        maxHeap.offer(2);
        maxHeap.offer(5);
        maxHeap.offer(4);
        maxHeap.offer(3);
        maxHeap.offer(6);
        
        Iterator<Integer> it = maxHeap.iterator(); 

        while(it.hasNext()){
            System.out.println(it.next());
        } 
        
//        결과값
//        9
//        5
//        6
//        1
//        4
//        2
//        3	
	}
}