[Java][Tutorial] 3-2. Collections: Queue, Deque, Map

The Queue Interface

• Queue는 처리를 위해 요소를 보관하는 컬렉션입니다.
• 기본적인 Collection 연산 외에도 추가적인 삽입, 삭제, 검사 연산을 제공합니다.

 

Key Features

기본연산

• add(e), offer(e) : 요소를 추가합니다.
• remove(), poll() : 큐의 앞쪽 요소를 제거하고 반환합니다.
• element(), peek(): 큐의 앞쪽 요소를 확인하되 제거하지 않습니다.

 

특징

• 큐는 대개 FIFO(First-In-First-Out) 방식으로 요소를 정렬하지만, 항상 그런 것은 아닙니다.
  • 우선순위 큐는 요소의 값을 기준으로 요소를 정렬합니다.
• add 메서드는 큐의 용량 제한을 위반할 경우 IllegalStateException을 던집니다.
  • offer 메서드는 용량 제한이 있는 큐에서만 사용하기 위한 것으로, 요소를 삽입하지 못했을 때 false를 반환합니다.
• LinkedList는 Queue를 구현하는 특별한 경우로, 이는 null 요소를 허용합니다.
  • null은 poll과 peek 메서드에서 특별한 반환 값으로 사용되므로 가능하면 null 요소를 추가하는 것은 피하는 것이 좋습니다.
• Queue 인터페이스는 동시 프로그래밍에서 자주 사용되는 블로킹 큐 메서드를 정의하지 않습니다.
  • 이러한 메서드들은 java.util.concurrent.BlockingQueue 인터페이스에 정의되어 있습니다.

static <E> List<E> heapSort(Collection<E> c) {
    Queue<E> queue = new PriorityQueue<E>(c);
    List<E> result = new ArrayList<E>();

    while (!queue.isEmpty())
        result.add(queue.remove());

    return result;
}

 

The Deque Interface

• Deque는 더블 엔디드 큐(double-ended-queue)를 나타냅니다.
• 선형 컬렉션으로 양쪽 끝에서 요소의 삽입, 제거, 조회를 지원하는 구조입니다.
  • Deque 인터페이스는 LIFO(Last-In-First-Out, 스택)와 FIFO(First-In-First-Out, 큐) 방식 모두로 사용할 수 있습니다.
  • 이를 통해 스택과 큐의 동작을 동시에 구현할 수 있습니다.
• ArrayDeque와 LinkedList와 같은 미리 정의된 클래스들은 Deque 인터페이스를 구현합니다.

 

Key Features

기본연산

인터페이스에 제공된 메서드들은 세 가지 부분으로 나뉩니다

 

• 삽입
  • addFirst(), offerFirst(): Deque의 시작 부분에 요소를 삽입합니다.
  • addLast(), offerLast(): Deque의 끝 부분에 요소를 삽입합니다.

 

• 제거
  • removeFirst(), pollFirst(): Deque의 시작 부분에서 요소를 제거합니다.
  • removeLast(), pollLast(): Deque의 끝 부분에서 요소를 제거합니다.

 

• 조회
  • getFirst(), peekFirst(): Deque의 시작 부분의 요소를 조회합니다.
  • getLast(), peekLast(): Deque의 끝 부분의 요소를 조회합니다.

 

The Map Interface

• 고유식별자로 객체를 검색할 수 있는 집합입니다.
• 각 entry는 key-value 형식의 쌍으로 저장됩니다.

 

Key Features

기본 연산

• put (추가)
• get (검색)
• remove (삭제)
• containsKey (특정 키의 존재 여부 확인), containsValue (특정 값의 존재 여부 확인)
• size (항목 수 얻기), isEmpty (맵이 비어 있는지 확인)

 

대량 연산

• putAll (한 맵에서 다른 맵으로 모든 매핑 복사)
• clear (모든 매핑 제거)

 

컬렉션 뷰

• keySet(): 모든 키의 집합을 반환합니다.
• values(): 모든 값의 컬렉션을 반환합니다.
• entrySet(): 모든 키-값 쌍의 집합을 반환합니다.

 

종류

HashMap

• 순서를 유지하지 않습니다.

 

TreeMap

• 키를 기반으로 순서를 유지합니다.

 

LinkedHashMap

• 삽입 순서를 유지합니다.

 

Object Ordering

Comparator

• 객체들의 순서를 정의하고 싶을 때 사용하는 인터페이스입니다.
• 객체들이 자연스러운 순서(Comparable 인터페이스에 정의된 순서)가 없거나, 다른 순서로 정렬하고 싶을 때 사용합니다.

public interface Comparator<T> {
    int compare(T o1, T o2);
}

compare 메서드

• 두 객체를 비교하여 정수를 반환하며 값이 작을수록 우선순위가 높습니다.
  • 작으면 음수, 같으면 0, 크면 양수
• 비교하려는 두 객체 중 하나가 Comparator에 적절하지 않은 타입이라면 ClassCastException이 발생합니다.

 

 

 

 

출처

• Java tutorial - Collections