[자료구조] 6. Java 큐 인터페이스(Queue)

Queue Interface

Queue는 '대기열'이라고 생각하면 된다. 흔히 리그오브레전드의 '큐 잡는다' 할때의 큐가 이 Queue를 의미한다.

큐는 스택과는 다르게 선입선출(First in First Out)의 구조를 가진다. 먼저 들어온 것이 가장 먼저 구조를 빠져나가는 것이다. 

보통 시간 순으로 작업이나 데이터를 처리할 때 사용하고 대표적으로 알고리즘에서 BFS(너비 우선 탐색)에 사용된다.

---

Queue Interface에 선언할 메소드

메소드	리턴 타입	설명
offer(E e)	boolean	큐의 마지막에 요소를 추가한다.
poll()	E	큐의 첫 번째 요소를 제거하고 제거된 요소를 반환한다.
peek()	E	큐의 첫 번째 요소를 제거하지 않고 반환한다.

 

큐 같은 경우는 실제로 자바에서도 6가지 밖에 선언이 되어있지 않다.

먼저 offer() 의 경우 리스트에서의 add() 와 비슷한 역할이고 poll() 의 경우는 remove()와 비슷한 역할이며 peek()은 element()와 비슷한 역할이다.

 

차이점은 add(), remove(), element()는 내부적으로 예외를 처리하고 있다.

예를 들어 index 밖을 넘어가거나, 메소드가 처리하려는 대상이 없는 등의 예외적 경우에 대한 처리를 해줬다.

 

하지만 offer(), peek(), element()의 경우 예외를 던지는 것이 아닌 특별한 값을 던지는데, 일반적으로 null 또는 false를 던진다.

 

/**
 * Java Queue Interface 이다.
 * Queue 는 ArrayQueue, LinkedQueue, Deque, PriorityQueue 에 의해 구현된다.
 *
 * @param <E> the type of elements in this Queue
 */

public interface QueueInterface<E> {
    /**
     * 큐의 가장 마지막에 요소를 추가한다.
     *
     * @param e 큐에 추가할 요소
     * @return 큐에 요소가 정상적으로 추가되었을 경우 true 를 반환
     */
    boolean offer(E e);

    /**
     * 큐의 첫 번째 요소를 삭제하고 삭제된 요소를 반환한다.
     *
     * @return 큐의 삭제된 요소 반환
     */
    E poll();

    /**
     * 큐의 첫 번째 요소를 반환한다.
     *
     * @return 큐의 첫 번째 요소 반환.
     */
    E peek();
}

 

큐의 구현은 배열과 연결리스트로 각각 구현하고 Deque의 경우 연결리스트로만 구현한다.

다음 포스팅에서는 ArrayQueue, LinkedQueue, Deque, PriorityQueue 클래스들을 구현할 것이다.