Java Collection Framework - Collection interface - Queue

 

안녕하세요.

이전 시간에 이어 Collection Interface의 Queue를 배워보도록 하겠습니다. 

 

Queue 자료 구조는 대표적인 FIFO 형태로 먼저 들어온 원소가 가장 먼저 나가는 특징을 가지고 있는 자료 구조입니다. 

 

Queue의 구현체로는 양방향 큐라고 불리는 ArrayDeque, PriortyQueue 등이 존재합니다. 

 

 

제공되는 메서드로는 다음과 같습니다. 

 

그럼 우선 순위 큐에 대해 알아보도록 하겠습니다. 

우선순위를 가지는 Queue로 부여된 우선순위에 맞춰 정렬되어 반환 값을 제공합니다. 

우선순위를 지정하기 위해서는 compareTo 메서드를 통해 지정해주어야 합니다. 

 

대표적인 특징으로는 배열을 저장 공간으로 사용하고 힙 형태로 데이터를 저장한다는  것인데요.

이를 통해 우선순위 갱신이 빠르게 진행되고 가장 큰 값, 혹은 작은 값은 빠르게 찾을 수 있다는 장점이 존재합니다. 

 

 

우선순위를 지정하는 예제는 아래와 같습니다. 

 

class Student implements Comparable<Student> {
    String name; 
    int priority; 

    public Student(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
    @Override
    public int compareTo(Student user) {
      
        if (this.priority < user.priority) {
            return -1;
        } else if (this.priority == user.priority) {
            return 0;
        } else {
            return 1;
        }
    }

}

 

 

그럼 Deque에 대해 알아볼까요?

Deque는 양방향으로 삽입, 삭제가 가능한 자료구조를 의미합니다.

큐와 스택의 특징을 모두 가지고 있어 상황에 맞춰 큐 혹은 스택으로의 사용이 용이합니다. 

Deque의 조상은 Queue이며 구현체로 LinkdList, ArrayDeque가 존재합니다. 

 

 

그럼 구현체인 ArrayDeque를 확인해 보도록 하겠습니다. 

배열을 사용하여 구현되어 있기 때문에 스택의 사용 혹은 대기열로의 사용에서는 LinkedList보다 빠르다는 장점을 보여주고 있습니다. 

또한, 사이즈의 제한이 없으며 null 저장을 허용하지 않는다는 특징을 가지고 있습니다.

 

그럼 LinkedList는 어떤 상황에서 유리할까요?

Queue로의 구현 시 ArrayDeque 보다 성능이 좋습니다.

ArrayDeque의 경우 배열을 기반으로 하기에 앞의 데이터가 삭제됨에 따라 빈 공간을 채우기 위해 데이터의 이동이 빈번하게 이루어지기 때문입니다. 

 

 

큐 문제로는 아래 문제를 풀어보시면 이해가 빠를 것이라 생각합니다. 

https://www.acmicpc.net/problem/2075

 

Deque 관련 문제로는 아래 문제를 풀어보시면 이해가 빠를 것이라 생각합니다.

https://www.acmicpc.net/problem/10866

 

다음 포스팅에서는 Set에 대해 알아보도록 하겠습니다.