Java Collections Framework(JCF)란? - Queue와 Deque (JAVA)

안녕하세요? 제이온입니다.

 

오늘은 Queue와 Deque 인터페이스를 알아보겠습니다.

 

 

Queue Interface

Queue 인터페이스는 FIFO 구조를 가진 자료구조입니다. 먼저 들어온 요소가 먼저 나가는 방식으로, 메소드는 총 6가지가 존재합니다.

 

 

 

 

요소를 추가하는 메소드는 add()와 offer(), 요소를 제거하는 메소드는 poll()과 remove(), 맨 처음 요소를 반환하는 메소드는 peek(), element()가 있습니다. 그리고 주로 offer(), poll(), peek()을 사용합니다. 왜냐하면, 이들 외의 나머지 메소드는 큐가 비어있을 경우 .NoSuchElementException을 내뱉기 때문이죠.

 

 

 

 

Enqueue는 요소를 맨 뒤에 추가하는 것을 말하며, Dequeue는 맨 앞에 있는 요소를 제거하는 것을 말합니다.

 

 

Queue Interface와 LinkedList Class

흔히 Queue를 생성할 때는 다음과 같이 생성합니다.

 

 

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

 

 

이것은 LinkedList가 Queue 인터페이스를 상속받았기때문이며, 결국 Queue는 자식 클래스인 LinkedList를 이용하여 구채화됩니다. 그렇다면, 여기서 의문이 하나 생길 수 있습니다. 왜 ArrayList가 아닌 LinkedList일까요?

 

그것은 LinkedList에서 추가, 삭제 시간복잡도가 O(1)이기때문입니다. 엥? O(N)이 아니냐고요? 물론, 일반적인 상황에서 LinkedList는 추가나 삭제할 데이터를 탐색하는 시간까지 합쳐서 O(N)이 맞지만, 위치를 알고 있을 경우 O(1)입니다.

 

Queue의 동작 방식은 요소를 추가할 때 맨 뒤에 요소를 추가하고, 삭제할 때 맨 앞의 요소를 제거하므로 연산에서 시간복잡도는 O(1)이 되는 것이죠. 맨 앞의 요소를 반환하는 경우도 마찬가지입니다.

 

ArrayList도 맨 뒤에 요소를 추가하는 것은 O(1)이지만, 삭제하는 과정은 맨 앞의 요소를 삭제하는 것이므로 그 뒤에 있는 요소를 싹다 한 칸씩 왼쪽으로 밀어야하므로 O(N)이 됩니다.

 

이러한 이유로 Queue는 LinkedList를 이용하여 생성합니다.

 

흥미로운 점은 여기서 Queue는 LinkedList와 다름없어서 LinkedList에 있는 contains()나 stream() 메소드도 호출하여 사용할 수는 있습니다.

 

 

PriorityQueue Class

흔히 우선순위 큐라고 불리는 클래스입니다. Queue 인터페이스를 상속받았으며, 일반적인 Queue와는 다른 특징을 띕니다. 우선순위 큐는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 요소가 먼저 나가는 자료구조입니다. 

 

우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이며, 요소를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성합니다. 그리고 요소를 꺼낼 때 루트 노드를 얻어낸 뒤, 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다.

 

메소드는 Queue에서 정의한 6가지 메소드를 모두 사용할 수 있고, Collection 인터페이스도 상속을 받았으므로 그 안의 메소드도 활용이 가능합니다. 그래도, 일반적으로는 offer(), poll(), peek(), isEmpty() 정도만 쓰는 편입니다.

 

그렇다면, 이 우선순위를 어떻게 정할까요? 만약, 우선순위 큐에 들어갈 요소가 Integer, Double, String, Character와 같은 경우, 따로 Comparator을 설정하지 않으면 정렬 기준이 오름차순이 됩니다. 하지만, Car와 Bus와 같이 개발자가 따로 만들어 둔 객체를 우선순위 큐에 바로 넣으면 정렬 기준이 없어서 .ClassCastException이 발생합니다. 따라서, 해당 객체 안에 Comparable을 상속받아서 compareTo를 정의해 주거나, 정렬 기준을 Comparator을 사용하여 정해줘야합니다.

 

단, 우선순위 큐는 null 요소는 저장이 불가합니다.

 

 

Deque Interface

Deque는 Double-Ended Queue의 약어로, Queue의 양쪽 끝에서 추가와 삭제가 일어날 수 있는 자료구조입니다. 사용 방식에 따라 Stack이 될 수도 있고 Queue가 될 수도 있습니다. 저번 포스팅에서 말했듯이, Stack을 구현할 때는 이 Deque를 사용해야합니다.

 

 

 

 

기본적으로 Queue를 상속받고 있으나 Deque만 가지고 있는 일부 메소드가 있습니다.

 

 

 

 

앞서 말했듯이, 양쪽이 뚫려있는 구조라서 앞에 요소를 추가할 수도 있고, 뒤에 요소를 삭제하는 등 추가와 삭제가 Qeueu에 비해 비교적 자유롭습니다.

 

 

 

 

Deque는 Queue의 메소드를 모두 가지고 있습니다. 위 사진은 Queue 메소드와 Deque에서 새롭게 정의한 메소드를 비교하고 있습니다. Queue의 add(e)와 Deque의 addLast(e)는 같다고 말하고 있는 것이죠.

 

 

 

 

Deque는 Stack의 메소드도 모두 가지고 있습니다. 위 사진은 Stack 메소드와 Deque에서 새롭게 정의한 메소드를 비교하고 있습니다. Stack의 push(e)와 Deque의 addFirst(e)는 같다고 말하고 있는 것이죠.

 

참고로, 각각의 메소드의 시간복잡도는 모두 O(1)입니다.

 

Deque의 구현 클래스는 ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList이 있는데, 주로 ArrayDeque를 사용하는 편입니다.

 

 

ArrayDeque Class

ArrayDeque 클래스는 Deque 인터페이스를 상속받아서 사용하는 구현 클래스입니다. ArrayDeque는 사이즈 제한이 없는 가변 배열이며 (단, 처음부터 사이즈가 무한대인 것은 아니고 초기 사이즈 16에서 2배씩 늘려나갑니다), null 요소는 저장할 수 없습니다. 또한, 비동기 방식이라서 멀티 쓰레드 환경에서는 어울리지 않다는 특징이 있습니다. 마지막으로, ArrayDeque는 Stack 목적으로 구현하였을 때 기존의 Stack보다 빠르고, Queue 목적으로 구현하였을 때 LinkedList보다 빠릅니다.

 

여기서 Stack은 저번 포스팅에서 말했듯이, 대부분의 메소드에 덕지 덕지 동기화 처리가 되어있는 Vector를 상속하므로 Stack을 사용하는 것보다 ArrayDeque를 통해 Stack을 사용하는 편이 더 성능이 좋습니다.

 

그렇다면, Queue를 목적으로 ArrayDeque를 사용하면 왜 기존 구현 클래스인 LinkedList보다 빠를까요?

 

먼저, LinkedList로 구현한 Queue의 경우, 맨 마지막 요소를 추가할 때 새로운 노드를 만들고 이전 노드와 새로운 노드의 주소를 가리키는 등 여러 가지 작업이 필요합니다.

 

하지만, ArrayDeque로 구현한 Queue의 경우, 단순히 arr[tail] = e와 같이 마지막 인덱스에 해당하는 값에 요소를 할당해 주면 됩니다. 그리고 사이즈가 꽉찼다면, 2배로 늘리면 되는 것입니다.

 

단, 항상 ArrayDeque가 바람직한 것은 아닙니다. 만약, 저장해야할 데이터의 양이 방대하다면 ArrayDeque의 사이즈를 계속 2배씩 늘려야하므로 이때는 LinkedList가 더 낫습니다. 하지만, 일반적인 경우 Queue를 목적으로 ArrayDeque를 사용할 때가 성능이 더 좋습니다.

 

 

ArrayDeque의 시간복잡도

ArrayList의 경우, remove(0)을 할 때 시간복잡도가 O(N)이라고 설명한 적이 있습니다. 그런데, ArrayDeque도 어쨌든 가변 배열인데, removeFirst()가 어떻게 시간복잡도가 O(1)인지 궁금증이 생겼습니다. 구글링을 해 보니, ArrayDeque는 원형 큐 방식으로 구현이 되어있었기 때문에 시간복잡도가 O(1)인 것을 알게 되었습니다. 자세한 구현 과정은 이곳을 참고하시길 바랍니다.

 

 

정리

지금까지 Queue와 Deque 인터페이스를 알아보았습니다. 다음 시간에는 Set 인터페이스를 설명하겠습니다.

 

 

출처

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

 

 

ArrayDeque (Java Platform SE 8 )