[Java 가지고놀기] Java Collections 정리(3) - Queue

callme.waffle·2024년 9월 15일

Java 가지고놀기

목록 보기
6/18

1. 개요

Java 문법을 복습하며 Collection 구현체들을 사용하는 것 자체에서 고민이 많았습니다.
조금이라도 효율적으로 구성해야하는 서버의 특성 상 자세히 그 특성을 알고 쓰고 싶은데, 그정도의 지식 깊이를 쌓지 못한 것 같습니다.
부족한 내용들을 다시 공부하였고, 나중에 까먹으면 다시 보기 위해 정리하였습니다.

#Reference

hihello님의 글
Joon님의 글, olrlobt님의 글
mxnzx님의 글
크네무의 개발상자

2. Queue란?

순서 O, 데이터 중복 O

Queue는 List처럼 순서와 데이터 중복을 허용하는 자료구조입니다.
List와 다른 특징이라면, 중간 특정위치에 다른 데이터를 추가하는 것이 불가하고,
입력은 무조건 tail(=끝), 출력은 무조건 head(=앞)에서만 가능합니다.

Interface 분석: Queue<T>

Queue에는 총 6개의 구현명세가 존재합니다.

유형MethodReturn설명
추가Queue.add( E element )trueelement를 추가합니다. 만약 추가가 가능한 경우 true를 return하고, 불가능한 경우 에러를 throw 합니다.
추가Queue.offer( E element )booleanelement를 추가합니다. 만약 추가가 가능한 경우 true를 return하고, 불가능한 경우 false를 return합니다.
조회Queue.element()Etail에 있는 element를 return합니다. 데이터가 존재하지 않으면 Exception(NoSuchElementException)을 throw합니다.
조회Queue.peek()Etail에 있는 element를 return합니다. 데이터가 존재하지 않으면 null을 return합니다.
삭제Queue.remove()Etail에 있는 element를 return하고 해당 요소를 삭제합니다. 데이터가 존재하지 않으면 Exception(NoSuchElementException)을 throw합니다.
삭제Queue.poll()Etail에 있는 element를 return하고 해당 요소를 삭제합니다. 데이터가 존재하지 않으면 null을 return합니다.

Interface 분석: Deque<T>

Deque는 'Double Ended Queue'의 약자로, Queue의 입/출력을 양방향으로 지원하는 것을 의미합니다.

List와 Queue를 반반 섞어놓은 것과 비슷하며, 실제로 LinkedList Class가 Deque Interface를 implement 합니다.

구현을 명시하는 메서드들은 다음과 같습니다:

  1. 양방향 Queue 메서드
    : 양방향으로 지원하는 Queue를 의미하다보니, Deque에는 Queue에 있는 모든 method를 각각 양방향으로 2개씩 구현하도록 되어있습니다.
    ex) Queue.offer -> Deque.offerFirst(), Deque.offerLast()

  2. 단방향 Queue 메서드
    : 물론, Deque는 Queue를 implement하므로 기존 Queue의 메서드들 또한 구현되어야 합니다. 따라서 Deque.offer()와 Deque.offerLast()는 동일한 역할을 합니다.
    실제로 ArrayDeque의 구현을 참고하면, Deque.offer()는 Deque.offerLast()를 호출합니다.

  3. Stack 메서드
    : Stack은 Vector기반의 구현체가 이미 존재하지만, 성능 및 동기화 문제로 인해 현재는 하위호환성 지원을 위한 목적으로만 사용합니다. 따라서 양방향 입출력이 가능한 Deque에 Stack관련 메서드 지원을 추가하여, Java에서는 Deque 구현체를 통해 Stack으로도 사용이 가능하도록 하였습니다.

이외에도 Collection을 implement하는 Queue의 특성을 따라 Collection Interface의 메서드들 또한 명시적으로 기재되어 있습니다.

3. 구현체 톺아보기

전체적인 구현체들의 상속관계는 다음과 같습니다

  • AbstractCollection (implements Collection) [Class(Abstract)]
    • AbstractQueue (implements Queue) [Class(Abstract)]
      • PriorityQueue (implements java.io.Serializable) [Class]
      • ArrayDeque (implements Deque, Cloneable, java.io.Serializable) [Class]

일반적인 Queue

PriorityQueue

특정시점에 최대/최소값 조회가 필요할 때 사용

일반적으로 FIFO 구조를 가지는 Queue의 특성과는 다르게, 각 element의 우선순위에 따라 출력순서가 정해지는 Queue입니다. 데이터를 추가할 때, 배열을 이진트리 형태로 이동하며 comparator로 값을 비교 후 결과에 따라 오름차순 정렬하여 저장합니다. (객체 내 shiftUp() method 사용)
상세내용은 이 포스트(작성예정)를 참고해주세요.

동작유형시간복잡도설명
추가O(log n) / O(n)이진트리형태로 값을 비교하여 저장위치를 고려하는 시간 소요 / 내부가 배열로 구현되어있어, 가용범위 초과 시 새로운 배열을 생성하여 값을 옮기는 경우 O(n) 소요
조회 - peek/elementO(1)-
조회 - containsO(n)내부 indexOf() method 이용, for문으로 순회하며 탐색
삭제 - poll/removeO(log n)위치로 이동 후 삭제 / 삭제된 값을 제외한 나머지값들의 위치를 조정하는 시간 소요

ArrayDeque

Stack / Queue 사용 시 범용적으로 사용

ArrayDeque는 Deque의 구현체로서 Stack과 Queue의 기능을 모두할 수 있는 구현체 입니다. Java에서도 사용을 권장합니다.
다만 Thread-safe하지 않아 멀티스레드 환경에서는 사용할 수 없고, PriorityQueue와 마찬가지로 배열을 사용하여 값을 저장합니다.
상세내용은 이 포스트(작성예정)를 참고해주세요.

동작유형시간복잡도설명
추가O(1) / O(n)내부가 배열로 구현되어있어, 가용범위 초과 시 새로운 배열을 생성하여 값을 옮기는 경우 O(n) 소요
조회 - peek/elementO(1)-
조회 - containsO(n)내부 indexOf() method 이용, for문으로 순회하며 탐색
삭제 - poll/removeO(1)-

동시사용이 가능한 Queue

는 나중에 채우도록 하겠습니다 ㅎㅎ..
(아직 공부중)

4. 자료구조 관점에서의 Queue구현체 사용

A) LIFO형태 자료구조 (ex: Stack)

Java에서는 Stack을 사용하기 위한 구현체로 ArrayDeque을 권장합니다.

이는 Stack 구현체가 Vector기반으로 구현되어 있는데, 이는 하위 호환성을 위해 존재할 뿐 다양한 문제점들이 있어 현재는 사용하지 않기 때문입니다.

허나 ArrayDeque에 구현되어있는 기능들을 사용한다면 Stack의 LIFO적 특성을 지원하는 것이 가능하므로 Stack이 필요한 경우 ArrayDeque을 사용합니다.

B) FIFO형태 자료구조 (ex: Queue)

결론부터 말하자면 ArrayDeque을 사용하는 것이 좋습니다.
LinkedList라는 선택지도 있는데, 그럼에도 ArrayDeque를 사용하는 이유는 메모리 사용량 차이입니다.

[메모리 관점]

LinkedList는 값을 저장하기 위해 앞뒤 값에 대한 정보를 함께 저장해야 하므로, 해당 정보를 함께 담을 수 있는 Node 객체로 감싸 값을 저장합니다.
반면 ArrayDeque은 값을 저장할 때 바로 배열에 저장하므로 감싸는 객체가 없습니다.

따라서 같은 개수를 저장할 때, ArrayDeque이 LinkedList보다 메모리를 덜 사용합니다.

[소요시간 관점]

LinkedList는 메모리에 저장되는 위치가 각자 다르기 때문에 접근하기 위해 비교적 오랜 시간이 소요됩니다.
반면 ArrayDeque은 다음 값이 항상 물리적으로 바로 다음에 위치해있으므로 접근하기 위해 비교적 적은 시간이 소요됩니다.

따라서 같은 항목에 접근할 때, ArrayDeque이 LinkedList보다 빠르게 접근할 수 있습니다.

5. 결론

Queue와 Deque에 대한 Interface를 공부해보았습니다.
새롭게 알게된건, LinkedList가 언제나 만능은 아니라는 것이었습니다.
상황에 따라 적절히 사용할 수 있는 연습이 필요할 것 같습니다.

profile
Developer waffle = new Waffle();

0개의 댓글