ArrayDeque와 PriorityQueue 비교 (Java 17 기준)
ArrayDeque
선언
Queue deque = new ArrayDeque<>();특징
- 원형 배열로 이루어져 있고, 양방향 큐 또는 스택으로 사용할 수 있음.
- 동적 배열 기반으로 구현되어 있으며, 요소의 추가와 제거가 빠름.
- FIFO(First In First Out) 순서로 저장하고 관리함.
시간 복잡도
추가 : O(1)
deque.offer(obj););
deque.offerFirst(obj);
deque.offerLast(obj);삭제 : O(1)
deque.poll(obj););
deque.pollFirst(obj);
deque.pollLast(obj);조회 : O(1)
deque.peek(obj););
deque.peekFirst(obj);
deque.peekLast(obj);※ 헷갈렸던 점
Q. 원형으로 이루어져 있는데 어떻게 앞, 뒤가 존재하는지?
A. 원형 '배열'로 저장하기 때문에 큐와 스택을 모두 지원할 수 있다. 원형은 끝과 끝이 연결되어 있지만, 내부에서는 논리적으로 앞과 뒤를 추적하고 명확하게 제어할 수 있다.
Q. Queue<Integer> q = new ArrayDeque<>();로 선언했을 때와 Deque<Integer> q = new ArrayDeque<>();로 선언했을 때, 사용할 수 있는 메소드가 다른 이유
A. Queue Interface로 선언한 것과 Deque Interface로 선언한 것의 차이.
Queue로 선언하면 Queue 자료 구조 기본 동작을 지원하고, Deque로 선언하면, Queue와 Deque의 모든 메소드를 사용할 수 있기 때문에, offer, poll, peek 외에도 addFirst, addLast, removeFirst, removeLast, getFirst, getLast 등을 사용할 수 있음
Q. Deque의 앞쪽(헤드) 요소를 반환하는 q.element()와 q.getFirst()의 차이점
A.
...?
element()의 경우 queue가 비어 있을 경우, NoSuchElementException을 반환하지만, getFirst()의 경우 Exception을 반환하지 않고 null을 반환함
q.getFirst() 외에도 q.peek(), q.poll() 등 모두 null을 반환함
PriorityQueue
선언
Queue pq = new PriorityQueue<>();특징
Heap을 기반으로 구현되며, 우선 순위 큐, 최소 힙 등으로 불림- 요소의 추가와 제거는 우선순위 큐의 힙 조건을 유지하면서 이루어짐
- 우선 순위 요소가 가장 높은 요소가 항상 큐의 맨 앞에 위치함
- Integer, Double, String 등을 정렬할 수 있고, 필요한 경우 Comparator를 정의하여 정렬 기준을 바꿔서 사용할 수 있음
시간 복잡도
추가 : O(log n)
deque.offer(obj););삭제 : O(log n)
deque.poll(obj););
deque.pollFirst(obj);
deque.pollLast(obj);조회 : O(1)
deque.peek(obj););
deque.peekFirst(obj);
deque.peekLast(obj);ArrayDeque와 PriorityQueue의 사용 차이
- 정렬이 필요한 경우 PriorityQueue를 사용한다.
Reference
Oracle Java 17 ArrayDeque
Oracle Java 17 PriorityQueue
Chat GPT
