[Java | 자료구조] 큐 (Queue) 정리

PS/자료구조

[Java | 자료구조] 큐 (Queue) 정리

yaho!! 2024. 7. 24. 08:46

Queue란?

큐(Queue)는 자료구조 중 하나로, 선입선출(FIFO, First In First Out) 방식으로 데이터를 저장하고 처리한다.

큐는 일상 생활에서도 쉽게 접할 수 있는 개념으로 예를 들어보자.

줄 서기는 일상생활에서 쉽게 접할 수 있는 선입선출의 전형적인 예이다.
영화관에 도착해서 티켓을 사기 위해 줄을 서면, 가장 먼저 줄을 선 사람이 먼저 티켓을 구매하게 된다.
이처럼 먼저 들어온 데이터가 먼저 처리되는 방식이 큐의 기본 원리이다.

큐에 데이터를 추가하는 작업을 enqueue 라고 하며, 큐에 데이터를 제거하는 작업을 dequeue 라고 한다.
큐에서는 데이터를 추가할 때는 입구에서, 데이터를 삭제할 때는 출구에서 작업이 이루어 진다.

큐는 다양한 분야에서 유용하게 사용된다. 예를 들어, 운영 체제의 작업 스케줄링, 너비 우선 탐색(BFS) 알고리즘, 프린터 작업 관리 등에서 큐를 활용할 수 있다.

Queue 인터페이스를 구현한 클래스

Java에서는 Queue 인터페이스를 통해 다양한 큐 구현체를 제공한다.

Queue 인터페이스는 java.util 패키지에서 정의되어 있으며, 각 구현체는 특정 요구 사항과 용도에 맞춰 설계되어있다.

LinkedList	Queue 인터페이스를 구현하며, 링크드 리스트 기반의 큐이다.
PriorityQueue	우선순위 큐를 구현하며, 요소가 우선순위에 따라 정렬된다.
ArrayDeque	배열을 기반으로 한 덱(Deque) 구현체로, 큐와 덱의 기능을 제공한다.
ConcurrentLinkedQueue	멀티스레드 환경에서 안전하게 사용할 수 있는 큐 구현체이다.
BlockingQueue	큐가 비어있거나 가득 찼을 때 블로킹 동작을 지원하는 인터페이스로, 구현체로는 ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue 등이 있습니다.

Queue 인터페이스 메서드

boolean add(E e)	큐에 요소를 추가한다. - 큐의 크기 제한이 있는 경우 큐가 가득 차 있으면 예외(IllegalStateException)가 발생한다. - 요소 추가가 성공하면 true를 반환한다.
boolean offer(E e)	큐에 요소를 추가한다. - 큐의 크기 제한이 있는 경우 큐가 가득 차 있으면 false를 반환한다. - 요소 추가가 성공하면 true를 반환하고, 큐가 가득 차 있으면 false를 반환한다. - 큐의 크기 제한이 없으면 항상 true를 반환함
E remove()	큐의 앞쪽에서 요소를 제거한다. - 큐가 비어 있으면 NoSuchElementException을 발생시킨다. - 제거된 요소를 반환한다.
E poll()	큐의 앞쪽에서 요소를 제거한다. - 큐가 비어 있을 경우 null을 반환한다. - 제거된 요소를 반환하거나, 큐가 비어 있으면 null을 반환한다.
E peek()	큐의 앞쪽에 있는 요소를 확인한다. - 큐의 앞쪽 요소를 반환하거나, 큐가 비어 있으면 null을 반환합니다. - 큐의 요소를 제거하지 않지 않는다.
E element()	큐의 앞쪽에 있는 요소를 확인한다. - 큐가 비어 있을 경우 NoSuchElementException을 발생시킨다. - 큐의 요소를 제거하지 않지 않는다.
int size()	큐에 있는 요소의 개수를 반환한다.
boolean isEmpty()	큐가 비어 있는지 여부를 확인한다. - 큐가 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.
boolean contains(Object o)	큐에 특정 요소가 포함되어 있는지 확인한다. - 큐에 해당 요소가 포함되어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.

Queue 구현하기

1. LinkedList를 사용한 큐 구현

LinkedList 클래스는 Queue 인터페이스를 구현하고 있으며, 큐의 기본 연산을 지원한다.

Queue<Integer> queue = new LinkedList<>();

queue.add(10);
queue.add(20);
queue.add(30);

System.out.println("앞쪽 요소: " + queue.peek());
System.out.println("제거된 요소: " + queue.remove());
System.out.println("제거 후 큐 상태: " + queue);
 
// 실행결과
앞쪽 요소: 10
제거된 요소: 10
제거 후 큐 상태: [20, 30]

2. PriorityQueue를 사용한 큐 구현

PriorityQueue 클래스는 자바의 java.util 패키지에 포함된 큐 구현체로, 요소를 우선순위에 따라 정렬하는 큐이다.

기본적으로 요소는 자연 순서(숫자의 경우 오름차순) 또는 제공된 비교자(comparator)에 따라 우선순위가 결정된다.

우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.

사용자가 정의한 객체를 우선순위 큐에 저장하기 위해서는 정렬 기준이 정의 되어야하기 때문이다.
정렬 기준이 없으면 우선순위를 정할 수 없기 떄문이다.

PriorityQueue<Integer> queue = new PriorityQueue<>();
// new PriorityQueue<>(Collections.reverseOrder()); 높은 숫자가 우선 내림차순

queue.add(40);
queue.add(10);
queue.add(30);
queue.add(20);

System.out.println("큐 상태: " + queue);
System.out.println("앞쪽 요소: " + queue.peek());
System.out.println("제거된 요소: " + queue.poll());
System.out.println("제거 후 큐 상태: " + queue);

//실행결과
큐 상태: [10, 20, 30, 40]
앞쪽 요소: 10
제거된 요소: 10
제거 후 큐 상태: [20, 40, 30]

사용자 정의 객체와 우선순위 큐

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class Main {
    public static void main(String[] args) {

        Comparator<Person> ageComparator = new Comparator<Person>() {
            @Override
            public int compare(Person p1, Person p2) {
                return Integer.compare(p1.age, p2.age);
            }
        };

        PriorityQueue<Person> queue = new PriorityQueue<>(ageComparator);

        queue.add(new Person("김주인", 25));
        queue.add(new Person("박멍구", 8));
        queue.add(new Person("최베베", 10));

        System.out.println("큐 상태: " + queue);
        System.out.println("앞쪽 요소: " + queue.peek());
        System.out.println("제거된 요소: " + queue.poll());
        System.out.println("제거 후 큐 상태: " + queue);

    }
}

//실행결과
큐 상태: [박멍구 (8), 김주인 (25), 최베베 (10)]
앞쪽 요소: 박멍구 (8)
제거된 요소: 박멍구 (8)
제거 후 큐 상태: [최베베 (10), 김주인 (25)]

주요 특징

우선순위 기반
- PriorityQueue는 우선순위에 따라 요소를 정렬한다.
- 기본적으로는 요소의 자연 순서(Comparable을 구현한 경우)로 정렬된다.
- 사용자 정의 객체의 경우, 제공된 비교자(Comparator)를 사용하여 정렬할 수 있다.
힙 기반
- 내부적으로는 최소 힙(min-heap) 구조를 사용하여 요소를 저장한다. -> 포스팅 작성하자.
- 이는 가장 작은 요소가 큐의 맨 앞에 위치하게 한다.
- 최대 힙(max-heap) 구조로 사용하려면 비교자를 제공해야 한다.
순서 보장 없음
- 우선순위 큐는 요소의 삽입 순서를 보장하지 않는다.
- 우선순위에 따라 자동으로 정렬되기 때문에, 요소를 제거할 때는 우선순위가 가장 높은 요소가 먼저 제거된다.

3. ArrayBlockingQueue를 사용한 큐 구현

ArrayBlockingQueue는 고정 크기의 배열을 사용하는 차단 큐로, 큐의 크기가 제한되어 있다.

스레드 안전성을 보장하며, 멀티스레드 환경에서 유용하게 사용된다.

BlockingQueue<Integer>queue=newArrayBlockingQueue<>(3);

queue.put(1);
queue.put(2);
queue.put(3);

System.out.println("Queue:"+queue);
System.out.println("RemovedElement:"+queue.take());
System.out.println("Queueafterremoval:"+queue);

//실행결과
큐 상태: [1, 2, 3]
제거된 요소: 1
제거후 큐 상태: [2, 3]

4. ConcurrentLinkedQueue를 사용한 큐 구현

ConcurrentLinkedQueue는 스레드 안전한 비차단 큐이다.

멀티스레드 환경에서의 높은 성능을 제공하며, 큐의 앞쪽과 뒤쪽에서 비차단 방식으로 요소를 추가하고 제거할 수 있다.

ConcurrentLinkedQueue<Integer>queue=newConcurrentLinkedQueue<>();

queue.add(1);
queue.add(2);
queue.add(3);

System.out.println("앞쪽 요소:"+queue.peek());
System.out.println("제거된 요소:"+queue.poll());
System.out.println("제거 후 큐 상태:"+queue);

//실행결과
큐 상태: [1, 2, 3]
제거된 요소: 1
제거후 큐 상태: [2, 3]