[Java]Collection(3) - Queue, Deque

안녕하세요. List 컬렉션에 이어 Queue 컬렉션에 대해 알아보겠습니다.

 

[Java] Collection(2) - List

 

Queue Collection

---

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ⁿ)입니다

 

 

이렇게 Queue 컬렉션에 대해 알아보았습니다. 

도움이 되셨다면 공감 한 번 부탁드리며 잘못된 정보가 있다면 언제든 댓글 달아주세요!🪄

 

 

⬇️ 참고 URL

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://www.geeksforgeeks.org/heap-data-structure/?ref=header_outind

https://youngjinmo.github.io/2021/05/java-queue/