'자바 큐 구현'에 해당되는 글 1건

자바의 Queue는 FIFO(First-In-First-Out) 구조를 따르는 자료구조다.

즉, 먼저 추가된 요소가 먼저 제거되는 구조이다.

쉽게 기억하려면 맛집 대기열을 생각하면 된다. 먼저 온 순서대로 가게에 들어가서 먹고, 먼저 나온다라는 걸 이미지로 기억해 두면 편하다.

Queue는 인터페이스이며, 일반적으로 LinkedList, PriorityQueue, ArrayDeque 등으로 구현된다.

Queue의 상속 구조

java.util.Queue<E> extends java.util.Collection<E>

Queue는 Collection 인터페이스를 상속받아 만들어진 인터페이스이다. (그러므로 Queue<E> queue = new Queue<>(); 와 같은 식으로 구현은 못한다.)

그리고 Collection은 다시 Iterable을 상속한다.

전체 계층 구조:

java.lang.Iterable<E>
  └── java.util.Collection<E>
        └── java.util.Queue<E>

1. 기본 메서드

Queue 인터페이스는 java.util 패키지에 포함되어 있으며, 주요 메서드는 다음과 같다:

2. 예제 구현 (LinkedList 기반)

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("Alpha");
        queue.offer("Bravo");
        queue.offer("Charlie");

        System.out.println("헤드 요소: " + queue.peek()); // Alpha

        while (!queue.isEmpty()) {
            System.out.println("제거: " + queue.poll());
        }
    }
}


// 출력
헤드 요소: Alpha
제거: Alpha
제거: Bravo
제거: Charlie

3. 자주 사용하는 구현체

3-1. PriorityQueue

개요:

PriorityQueue는 우선순위가 높은 요소가 먼저 나오는 큐이다.

즉, 일반적인 FIFO 큐가 아니라, 요소를 넣은 순서보다 우선순위 기준(숫자 오름차순, 알파벳 순서 등)에 따라 순서가 결정됨.

특징:

• 내부적으로 힙(heap) 구조로 되어 있음 (기본은 최소 힙)
• Comparable 또는 Comparator를 통해 우선순위를 정할 수 있음
• null 요소 저장 불가
• 동기화 안 됨 (멀티스레드 환경에서는 PriorityBlockingQueue 사용)

기본 사용 예:

import java.util.PriorityQueue;

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

        pq.offer(30);
        pq.offer(10);
        pq.offer(20);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 10, 20, 30
        }
    }
}

PriorityQueue<String> pq = 
new PriorityQueue<>((a, b) -> b.length() - a.length()); // Comparator를 사용하여 사용자 정의 우선순위 지정

pq.offer("apple");
pq.offer("banana");
pq.offer("kiwi");

System.out.println(pq.poll()); // banana (가장 길이 김)

2. Deque (Double Ended Queue)

개요:

Deque는 양쪽 끝에서 삽입과 삭제가 가능한 큐다. 

Stack처럼도, Queue처럼도 사용할 수 있어서 유연성이 아주 높다.

대표 구현체: ArrayDeque, LinkedList

주의 : LinkedList가 이곳저곳에서 튀어나와서 헷갈릴 수 있다.

LinkedList는 특이하게 List와 Deque(Queue상속)를 둘 다 상속 받아 만들어진 클래스이다.

java.util.LinkedList<E> extends AbstractSequentialList<E>
                         implements List<E>, Deque<E>, Cloneable, Serializable

주요 메서드:

예제:

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        deque.offerFirst("Front");
        deque.offerLast("Back");

        System.out.println(deque.pollFirst()); // Front
        System.out.println(deque.pollLast());  // Back
    }
}

구현체  비교: