[Java] 자료구조 - Queue 인터페이스의 이해 및 사용법

1. Queue란

Queue란 FIFO(First In First Out)의 특성을 가지는 자료구조의 한 종류다.

Dequeue는 Queue의 front 부분의 저장된 데이터를 빼는 동작이고 Enqueue는 Queue의 rear부분으로 새로운 데이터를 추가하는 동작이다.

디큐가 발생할 때 마다 데이터는 한칸씩 front방향으로 미뤄져 front에는 가장 먼저 들어온 데이터가 있게 되고, 마찬가지로 enqueue 시에도 데이터가 한 칸씩 front 방향으로 밀린 후 들어오기 때문에 rear에는 가장 마지막에 들어온 데이터가 있게 된다. 이러한 방식으로 선입선출의 데이터 관리가 가능하다.

2. Java에서 Queue 인터페이스

Java에서 Queue의 인터페이스는 아래와 같은 패키지와 형태를 가진다.

package java.util.Queue;
// Interface Queue<E> queue

// 생성 : 인터페이스이기 때문에 클래스로 생성자를 지정해야 한다.
import java.util.Queue;
import java.util.LinkedList;
Queue<Integer> q = new LinkedList<Integer>();

Java에서 Queue 인터페이스의 메서드는 아래와 같다.

[출처: https://docs.oracle.com/javase/10/docs/api/java/util/Queue.html]

Enqueue 동작을 하는 메서드는 add()와 offer()이다. Description을 보면 add()는 capacity가 부족할 때 enqueue를 하면 IllegalStateException을 throw하고, offer()는 capacity 제안에 방해받지 않고, 용량이 넘치더라도 exception을 throw하지 않고 그냥 가능한 경우에만 enqueue를 하고 그렇지 않으면 하지 않는다는 점에서 차이를 가진다.

Dequeue를 하는 동작은 poll()과 remove()가 있다. 두 메서드 모두 Dequeue한 데이터를 반환한다. 그러나 poll()은 Queue가 비어있으면 null을 반환하고, 하지만 remove()는 Queue가 비어 있을 때 NoSuchElementException를 throw한다는 점에서 차이가 있다.

그 외에 element()와 peek()은 head의 데이터를 반환하지만 Dequeue 하지는 않는 동작이다. element()는 Queue가 비어있으면 NoSuchElementException을 throw 하지만 peek()은 그냥 null을 반환한다는 점이 다르다.

표로 정리해보면 아래와 같다.

따라서 저장용량이 제한된 Queue를 이용할 때는 offer, poll, peek을 이용하여 동작을 짜는 것이 더 낫다.

3. Java에서 Queue 인터페이스의 멤버, 메서드 활용 코드

위의 description을 적용하여 Queue 인터페이스를 LinkedList로 생성해서 메서드를 활용해 본 예제코드는 아래와 같다.

import java.util.Queue;
import java.util.LinkedList;
/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Queue<Integer> q = new LinkedList<Integer>();
        // offer를 통해 element인 Integer를 enqueue해주었다.
		q.offer(1);
		q.offer(2);
		q.offer(3);
        // peek은 아무리 해도 같은 값으로 나온다.
		System.out.println("peek: " + q.peek());
		System.out.println("peek: " + q.peek());
		System.out.println("peek: " + q.peek());
        // poll을 하니 dequeue가 이루어진다.
		System.out.println("poll: " + q.poll());
		System.out.println("poll: " + q.poll());
		System.out.println("poll: " + q.poll());
	}
}

References

Queue에 대한 이론적 설명: https://coding-factory.tistory.com/602

java.util.Queue: https://docs.oracle.com/javase/10/docs/api/java/util/Queue.html