[Java Collection Framework] 3. Queue, PriorityQueue, Deque, ArrayDeque

2. Queue 인터페이스

: 데이터 처리를 하기 전 요소를 보관하도록 설계된 컬렉션

✅ 특징

1. 삽입, 추출, 검사 메소드 추가

- 기본 Collection 작업 외에도 추가 적인 메소드 제공
- 각 메서드는 두 가지 형식으로 존재(예외가 발생하는 것과 값을 반환하는 것으로 구분)

- 대기열은 일반적으로 FIFO(선입선출) 방식으로 요소를 정렬

- add, remove, element 메소드의 경우 값이 없으면 예외가 발생하나, offer, poll, peek은 false나 null 값을 반환

값이 없을 경우	예외 발생	값 반환(false or null)
삽입	add(e)	offer(e)
추출	remove()	poll()
검사	element()	peek()

2. null 값 추가 비허용

- Queue는 null 값의 삽입을 허용하지 않음(요소가 없다는 의미로 값을 반환하기 때문에 허용하지 않음)

3. equals와 hashCode 메소드는 identity-based

- Queue는 요소를 순서대로 저장하는 자료구조이기 때문에 같은 요소를 가지고 있어도 순서가 다르면 다른 Queue로 간주
  => element-based equality가 잘 정의되지 않는 경우가 많음
- 따라서 Queue가 동일 객체 인스턴스를 참조하는 경우에만 같은 Queue로 간주됨 (identity-based)

✅ 주요 메소드

Mdofier and Type	Method	Description
boolean	add(E e)	삽입이 가능하면 삽입 후 true, Queue의 한계 용량에 도달하여 추가할 수 없으면 예외 발생
E	element()	Queue의 head 값을 반환. 큐가 비어있을 경우 예외 발생
boolean	offer(E e)	삽입이 가능하면 삽입 후 true, 추가 할 수 없는 경우 false 반환
E	peek()	Queue의 head 값을 반환. 큐가 비어있을 경우 null 반환
E	poll()	Queue의 head 값을 꺼내서 반환. 큐가 비어있을 경우 null 반환
E	remove()	Queue의 head 값을 꺼내서 반환. 큐가 비어있을 경우 예외 발생

2-1. PriorityQueue 클래스

✅ 특징

1. Priority Heap을 통해 구현

- 이진 트리 구조를 기반으로 하여 부모 노드가 자식 노드보다 우선순위가 높은 완전 이진 트리 형태
- 루트 노드에 항상 우선순위가 가장 높은 요소를 두고, 이진 트리 속성을 이용해 요소를 추가하거나 삭제
- 삽입, 삭제에 모두 O(log n)의 시간 복잡도를 가짐

2. Comparator에 따라 우선순위를 기준으로 정렬

- head는 우선순위가 가장 높은 요소로, 큐의 연산인 poll, remove, peek, element는 큐의 head 요소에 접근함

3. Iterator() 메서드는 요소를 특정 순서로 탐색하지는 않음

- 우선순위 순서대로 접근해야 할 경우, 우선순위 큐의 요소를 배열로 변환하여 직접 정렬 후에 접근하는 것이 더 안전

4. 동기화되어 있지 않음

- 여러 스레드가 큐를 수정할 때는 PriorityBlockingQueue 클래스와 같은 스레드 안전한 클래스를 사용해야 함

2-2. Deque 인터페이스

: Double ended queue의 약어로 

✅ 특징

1. 시작과 끝 양쪽 방향에서 삽입/삭제/조회 가능

- 시작과 끝에서 데이터를 접근하기 위한 추가적인 메소드 가지고 있음

- Deque는 Queue의 FIFO 구조와 Stack의 LIFO 구조 모두 가지고 있음

- 기본 Queue에 있는 add 등의 메소드 사용시에는 Queue와 같이 동작함

2. Index로 접근 불가

3. null 요소 삽입 불가

- Deque가 비어있는지 아닌지를 알리기 위해 사용되기 때문에 null 요소 삽입은 금지

4. Doubly Linked List를 내부적으로 이용해서 구현

✅ 주요 메소드

구분	First Element Throws exception	First Element Special value	Last Element Throws exception	Last Element Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

2-3. ArrayDeque 클래스

✅ 특징

1. 스택 구조로 사용하면 스택보다 빠르고 큐 구조로 사용하면 LinkedList보다 빠름

- 내부적으로 배열을 이용하여 구현하기 때문에 더 높은 속도를 가짐

2. Thread-safe하지 않음

- 스레드 환경에서는 synchronized를 붙여서 동기화 할 수 있음

3. 용량에 제한이 없음

- 내부적으로 배열을 이용해 구현하는데, 초기 설정은 16 크기의 배열 생성

- 기본 용량을 초과하면 2배씩 용량을 증가시킴

 

🔽 공부하면서 생긴 의문

Q. ArrayDeque가 Array를 통해 구현되었는데 왜 인덱스로 접근은 불가한지?

ArrayDeque는 내부에서는 큐를 배열로 구현하고 있지만, 그 배열은 순환(circular) 배열로 구현되어 있습니다. 이는 배열의 시작과 끝이 연결되어 있어 마치 원형처럼 동작하도록 만들어진 것입니다. 이렇게 함으로써, 큐의 끝에 도달했을 때 배열의 시작 부분으로 다시 돌아가지 않고, 상수 시간에 큐의 양 끝에서 요소를 추가/제거할 수 있습니다. 이러한 구현 방식 때문에 index를 직접적으로 접근하는 것은 불가능합니다. 대신, 큐의 양 끝에서 요소를 추가/제거하거나, Iterator를 사용하여 요소에 접근할 수 있습니다.

예상 면접 질문

Q. Deque를 LinkedList로 구현하는 것과 ArrayDeque로 구현하는 것 중 어떤 것이 더 좋은지?

JavaDocs 기준 ArrayDeque이 더 빠르다고 함
[ 이유 ]

1. ArrayDeque는 Array에 의해 구현되어 있으므로 cache-locality에 좀 더 친숙
(LinkedList는 다음 노드가 있는 곳으로 가기 위해 간접적인 경로를 거쳐감)

2. ArrayDeque는 다음 노드에 대한 추가 참조를 유지할 필요가 없어 메모리 효율적

 

하지만 배열의 삽입 삭제가 빈번하지 않고 양 끝에서만 삽입 삭제 연산이 일어난다면 리스트와 큰 차이 없음

Q. Stack과 Queue의 실사용 예를 들어 간단히 설명해주세요.

1. Stack
- 자바의 Stack 메모리 영역
- 지역변수와 매개변수 데이터 값이 저장되는 공간으로 메소드 호출시 메모리에 할당되고 종료되면 메모리가 해제되며 LIFO 구조를 가짐
2. Queue
- OS의 스케줄러
- 자원의 할당과 회수를 하는 스케줄러 역할
- 메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 순서 결정하는 데 가장 단순한 스케줄링 정책이 FIFO