40. Queue - 큐, FIFO, 우선순위 큐

 

▶ 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 순으로 정렬된 상태로 출력됨.
		}
	}
}

[출력 결과]