The Queue Interface

The Queue Interface

Queue는 엘리먼트를 저장한 순서대로 처리하는 작업을 수행하는 컬렉션이다. 기본 Collection 처리 내부에 큐는 추가적인 인서트 처리, 삭제, 검증 오퍼레이션을 제공한다. 큐 인터페이스는 다음과 같다.

public interface Queue<E> extends Collection<E> {

    E element();

    boolean offer(E e);

    E peek();

    E poll();

    E remove();

}

각 Queue메소드는 2개의 폼이 존재한다. 하나는 작업 실패에 한 예외를 던지는 것과, 다른 하나는 작업 실패시 특정 값을 반환하는 것이다. 특정값은 (null이나 false값, 혹은 처리에 대한 값)이 있다. 보통 다음 테이블에서 보여준 인터페이스가 주로 이용된다.

Queue Interface Structure

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

Queue는 일반적으로 FIFO의 방법에 따라 동작한다. 예외적으로 priorty queue가 있는데 이것은 그들의 값에 따라 순서를 정의하는 것이다. Object Ordering 을 보면 확인할 수 있다. 큐의 헤더는 remove나 poll메소드에 의해서 제거가 이루어 진다. FIFO 큐에서는 모든 입력 엘리먼트는 꼬리에 붙게 된다. 다른 종류의 큐에서는 서로 다른 위치에 특정 규칙에 따라 입력이 될 수 있다. 모든 Queue는 이러한 순서 규칙을 따라서 구현해야한다.

큐를 구현할때 큐가 가질수 있는 엘리먼트의 개수를 제약할 수 있도록 만들 수 있다. 그러한 큐가 바운드된 큐로 잘 알려져 있다. 몇몇 큐는 java.util.concurrent에서 구현되어 있으며, 이것은 바운드된 큐이이다. 그러나 java.util에는 구현되어 있지 않다.

add메소드는 Collection으로 부터 상속받았으며, 이것은 큐의 개수 제한에 대한 규칙을 준수하지 않게 되면, 이때에는 IllegalStateException이 발생하게 된다. offer메소드는  바운드된 큐로 구현되어 범위를 벗어나게 되는경우 false를 반환하게 된다.

remove와  poll메소드는 모두 큐의 헤더의 값을 제거하는데 사용된다. 정확하게 엘리먼트는 큐에 들어있는 정렬 순서대로 제거를 수행하게 된다. remove와 poll메소드는 큐가 비어 있을때 그 행동이 달라지며, remove는 큐가 비어있을때 수행된 경우 NoSuchElementException이 던져지며 poll은 널값이 반환된다.

element와 peek메소드는 값을 반환하되 엘리먼트를 제거하지는 않는다. remove와 poll과 동일하게 작용한다. 만약 큐가 비어있다면 element는 NoSuchElementException이 던져지고, peek는 널을 반환한다.

Quque는 일반적으로 null 엘리먼트를 입력하지 못하게 되어 있다. LinkedList 구현에서 구현된 큐는 이것을 예외적으로 개량한 형태이다. 전통적인 이유로, 이것은 널 엘리먼트를 허용하지만 가능하면 삼가하는것이 유리하다. 왜냐하면 null은 poll과 peek메소드의 특정 반환값으로 예약이 되어 있기 때문이다.

Quque는 equals과 hashCode메소드의 기본적인 버젼을 정의하고 있지 않다. 그러나 Objecty로 부터 지정된 equals과 hashCode로는 지정이 되어 있다.

Quque 인터페이스는 concurrent 프로그래밍에서  블로킹 큐 메시지를 지정하고 있지 않다. 이러한 메소드는 java.util.concurrent.BlockingQueue에 있는 인터페이스를 정의 할 수 있도록 해두고 있다.

다음 예제는 큐를 이용한 카운트다운 타이머이다. 큐는 모든 integer 값을 커멘드라인으로 부터 읽어 들여 저장하고, 이값을 역순으로 정렬한다. 그리고 매초당 헤더에 있는 값을 제거한다.

import java.util.*;



public class Countdown {

    public static void main(String[] args)

            throws InterruptedException {

        int time = Integer.parseInt(args[0]);

        Queue<Integer> queue = new LinkedList<Integer>();

        for (int i = time; i >= 0; i--)

            queue.add(i);

        while (!queue.isEmpty()) {

            System.out.println(queue.remove());

            Thread.sleep(1000);

        }

    }

}

다음 예제는 우선순위 큐로 엘리먼트의 컬렉션을 소트하여 이용하고 잇다. 이 프로그램은 Collection에서 제공되는 소트 메소드를 이용하지 않고 우선순위 큐를 이용하고 있다.

static <E> List<E> heapSort(Collection<E> c) {

    Queue<E> queue = new PriorityQueue<E>(c);

    List<E> result = new ArrayList<E>();

    while (!queue.isEmpty())

        result.add(queue.remove());

    return result;

}