▶ Queue 인터페이스
- 큐(Queue) : 데이터를 처리하기 전에 잠시 저장하고 있는 자료 구조이다.
- 전형적인 큐는 원소들을 FIFO(First-In-Fist-Out) 형식으로 저장하는 FIFO 큐인데, 후단(tail)에서 원소를 추가하고, 전단(head)에서 원소를 삭제한다. 새로운 원소들은 큐의 끝에 추가된다.
- 큐에서는 중간에 원소를 추가하는 것은 허용되지 않는다.
- 디큐는 자바 버전 1.6부터 Deque 인터페이스로 추가되었는데, 전단과 후단에서 모두 원소를 추가하거나 삭제할 수 있다.
- Deque 인터페이스는 ArrayDeque와 LinkedList 클래스들로 구현된다.
- Queue 인터페이스는 기본적인 Collection의 연산 외에 다음과 같은 삽입, 삭제, 검색, 연산을 추가로 제공한다.
public interface Queue<E> extends Collection<E> {
E element(); //큐의 처음에 있는 원소를 삭제하지 않고 가져온다. 큐가 비어있으면 예외발생
E peak(); //큐의 처음에 있는 원소를 삭제하지 않고 가져온다. 큐가 비어있으면 null을 반환
boolean offer(E e); //원소를 추가할 때 큐의 용량을 넘어서면 false를 반환한다.
E poll(); //큐의 처음에 있는 원소를 가져온다. 큐에 원소가 없으면 null을 반환한다.
E remove(); //큐의 처음에 있는 원소를 제거한다. 큐에 원소가 없으면 예외가 발생한다.
}
- 아래의 예제는 큐가 카운트 다운 타이머를 구현하는 예제이다.
import java.util.*;
public class QueueTest {
public static void main(String[] args) throws InterruptedException {
int time = 10;
// LinkedList 안에 Queue 인터페이스가 구현되어 있다.
Queue<Integer> queue = new LinkedList<Integer>();
for(int i = time; i > 0; i--) {
queue.add(i);
}
System.out.println("start time : " + System.currentTimeMillis() / 1000);
while(!queue.isEmpty()) {
System.out.println(queue.remove()+ " ");
Thread.sleep(1000); //현재의 스레드를 1초간 재운다.
}
System.out.println("end time : " + System.currentTimeMillis() / 1000);
}
}[출력 결과]
start time - end time = 10
- FIFO 큐가 전형적이지만 예외적인 큐도 존재한다. 원소들을 우선순위에 따라 저장하고 기본적인 우선순위는 원소들의 값으로 결정되는 우선순위 큐(Priority Queues)가 있다.
▶ 우선순위 큐(Priority Queue)
- 원소들이 무작위로 삽입되었더라도 정렬된 상태로 원소들을 추출한다.
- remove()를 호출할 때마다 가장 작은 원소가 추출된다.
- 우선순위 큐는 히프(heap)라고 하는 자료 구조를 내부적으로 사용하여 큐를 정렬한다.
히프는 이진 트리의 일종으로서 add()와 remove()를 호출하면 가장 작은 원소가 효율적으로 트리의 루트로 이동하게 된다.
오름차순으로 트리가 설정된다.
- 우선순위 큐의 가장 대표적인 예는 작업 스케쥴링(job scheduling)이다. 각 작업은 우선순위를 가지고 있고 가장 높은 우선순위의 작업이 큐에서 먼저 추출되어 시작된다.
- 아래는 우선순위 큐에 대한 예제이다.
import java.util.*;
public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.add(30);
pq.add(80);
pq.add(20);
for(Integer o : pq) {
System.out.println(o); // 20, 80, 30 순으로 출력됨
}
System.out.println("원소를 삭제합니다.");
while(!pq.isEmpty()) {
System.out.println(pq.remove()); //20, 30 80 순으로 정렬된 상태로 출력됨.
}
}
}
[출력 결과]
'Programming Language > JAVA' 카테고리의 다른 글
| 42. Collection Class - 컬렉션 클래스 (0) | 2017.07.24 |
|---|---|
| 41. Map, HashMap, TreeMap, LinkedHashMap (0) | 2017.07.24 |
| 39. Set, HashSet, TreeSet, LinkedHashSet - 집합 (0) | 2017.07.24 |
| 38. List interface, ArrayList, LinkedList, Vector - 리스트 인터페이스 (0) | 2017.07.23 |
| 37. Collection, Vector - 컬렉션, Vector 클래스, Collection 인터페이스 (0) | 2017.07.23 |
