`Queue interface`의 특징은 데이터를 일시적으로 저장하기 위한 자료구조 중 하나로, 선입선출(FIFO, Firs In First Out)의 특징을 가지고 있습니다. 가장 먼저 추가된 요소가 가장 먼저 제거됩니다. 자바에서 선입선출 리스트인 `Queue`는 `interface`입니다. 이 인터페이스를 구현한 클래스들을 알아보겠습니다.
LinkedList
PriorityQueue
ArrayBlockingQueue
LinkedBlockingQueue
ConcurrentLinkedQueue
아래의 3가지 클래스는 후에 Concurrent Collection에서 다시 소개드리고, 오늘은 `PriorityQueue` 에 대해 정리하겠습니다.
Queue
`Queue` 는 선입선출 리스트로 삽입 연산만 처리하는 `rear`와 삭제 연산만 처리하는 `front` 로 나눌 수 있습니다.
주로 버퍼나 메세지 큐에서 작업을 수행할 때 사용합니다.
Queue의 주요 메서드
메서드
설명
add(E e)
큐의 끝에 요소e를 추가합니다. 큐가 꽉 찼을 때 예외를 던집니다.
offer(E e)
큐의 끝에 요소e를 추가하며, 성공하면true, 실패하면false를 반환합니다.
remove()
큐의 첫 번째 요소를 제거하고 반환합니다. 큐가 비어 있을 경우 예외를 던집니다.
poll()
큐의 첫 번째 요소를 제거하고 반환합니다. 큐가 비어 있으면null을 반환합니다.
element()
큐의 첫 번째 요소를 반환하되, 제거하지는 않습니다. 큐가 비어 있을 경우 예외를 던집니다.
peek()
큐의 첫 번째 요소를 반환하되, 제거하지는 않습니다. 큐가 비어 있으면null을 반환합니다.
시간 복잡도
검색 :O(n)
삽입/삭제 :O(1)
💡 Big O 시간복잡도 -> 알고리즘의 성능을 나타내는 표기법 성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ)입니다
PriorityQueue
`PriorityQueue` 는 선입선출이 아닌 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.
동적 배열 기반 자료구조이며, 우선순위는 `default : 오름차순`입니다.
주로 운영체제의 작업 스케쥴링, Heap 정렬에서 사용합니다.
💡 힙 자료구조? 힙은 완전 이진트리 구조로 이루어져 있습니다. 여러 개의 값들 중에서 최대, 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다.
간단하게 오름차순 정렬은 최소힙, 내림차순 정렬은 최대힙을 사용합니다.
`PriorityQueue`는 배열 기반이지만, 힙 자료구조로 구현되어 있어 인덱스로 직접 요소를 꺼낼 수 없습니다.
중간 요소를 꺼내고 싶다면 배열을 순회하여 요소를 찾거나 해당 요소만큼 데이터를 꺼내야 합니다.
시간 복잡도
검색 :O(1)
삽입/삭제 :O(logN)
💡 Big O 시간복잡도 -> 알고리즘의 성능을 나타내는 표기법 성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ)입니다
Deque Collection
`Deque` 인터페이스는 앞, 뒤 모두 삽입, 삭제가 가능한 선형 자료구조입니다. `Queue`, `Stack`로 사용이 가능합니다.
주로 Undo/Redo 기능, 스레드 풀 관리 등에 사용합니다.
`Deque` 인터페이스를 구현한 클래스들을 알아보겠습니다.
ArrayDeque
LinkedBlockingDeque
`LinkedBlockingDeque` 역시 동시성 컬렉션 포스팅 부분에서 다시 알아보고, 이 포스팅에서는 `ArrayDeque`만 정리하겠습니다.
Deque
위의 설명과 마찬가지로 LIFO(Last In First Out), FIFO(First In First Out)이 모두 가능한 리스트입니다.
스택과 큐의 기능을 모두 포함한 자료구조기 때문에 메서드가 더 많습니다.
Deque의 주요 메서드
메서드
설명
addFirst(E e)
덱의 앞쪽에 요소를 추가합니다.
addLast(E e)
덱의 뒤쪽에 요소를 추가합니다.
offerFirst(E e)
덱의 앞쪽에 요소를 추가하며, 실패 시false를 반환합니다.
offerLast(E e)
덱의 뒤쪽에 요소를 추가하며, 실패 시false를 반환합니다.
removeFirst()
덱의 앞쪽 요소를 제거하고 반환합니다.
removeLast()
덱의 뒤쪽 요소를 제거하고 반환합니다.
pollFirst()
덱의 앞쪽 요소를 제거하고 반환하되, 비어 있을 때null을 반환합니다.
pollLast()
덱의 뒤쪽 요소를 제거하고 반환하되, 비어 있을 때null을 반환합니다.
getFirst()
덱의 앞쪽 요소를 반환하지만 제거하지 않습니다.
getLast()
덱의 뒤쪽 요소를 반환하지만 제거하지 않습니다.
peekFirst()
덱의 앞쪽 요소를 반환하지만 제거하지 않습니다.
peekLast()
덱의 뒤쪽 요소를 반환하지만 제거하지 않습니다.
push(E e)
덱의 앞쪽에 요소를 추가하며, 스택처럼 사용될 수 있습니다.
pop()
덱의 앞쪽 요소를 제거하고 반환하며, 스택처럼 사용될 수 있습니다.
시간 복잡도
검색/삽입/삭제 :O(n)
삽입 최악 시간 복잡도 : O(1)
💡 Big O 시간복잡도 -> 알고리즘의 성능을 나타내는 표기법 성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ)입니다
ArrayDeque
`ArrayDeque`는 배열 기반의 양방향 리스트입니다.
동적으로 크기를 조정하며 `Stack`으로도 `Queue`로도 사용할 수 있습니다. ArrayDeque는 `null`을 허용하지 않습니다.
또한, `Deque`의 모든 기능을 구현하며, `Stack`과 달리 동기화되지 않아 단일 스레드에서 성능이 우수합니다.
시간 복잡도
검색/삽입/삭제:O(1)
삽입 최악 시간 복잡도 : O(n)
💡 Big O 시간복잡도 -> 알고리즘의 성능을 나타내는 표기법 성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ)입니다
