[ JAVA ] Queue(큐)

1. Queue

▶ Queue는 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO(First In First) 구조이다.
▶ 큐는 Queue 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다.
    대신 Queue 인터페이스를 구현한 클래스들이 있어서 그중 하나를 선택해서 사용하면 된다. (예 : ArrayDeque, LinkedList 등..)
▶ 큐의 활용 예 : 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)

Queue<Element> q = new LinkedList<Element>(); // Element 타입으로 선언

FIFO(First In First Out)

2. Queue의 메서드

메서드	설 명
boolean add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true를 반환. 저장공간이 부족하면 IllegalStateException 발생
Object remove()	Queue에서 객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어 온다. peek와 달리 Queue가 비었을 때 NoSuchElementException 발생
boolean offer(Object o)	Queue에 객체를 저장. 성공하면 true, 실패하면 false를 반환
Object poll()	Queue에서 객체를 꺼내서 반환. 비어있으면 null을 반환
Object peek()	삭제없이 요소를 읽어 온다.  Queue가 비어있으면 null을 반환

3. PriorityQueue

▶ Queue 인터페이스의 구현체 중 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 반환된다.
▶ null은 저장할 수 없으며, null을 저장하면 NullPointException이 발생한다.
▶ PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장한다.
    ※ 힙(heap)은 이진 트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있다.
    ※ 자료구조 힙(heap) != JVM의 힙(heap)
▶ PriorityQueue의 시간 복잡도는 삽입, 삭제 시 O(logN)의 시간이 걸린다.

//int형 priorityQueue 선언 (우선순위가 오름차순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 내림차순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 오름차순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 내림차순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

3. Deque(Double-Ended Queue)

▶ Queue의 변형으로, Deque(덱, 또는 디큐)은 양쪽 끝에 추가/삭제가 가능하다.
▶ Deque의 조상은 Queue이며, 구현체로는 ArrayDeque과 linkedList 등이 있다.
▶ Deque은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다.

⭐️ Deque의 메서드에 대응하는 큐와 스택의 메서드

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()	-
peekLast()	-	peek()