[Java] 자료구조 - 큐(Queue)

1. 큐란

 

선입선출(First In First Out, FIFO) 방식의 자료구조입니다. 먼저 들어간 놈이 먼저 나온다는 뜻입니다.

21

32

13

24

54

16

즉, 위의 큐에서 삭제를 하면 21이 제거되고 새로운 값 16을 추가하면 54의 오른쪽에 저장됩니다.

 

2. Java 라이브러에서의 큐

 

Java에서는 Queue 인터페이스를 제공하고 있고, 이를 구현하는 클래스로는

AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue 가 있습니다. (https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html 참조)

이 중에서 LinkedList를 이용해서 queue를 구현해보도록 하겠습니다.

선언하는 방법은 다음과 같습니다.

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

 

3. 메서드

 

1) 삽입

queue.add(21);
queue.offer(21);

 

 add() 는 삽입에 성공하면 true를 반환하고, 큐에 빈 공간이 없을 경우 IllegalStateException을 던집니다.

 offer() 는 그냥 삽입만 합니다.

2) 삭제

result[0] = queue.poll();
result[1] = queue.remove();

 poll() 은 큐의 첫 번째 원소를 반환하고, 큐에서 해당 원소를 삭제합니다. 만약 큐가 비어있으면 null을 반환합니다.

 remove() 는 큐의 첫 번째 원소를 반환하고, 큐에서 해당 원소를 삭제합니다.

3) 조회

result[0] = queue.peek();
result[1] = queue.element();

 peek() 은 큐의 첫 번째 원소를 반환하되, 삭제하지는 않고 만약 큐가 비어있으면 null을 반환합니다.

 element() 는 큐의 첫 번째 원소를 반환하되, 삭제하지는 않습니다.

4) 기타

java.util.Collection 의 메서드(addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray)도 상속받으므로 사용할 수 있습니다.

queue.clear(); // 큐를 초기화
queue.isEmpty(); // 큐가 비어있는지 확인
queue.size(); // 큐의 크기
queue.contains(21); // 포함여부 확인

 

4. 예제

 

아래 프로그램은 필수과목 compulsory 와 학생의 수강계획서 plan 을 대조해서

필수과목이 수강계획서에 포함되어 있지 않거나, 순서가 다른 경우 0을 반환하고,

필수과목을 모두 순서대로 수강할 계획이라면 1을 반환합니다.

이 때 필수과목의 순서가 유지되어야 하므로 큐를 사용했습니다.

예를 들어 필수과목이 ABC 일 때,

학습계획이 AFBZCDE 라면 통과 / BDAEC 는 순서가 달라 탈락 / ABDEF 는 C가 빠졌으므로 탈락 입니다.

//입력
Scanner sc = new Scanner(System.in);
String compulsory = sc.next();
String plan = sc.next();

//필수과목을 큐에 추가
Queue<Character> queue = new LinkedList<>();
for(int i = 0; i < compulsory.length(); i++) {
    queue.add(compulsory.charAt(i));
}

//필수과목과 계획을 대조
char next = queue.remove();
for(int i = 0; i < plan.length(); i++) {
    if(plan.charAt(i) == next) {
        if(queue.peek() != null) next = queue.remove();
        else next = '\0';
    }
    if(queue.isEmpty() && next=='\0') break;
}

if(queue.isEmpty() && next=='\0') return 1;
else return 0;