Deque / PriorityQueue

PriorityQueue ?

- Queue 인터페이스 구현체 중 하나로 순서와 상관없이 우선순위가 높은 순으로 꺼내진다.

- 저장공간으로 배열을 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장
   ** 힙: 이진트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있는 특징이있다.
           : JVM 힙 영역 X

Queue pq =  new PriorityQueue();
pq.offer(3);
pq.offer(1);
pq.offer(4);
pq.offer(5);
pq.offer(2);

Object obj = null;
while((obj = pq.poll()) != null){
	System.out.println(obj);
}

//== 출력 결과 ==//
1
2
3
4
5

다음 출력결과에서도 볼 수 있듯이 숫자형에서는 수가 작은 것이 우선순위를 갖는다. 추가적으로 객체를 사용하거나 할 경우에는 우선순위를 결정할 수 있도록 방법을 제공해주어야한다.

 

Deque(Double - Ended Queue)?

- 기존에 큐는 한 쪽 방향으로 추가와 삭제가 가능했다면, 디큐(=덱)의 경우는 양 방향으로 추가 / 삭제가 가능하도록 큐를 향상시킨 구조이다.👉 큐/ 스택으로 상황에 따라 유연하게 사용할 수 있다.

- Deque(=인터페이스)의 조상은 Queue이며, 구현체로는 ArrayDeque와 LinkedList 등이 있다.

- 사용하기 위한 메서드는 아래와 같이 크게 어려지않고 나름 직관적이라고 생각한다.