[Java] Queue 인터페이스, PriorityQueue 클래스

wujin·2023년 5월 5일

Collection Java

Java Collection

목록 보기

3/5

`Queue<E>` 인터페이스

Java의 Queue 인터페이스는 컬렉션 프레임워크의 일부로, FIFO(First-In-First-Out, 선입선출) 방식의 요소 관리가 필요한 경우에 사용한다.

Queue 인터페이스를 구현한 주요 클래스에는 LinkedList, PriorityQueue, ArrayDeque 등이 있다.

LinkedList
- 이중 연결 리스트를 사용하여 큐를 구현
- Queue 인터페이스를 구현하므로, 큐로서 사용 가능
- 요소의 추가, 제거가 빠름
ArrayDeque
- 동적 배열을 사용하여 큐를 구현
- Deque(Double-Ended Queue)를 구현하여 양쪽 끝에서 요소를 추가 및 제거 가능
- 큐로서 사용될 때는 FIFO 순서를 따름
PriorityQueue
- 우선순위 힙을 사용하여 큐를 구현
- 요소의 자연 순서 또는 제공된 비교자를 사용하여 순서를 유지
- 요소의 추가, 제거가 논리적 순서에 따라 이루어짐

`Queue<E>` 인터페이스 메서드

Queue<E> 인터페이스는 큐 메모리 구조를 표현하기 위해, 다음과 같은 Collection 인터페이스 메서드만을 상속받아 사용한다.

boolean add(E e)
해당 큐의 맨 뒤에 전달된 요소를 삽입함. 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킴.
E element()
해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
boolean offer(E e)
해당 큐의 맨 뒤에 전달된 요소를 삽입함.
E peek()
해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
만약 큐가 비어있으면 null을 반환함.
E poll()
해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함.
만약 큐가 비어있으면 null을 반환함.
E remove()
해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거함.

예시

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
    	// 큐의 생성
    	LinkedList<String> qu = new LinkedList<String>();
		// Deque<String> qu = new ArrayDeque<String>();

        // add() 메소드를 이용한 요소의 저장
        qu.add("넷");
		qu.add("둘");
		qu.add("셋");
		qu.add("하나");

        // peek() 메소드를 이용한 요소의 반환
        System.out.println(qu.peek()); // 넷
		System.out.println(qu); // [넷, 둘, 셋, 하나]

        // poll() 메소드를 이용한 요소의 반환 및 제거
        System.out.println(qu.poll()); // 넷
		System.out.println(qu); // [둘, 셋, 하나]
        
        // remove() 메소드를 이용한 요소의 제거
        qu.remove("하나");
		System.out.println(qu); // [둘, 셋]
    }
}

`PriorityQueue<E>` 클래스

일반적인 queue는 먼저 들어간 데이터가 먼저 나가는 FIFO 형식의 구조이다. 반면에 우선순위 큐의 경우 들어가는 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

선언 방법은 아래와 같다.

// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>();
 
// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

`add()`와 `offer()`의 차이

boolean add(E e)
우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 OutOfMemoryError 예외 발생
boolean offer(E e)
우선순위 큐에 원소를 추가. 값 추가 실패 시 false를 반환

예시

import java.util.PriorityQueue;
 
public class Example {
    public static void main(String[] args) {
 
        // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
 
        pQ.offer(1);    // pQ에 원소 1 추가
        pQ.offer(6);    // pQ에 원소 6 추가
        pQ.offer(2);    // pQ에 원소 2 추가
        
        // pQ가 비어있면: true, 그렇지 않으면 : false
        while(!pQ.isEmpty()) {
            // pQ에 첫 번째 값을 반환하고 제거, 비어있다면 null 반환
            System.out.println("pQ.poll() = " + pQ.poll());
        }
    }
}

// pQ.poll() = 1
// pQ.poll() = 2
// pQ.poll() = 6