[Java] Java에서 Queue와 구현체들 (+ ArrayList와 LinkedList의 차이)

Queue

Java의 Queue 인터페이스는 FIFO(First In First Out) 방식의 순차적 자료 구조를 구현합니다.

즉, 먼저 추가된 요소가 먼저 제거됩니다. Queue 인터페이스는 LinkedList, PriorityQueue, ArrayBlockingQueue 등 다양한 클래스에서 구현됩니다.

 

Queue 인터페이스는 큐에 요소를 추가, 제거, 검사하는 여러 메서드를 제공합니다. 다음은 가장 일반적으로 사용되는 메서드들입니다.

• add(element): 요소를 큐의 맨 뒤에 추가합니다. 큐가 가득 차 있으면 예외를 발생시킵니다.
• offer(element): 요소를 큐의 맨 뒤에 추가합니다. 큐가 가득 차 있으면 false를 반환합니다.
• remove(): 큐의 앞에서 요소를 제거하고 반환합니다. 큐가 비어 있으면 예외를 발생시킵니다.
• poll(): 큐의 앞에서 요소를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다.
• element(): 큐의 앞에 있는 요소를 제거하지 않고 반환합니다. 큐가 비어 있으면 예외를 발생시킵니다.
• peek(): 큐의 앞에 있는 요소를 제거하지 않고 반환합니다. 큐가 비어 있으면 null을 반환합니다.

PriorityQueue(우선순위 큐)

PriorityQueue 클래스는 Queue 인터페이스의 구현체 중 하나이며, 요소를 우선순위에 따라 정렬하여 저장합니다.

이 우선순위는 요소의 자연스러운 순서(요소가 Comparable 인터페이스를 구현하는 경우) 또는 Comparator에 의해 제공될 수 있습니다. 따라서 PriorityQueue에서는 먼저 추가된 요소가 아닌 가장 높은 우선순위를 가진 요소가 먼저 제거됩니다.

PriorityQueue는 Heap 구현에도 사용할 수 있습니다

다음은 MaxHeap 구현 예제 코드입니다.

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

public class Main {
    public static void main(String[] args) {
        // 최대 힙 생성
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        // 요소 추가
        maxHeap.add(4);
        maxHeap.add(2);
        maxHeap.add(1);
        maxHeap.add(3);

        // 요소 출력 (힙에서 요소를 제거하면서 출력)
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
    }
}

MinHeap의 경우엔 PriorityQueue<>();로 선언하면 됩니다.

LinkedList

LinkedList는 Collection 프레임워크에서 구현된 클래스로, 기본적으로 Linked List 자료 구조를 구현합니다.

이는 선형 데이터 구조로, 요소들이 연속적인 위치에 저장되지 않고 각 요소는 데이터 부분과 주소 부분을 가진 별도의 객체입니다.

요소들은 포인터와 주소를 사용하여 연결됩니다. 각 요소를 노드라고 합니다.

동적성과 삽입 및 삭제의 용이성 때문에 배열이나 큐보다 선호됩니다. 

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> ll = new LinkedList<>();

        // 요소 추가
        ll.add(1);
        ll.add(2);
        ll.add(3);

        // 요소 출력 (큐에서 요소를 제거하면서 출력)
        while (!ll.isEmpty()) {
            System.out.println(ll.poll());
        }
    }
}

PriorityBlockingQueue

PriorityQueue와 LinkedList 두 구현 모두 스레드 안전(thread-safe)하지 않다는 점을 주의해야 합니다.

스레드 안전한 구현이 필요한 경우, PriorityBlockingQueue는 대안적인 구현 방법입니다.

PriorityBlockingQueue는 PriorityQueue 클래스와 동일한 정렬 규칙을 사용하며,

Java의 concurrent 패키지에 속한 클래스로, 스레드 안전한 PriorityQueue를 제공합니다.

이 클래스는 무제한 크기를 가지며, 스레드가 요소를 검색할 때 해당 요소가 사용 가능해질 때까지 대기하게 할 수 있습니다. 따라서 이 클래스는 동시성을 다루는 멀티스레드 환경에서 유용합니다.
크기가 무제한이기 때문에, 리소스 고갈로 인해 요소 추가가 때때로 실패하며 OutOfMemoryError가 발생할 수 있습니다.

이 클래스를 사용하여 큐 객체를 생성하는 예제 입니다.

import java.util.Queue;
import java.util.concurrent.PriorityBlockingQueue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityBlockingQueue<>();

        // 요소 추가
        queue.add(3);
        queue.add(1);
        queue.add(2);

        // 요소 출력 (큐에서 요소를 제거하면서 출력)
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

그렇다면, ArrayList와 LinkedList의 차이는 무엇인가요?

이미지 출처: https://javagoal.com/wp-content/uploads/2020/08/42.png

	ArrayList	LinkedList
구현	배열(Array) 사용	노드를 연결(linked)
데이터 접근 시간	모든 데이터에 상수 시간 소요	위치에 따른 이동 시간 발생
삽입/삭제 시간	삽입 / 삭제 자체는 상수 시간
	삽입 / 삭제 시 데이터 시프트가 필요한 경우 추가 시간 발생	삽입 / 삭제 위치에 따라 그 위치까지 이동하는 시간 발생
리스트 크기 확장	배열 확장이 필요한 경우 새로운 배열에 복사하는 추가 시간 발생	무한대이므로 제한이 없음
검색	최악의 경우 리스트에 있는 아이템 수 만큼 확인
CPU cache	CPU cache 이점 활용	메모리가 연속적이지 않기 때문에 시간적, 공간적 지역성의 캐시 원리를 활용하기 어렵
구현 예	Java의 ArrayList, CPython의 list	Java의 LinkedList

참고 자료

https://www.geeksforgeeks.org/queue-interface-java/

Queue Interface In Java - GeeksforGeeks

https://www.youtube.com/watch?v=xvi-n11kym0&t=1083s