Collection & Map - 2. Queue & Deque
- 이번 시리즈에서는 Java의 Collection과 Map에 대해 소개합니다.
- 프레임워크의 기반이 되는 자료구조에 대한 개념은 따로 시리즈로 작성할 것이고, 본 시리즈에서는 Java에서 제공하는 자료구조들과 그에 따른 메서드들을 정리할 것입니다.
0. Java의 Collection Framework와 Map Interface
- Java에서는 데이터 구조와 알고리즘을 지원하는 강력한 표준 라이브러리를 제공하며, 이 중 Collection Framework와 Map은 데이터 관리와 처리의 핵심적인 역할을 합니다.
- 위 이미지는 주로 쓰이는 Collection Framework와 Map Interface의 상속 및 구현 관계를 제가 직접 그려본 것입니다.
- 회색으로 표시된
Vector, Stack, Hashtable은 Java 초창기에 만들어져서 하위 버전 호환을 위해 남겨진 Legacy Class들입니다.
- 구조적인 문제들이 있어서 현재는 더이상 업데이트되지 않고 거의 쓰이지 않기 때문에 본 시리즈에서도 따로 정리하진 않을 예정입니다.
- Collection Framework
- List 구현체 :
ArrayList, LinkedList
- Queue 구현체 :
PriorityQueue, ArrayDeque, LinkedList
- Deque 구현체 :
ArrayDeque, LinkedList
- Set 구현체 :
HashSet, LinkedHashSet, TreeSet
- Map Interface 구현체 :
HashMap, LinkedHashMap, TreeMap
- 이번 포스팅에서는 Collection Framework의 하위 인터페이스인
Queue와 Deque 인터페이스를 다루고, 두 인터페이스의 구현체 클래스인 ArrayDeque, LinkedList, PriorityQueue에 대해서 다룰 것입니다.
- 우선 가장 상위 클래스인
Queue 인터페이스를 살펴보도록 하겠습니다.
1. Queue Interface - 개요
Queue는 FIFO(First-In, First-Out) 구조를 따르는 컬렉션으로, 먼저 삽입된 요소가 먼저 삭제되는 방식으로 동작합니다.
Queue는 대기열, 작업 큐, 메시지 큐 등 순서에 맞춰 처리해야 하는 작업에서 주로 사용됩니다.- 데이터의 삽입과 제거가 주된 연산이므로, 시작 부분에서 요소를 제거하고 끝 부분에 요소를 삽입하는 데 최적화된 구조입니다.
1.1. Queue의 주요 특징
- FIFO 구조: 먼저 들어온 요소가 먼저 처리되는 구조로, 요소의 삽입과 삭제 순서가 일관되게 유지됩니다.
- 다만
PriorityQueue에서는 예외적으로 삭제시 삽입 순서에 관계없이 지정된 우선순위가 가장 높거나 낮은 데이터가 먼저 처리됩니다.
- 추가와 제거:
offer() 또는 add()를 사용해 큐의 끝에 요소를 추가하고, poll() 또는 remove()를 사용해 큐의 앞에서 요소를 제거합니다.
- 참고로
Collection에서 상속 받은 add()는 void 메서드이고, Queue 고유 메서드인 offer()는 boolean을 반환하는 메서드입니다.
- 큐가 비어있을 때 처리:
poll()은 큐가 비어있을 경우 null을 반환하며, remove()는 예외를 발생시킵니다.
1.2. Queue 주요 메서드
- 상위 인터페이스를 포함한 더 자세한 메서드들은 아래쪽(3번 파트)에서 다룰 예정이고, 아래 표는 Queue의 고유 메서드들을 간략하게 정리한 것입니다.
| 메서드 | 설명 | 반환값 |
|---|
| offer(E e) | 큐의 끝에 요소를 추가 | boolean |
| poll() | 큐의 앞에서 요소를 제거하고 반환 | E (null 반환 가능) |
| peek() | 큐의 앞에 있는 요소를 조회 (제거하지 않음) | E (null 반환 가능) |
| remove() | 큐의 앞에서 요소를 제거하고 반환 | E (예외 발생 가능) |
| element() | 큐의 앞에 있는 요소를 조회 (제거하지 않음) | E (예외 발생 가능) |
1.3. Queue의 주요 구현체
Queue에서는 하위 인터페이스인 Deque의 구현체들을 포함하여 대표적으로는 3개의 구현체가 있습니다.
LinkedList : 이중 연결리스트 기반의 Deque구현체이고, Queue로 의존성을 주입하여 사용할 수 있습니다.ArrayDeque : 배열 기반의 Deque구현체이고, Queue로 의존성을 주입하여 사용할 수 있습니다.PriorityQueue : Heap 자료구조 기반의 Queue를 직접 구현한 구현체입니다. 위 두 구현체와 비교하여 동작 방식의 차이가 있습니다. (우선 순위가 가장 높은 데이터가 먼저 출력되는 방식입니다.)
2. Deque Interface - 개요
Deque는 Double Ended Queue(양방향 큐)의 약자로, 양쪽 끝에서 요소를 추가하고 제거할 수 있는 자료구조입니다.
Deque는 FIFO와 LIFO(Last-In, First-Out) 두 가지 동작을 모두 지원하기 때문에, Queue뿐만 아니라 Stack으로도 활용할 수 있습니다.- Java에서
Deque는 Stack의 대안으로 사용되며, 양 끝에서의 삽입과 삭제가 필요한 작업에 최적화된 자료구조입니다.
2.1. Deque의 주요 특징
- 양방향 삽입/삭제:
Deque는 앞쪽과 뒤쪽 모두에서 요소를 삽입하거나 제거할 수 있습니다.
addFirst(), removeFirst()는 앞쪽에서, addLast(), removeLast()는 뒤쪽에서 요소를 처리합니다.
- 스택과 큐 모두로 활용 가능:
Deque는 스택처럼 LIFO 방식으로 사용할 수도 있고, 큐처럼 FIFO 방식으로 사용할 수도 있습니다.
- 이를 통해
Deque는 유연한 자료구조로, 다양한 상황에서 적합한 방식으로 사용될 수 있습니다.
- Null 값 금지:
Deque는 null 요소를 허용하지 않으며, null 값을 삽입하려고 하면 NullPointerException이 발생합니다.
2.2. Deque 주요 메서드
Deque 인터페이스는 Queue 인터페이스를 상속받기 때문에 Queue의 기능을 확장하여 양쪽에서의 삽입 및 삭제를 위한 메서드를 추가로 제공합니다.
추가 관련 Deque 고유 메서드
| 메서드 | 설명 | 반환값 |
|---|
| addFirst(E e) | 앞쪽에 요소를 추가 | void |
| addLast(E e) | 뒤쪽에 요소를 추가 | void |
| offerFirst(E e) | 앞쪽에 요소를 추가 (실패 시 false 반환) | boolean |
| offerLast(E e) | 뒤쪽에 요소를 추가 (실패 시 false 반환) | boolean |
| push(E e) | 앞쪽에 요소를 추가 (addFirst와 동일) | void |
삭제 관련 Deque 고유 메서드
| 메서드 | 설명 | 반환값 |
|---|
| removeFirst() | 앞쪽에서 요소를 제거하고 반환 | E (예외 발생 가능) |
| removeLast() | 뒤쪽에서 요소를 제거하고 반환 | E (예외 발생 가능) |
| pollFirst() | 앞쪽에서 요소를 제거하고 반환 (비어있으면 null 반환) | E (null 반환 가능) |
| pollLast() | 뒤쪽에서 요소를 제거하고 반환 (비어있으면 null 반환) | E (null 반환 가능) |
| pop() | 앞쪽에서 요소를 제거하고 반환 (removeFirst와 동일) | E (예외 발생 가능) |
조회 관련 Deque 고유 메서드
| 메서드 | 설명 | 반환값 |
|---|
| getFirst() | 앞쪽의 요소를 반환 (제거하지 않음) | E (예외 발생 가능) |
| getLast() | 뒤쪽의 요소를 반환 (제거하지 않음) | E (예외 발생 가능) |
| peekFirst() | 앞쪽의 요소를 조회 (제거하지 않음, 비어있으면 null 반환) | E (null 반환 가능) |
| peekLast() | 뒤쪽의 요소를 조회 (제거하지 않음, 비어있으면 null 반환) | E (null 반환 가능) |
2.3. Deque의 활용
Deque는 스택과 큐의 두 가지 역할을 모두 수행할 수 있기 때문에, 다양한 상황에서 활용될 수 있습니다.
- 큐처럼 사용: FIFO 방식으로 데이터를 처리해야 할 경우,
addLast()와 removeFirst() 메서드를 사용하여 Deque를 큐로 사용할 수 있습니다.
- 스택처럼 사용: LIFO 방식으로 데이터를 처리해야 할 경우,
addFirst()와 removeFirst() 메서드를 사용하여 Deque를 스택으로 사용할 수 있습니다.
- 참고로
Deque는 push()와 pop() 메서드도 함께 포함되어 있습니다.
import java.util.Deque;
import java.util.LinkedList;
public class DequeExample {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.addFirst("A");
deque.addFirst("B");
deque.addFirst("C");
System.out.println("스택처럼 사용 (LIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.removeFirst());
}
deque.addLast("1");
deque.addLast("2");
deque.addLast("3");
System.out.println("큐처럼 사용 (FIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.removeFirst());
}
}
}
2.4. Deque의 주요 구현체
Deque는 인터페이스로, LinkedList와 ArrayDeque가 대표적인 구현체입니다. 각 구현체는 내부 구조와 성능 특성에 차이가 있습니다.
LinkedList: 이중 연결 리스트 기반의 Deque 구현체로, 양쪽 끝에서의 삽입/삭제 성능이 뛰어납니다.ArrayDeque: 배열 기반의 Deque 구현체로, LinkedList보다 빠른 성능을 보이는 경우가 많고 메모리 오버헤드가 적습니다. 스택 또는 큐로 사용할 때 매우 효율적입니다.
3. Queue & Deque - 주요 메서드
- 주요 메서드는 상당히 많기 때문에 상위 클래스 및 인터페이스에서 부터 하위 인터페이스 순서로 메서드를 정리하고자 합니다.
3.1. Object & Iterable Interface 메서드
Object 메서드
Object 클래스는 모든 클래스의 최상위 클래스이므로, Queue와 Deque 구현체들도 이를 상속받습니다.
| 메서드 | 설명 | 반환값 |
|---|
| equals(Object obj) | 두 객체가 동일한지 비교 | boolean |
| hashCode() | 객체의 해시 코드를 반환 | int |
| toString() | 객체의 문자열 표현 반환 | String |
Iterable 메서드
Iterable 인터페이스는 모든 컬렉션이 구현해야 하며, 반복자를 생성하는 메서드가 포함됩니다.
| 메서드 | 설명 | 반환값 |
|---|
| iterator() | 컬렉션의 요소를 순차적으로 탐색할 수 있는 Iterator 반환 | Iterator<T> |
forEach(Consumer<? super T> action) | 각 요소에 대해 주어진 동작을 수행 | void |
| spliterator() | 요소의 분할 가능한 반복자를 반환 | Spliterator<T> |
3.2. Collection Interface 메서드
Collection 인터페이스는 List, Set, Queue, Deque 등 모든 컬렉션의 공통 메서드를 정의합니다.
| 메서드 | 설명 | 반환값 |
|---|
| add(T e) | 요소 추가 | boolean |
addAll(Collection<? extends T> c) | 주어진 컬렉션의 모든 요소를 추가 | boolean |
| remove(Object o) | 지정된 요소 삭제 | boolean |
removeAll(Collection<?> c) | 주어진 컬렉션에 있는 모든 요소를 삭제 | boolean |
retainAll(Collection<?> c) | 주어진 컬렉션에 있는 요소들만 유지 | boolean |
| size() | 컬렉션의 크기 반환 | int |
| isEmpty() | 컬렉션이 비어있는지 여부 확인 | boolean |
| contains(Object o) | 지정된 요소가 있는지 확인 | boolean |
containsAll(Collection<?> c) | 주어진 컬렉션의 모든 요소가 포함되어 있는지 확인 | boolean |
| clear() | 컬렉션의 모든 요소 삭제 | void |
| toArray() | 컬렉션의 요소를 배열로 반환 | Object[] or T[] |
3.3. Queue Interface 메서드
Queue 인터페이스는 Collection 인터페이스를 상속받아, 큐의 특성에 맞는 추가적인 메서드를 정의합니다.
| 메서드 | 설명 | 반환값 |
|---|
| offer(E e) | 큐의 끝에 요소를 추가 | boolean |
| poll() | 큐의 앞에서 요소를 제거하고 반환 | E (null 반환 가능) |
| peek() | 큐의 앞에 있는 요소를 조회 (제거하지 않음) | E (null 반환 가능) |
| remove() | 큐의 앞에서 요소를 제거하고 반환 | E (예외 발생 가능) |
| element() | 큐의 앞에 있는 요소를 조회 (제거하지 않음) | E (예외 발생 가능) |
3.4. Deque Interface 메서드
Deque는 Queue를 확장하여 양방향 큐의 삽입/삭제 기능을 추가로 정의합니다.
추가 관련 Deque 고유 메서드
| 메서드 | 설명 | 반환값 |
|---|
| addFirst(E e) | 앞쪽에 요소를 추가 | void |
| addLast(E e) | 뒤쪽에 요소를 추가 | void |
| offerFirst(E e) | 앞쪽에 요소를 추가 (실패 시 false 반환) | boolean |
| offerLast(E e) | 뒤쪽에 요소를 추가 (실패 시 false 반환) | boolean |
| push(E e) | 앞쪽에 요소를 추가 (addFirst와 동일) | void |
삭제 관련 Deque 고유 메서드
| 메서드 | 설명 | 반환값 |
|---|
| removeFirst() | 앞쪽에서 요소를 제거하고 반환 | E (예외 발생 가능) |
| removeLast() | 뒤쪽에서 요소를 제거하고 반환 | E (예외 발생 가능) |
| pollFirst() | 앞쪽에서 요소를 제거하고 반환 (비어있으면 null 반환) | E (null 반환 가능) |
| pollLast() | 뒤쪽에서 요소를 제거하고 반환 (비어있으면 null 반환) | E (null 반환 가능) |
| pop() | 앞쪽에서 요소를 제거하고 반환 (removeFirst와 동일) | E (예외 발생 가능) |
조회 관련 Deque 고유 메서드
| 메서드 | 설명 | 반환값 |
|---|
| getFirst() | 앞쪽의 요소를 반환 (제거하지 않음) | E (예외 발생 가능) |
| getLast() | 뒤쪽의 요소를 반환 (제거하지 않음) | E (예외 발생 가능) |
| peekFirst() | 앞쪽의 요소를 조회 (제거하지 않음, 비어있으면 null 반환) | E (null 반환 가능) |
| peekLast() | 뒤쪽의 요소를 조회 (제거하지 않음, 비어있으면 null 반환) | E (null 반환 가능) |
4. Queue 구현체 - PriorityQueue
4-1. PriorityQueue란?
PriorityQueue는 Queue 인터페이스를 구현한 클래스이며, 일반적인 큐와 달리 우선순위에 따라 요소가 처리되는 자료구조입니다.
- 기본적으로 최소 우선순위 큐(Min-Heap) 구조로 동작하며, 작은 값이 높은 우선순위를 가집니다.
- 기본적으로는 자연 순서를 따르며(숫자의 경우 오름차순, 알파벳의 경우 사전순), 특정
Comparator를 제공하여 사용자 정의 정렬 순서로 사용할 수 있습니다.
- 우선순위 큐의 내부 구현은 힙(Heap) 자료구조를 기반으로 하여, 요소의 삽입과 삭제가 이진 트리 형태로 관리됩니다.
- 참고로 힙(Heap) 자료구조는 메모리 Heap 영역과는 어원만 같을뿐 전혀 관련이 없는 자료구조에서의 용어입니다.
PriorityQueue 주요 특징
- 우선순위에 따라 요소가 처리됨:
PriorityQueue는 가장 먼저 추가된 요소가 아니라, 우선순위가 높은 요소가 먼저 처리됩니다.
- 즉, FIFO가 아닌 우선순위에 따라 처리되는 점이 일반 큐와의 차이점입니다.
- 힙 구조 기반: 내부적으로 이진 힙(Heap) 구조를 사용하여 요소를 정렬하고 관리합니다.
- 이로 인해 삽입과 삭제 연산의 시간 복잡도는
O(log n) 입니다.
- 자연 순서 또는 사용자 정의 정렬: 기본적으로 요소들은 자연 순서(
Comparable 구현을 따름)대로 정렬되지만, Comparator를 사용하여 사용자 정의 정렬 방식을 지정할 수도 있습니다.
- 동등한 우선순위: 동일한 우선순위를 가진 요소들은 순서가 보장되지 않으므로, 동일한 우선순위가 여러 개일 경우 결과는 예측할 수 없습니다.
4-2. PriorityQueue 사용 예시
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(10);
pq.offer(20);
pq.offer(15);
System.out.println("우선순위가 가장 높은 요소: " + pq.peek());
System.out.println("제거된 요소: " + pq.poll());
System.out.println("우선순위가 가장 높은 요소: " + pq.peek());
System.out.println("남은 요소들: " + pq);
}
}
우선순위 사용자 정의 (Comparator 사용)
- 기본적으로는 자연 순서(오름차순)에 따라 우선순위가 정해지지만,
Comparator를 통해 정렬 기준을 직접 정의할 수 있습니다.
- 예를 들어, 최대 우선순위 큐(큰 값이 높은 우선순위를 가짐)를 만들고 싶을 때는 다음과 같이 작성합니다.
import java.util.Comparator;
import java.util.PriorityQueue;
public class MaxPriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(20);
maxPQ.offer(15);
System.out.println("우선순위가 가장 높은 요소: " + maxPQ.peek());
System.out.println("제거된 요소: " + maxPQ.poll());
System.out.println("우선순위가 가장 높은 요소: " + maxPQ.peek());
}
}
4-3. PriorityQueue의 동작 방식 (Heap)
PriorityQueue는 힙(Heap) 자료구조를 기반으로 동작합니다. 힙은 완전 이진 트리의 일종으로, 최소 힙 또는 최대 힙의 구조로 유지됩니다.
- 최소 힙: 부모 노드가 자식 노드보다 작거나 같은 값을 가짐.
PriorityQueue의 기본 구현은 최소 힙입니다.
- 최대 힙: 부모 노드가 자식 노드보다 크거나 같은 값을 가짐.
Comparator를 사용해 최대 힙으로 만들 수 있습니다.
- 요소가 삽입될 때는 힙 성질을 유지하도록 이진 트리 구조에 따라 위치가 조정되고, 요소가 삭제될 때는 루트 노드에서 우선순위가 가장 높은 요소가 제거됩니다.
- 삽입/삭제 시에 새로운 요소가 삽입되거나 제거될 때마다, 부모/자식 관계를 확인하며 위치를 조정해 힙 구조를 유지합니다.
4-4. PriorityQueue의 주의점 및 사용 팁
- FIFO가 아님:
PriorityQueue는 일반적인 큐처럼 삽입 순서가 아닌 우선순위에 따라 요소가 처리됩니다. 따라서 순서를 보장해야 하는 작업에는 적합하지 않습니다.
- 동등한 우선순위: 동일한 우선순위를 가지는 요소들의 처리 순서는 보장되지 않습니다.
- Null 값 금지:
PriorityQueue는 null 요소를 허용하지 않으며, null 값을 삽입하려고 하면 NullPointerException이 발생합니다.
- 요소 순서 출력:
PriorityQueue는 내부적으로 힙을 사용하기 때문에, 큐의 전체 요소를 출력할 때는 순서가 보장되지 않습니다. 요소들은 정렬되지 않은 상태로 출력될 수 있습니다.
- 정확한 우선순위를 확인하려면,
poll()로 요소를 하나씩 꺼내며 확인하는 것이 필요합니다.
5-1. Deque 구현체 - LinkedList
5-1.1. LinkedList의 Deque 기능
LinkedList는 Deque 인터페이스를 구현한 대표적인 자료구조로, 양방향에서 삽입과 삭제가 가능합니다.
- 이중 연결 리스트(Doubly Linked List)를 기반으로 하여, 앞과 뒤 양쪽 끝에서 모두 빠른 삽입과 삭제가 가능합니다.
Deque 인터페이스를 통해 큐(Queue)와 스택(Stack) 두 가지 방식 모두로 활용할 수 있습니다.
Deque의 주요 동작 방식
- FIFO 방식으로 큐처럼 사용:
addLast()orofferLast()와 removeFirst()orpollFirst()를 통해 첫 번째 요소를 삭제하고 마지막에 요소를 추가하는 방식으로, 일반적인 큐처럼 사용할 수 있습니다.
- 큐 방식에서는
offerLast()와 pollFirst()를 더 권장합니다.
- LIFO 방식으로 스택처럼 사용:
addFirst()orpush()와 removeFirst()orpop()을 통해 마지막에 삽입된 요소를 먼저 제거하는 방식으로, 스택처럼 사용할 수 있습니다. (어떤걸 써도 무방하긴 합니다)
5-1.2. LinkedList를 이용한 Deque 사용 예시
import java.util.Deque;
import java.util.LinkedList;
public class DequeLinkedListExample {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.addLast("A");
deque.addLast("B");
deque.addLast("C");
System.out.println("큐처럼 사용 (FIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.removeFirst());
}
deque.addFirst("1");
deque.addFirst("2");
deque.addFirst("3");
System.out.println("스택처럼 사용 (LIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.removeFirst());
}
}
}
- 위 예제에서는
LinkedList를 Deque로 의존성을 주입하여 사용해서 큐(FIFO)와 스택(LIFO) 동작을 모두 구현했습니다.
5-2. Deque 구현체 - ArrayDeque
5-2.1. ArrayDeque란?
ArrayDeque는 배열 기반의 Deque 구현체로, 스택과 큐의 기능을 모두 효율적으로 지원합니다.
LinkedList와 비교하여 더 빠르고 메모리 오버헤드가 적은 특징을 가지고 있으며, 일반적인 스택과 큐의 대안으로 자주 사용됩니다.- Resizable 배열을 사용해 동적 크기 조절이 가능하며,
Deque의 기능을 효율적으로 수행합니다.
ArrayDeque 주요 특징
- 배열 기반:
ArrayDeque는 내부적으로 배열을 사용하여, 양방향에서의 삽입과 삭제가 상수 시간에 이루어집니다. (O(1) 시간 복잡도)
- 단, 배열의 크기가 꽉 찼을 경우에는 자동으로 배열 크기가 2배로 늘어나면서 복사가 이루어지기 때문에, 이 경우 성능 저하가 발생할 수 있습니다.
- 다만, 대부분의 경우 성능에 큰 영향을 미치지 않으며, 일반적으로 대규모 데이터를 처리할 때도 매우 효율적입니다.
- 참고로 원형 배열을 기반으로 만들어져 있는 자료구조이고, head와 tail의 인덱스 위치를 기반으로 삽입과 삭제가 이뤄진다는 특징이 있습니다.
- 빠른 삽입과 삭제: 앞뒤 양쪽에서의 삽입과 삭제가 모두 빠르게 이루어지므로, 큐와 스택 모두의 동작을 효율적으로 수행할 수 있습니다.
ArrayDeque는 스택(Stack) 대신 java.util.Stack 클래스의 대안으로 권장됩니다. (Stack의 동기화 메서드들때문에 Stack은 성능이 그렇게 좋지 못합니다.) LinkedList와 비교했을 때, 중간 삽입 및 삭제가 없는 경우에는 더 나은 성능을 보입니다. (다만 큐나 스택에서는 중간 삽입 과정이 있을 순 없어서 일반적으로 더 빠르다 생각하시면 됩니다.
- Null 값 금지:
ArrayDeque는 null 요소를 허용하지 않으며, null을 삽입하려고 하면 NullPointerException이 발생합니다.
- 고정 크기 없음: 크기가 고정된 큐와 달리,
ArrayDeque는 동적으로 크기가 조절되므로 더 유연하게 사용할 수 있습니다.
5-2.2. ArrayDeque 사용 예시
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeExample {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
deque.addLast("A");
deque.addLast("B");
deque.addLast("C");
System.out.println("큐처럼 사용 (FIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.removeFirst());
}
deque.addFirst("1");
deque.addFirst("2");
deque.addFirst("3");
System.out.println("스택처럼 사용 (LIFO):");
while (!deque.isEmpty()) {
System.out.println(deque.removeFirst());
}
}
}
- 위 예제에서
ArrayDeque는 큐(FIFO)와 스택(LIFO) 방식 모두를 유연하게 처리할 수 있습니다.
- 큐로 사용 시
addLast(), removeFirst() 메서드를 통해 FIFO 방식으로 동작합니다.
- 큐 방식에서는
offerLast()와 pollFirst()를 더 권장합니다.
- 스택으로 사용할 때는
addFirst(), removeFirst() 메서드를 통해 LIFO 방식으로 동작합니다.
- 마찬가지로
push(), pop()을 사용할 수 있습니다.
5-2.3. ArrayDeque 활용 팁
- 스택과 큐의 대체 구현체:
ArrayDeque는 스택과 큐 모두를 대체하는 강력한 구현체입니다.
java.util.Stack보다 성능이 우수하고, 동작 방식도 직관적이기 때문에 스택의 대체재로 권장됩니다.
- 동적 크기 조절:
ArrayDeque는 배열 기반으로 작동하지만, 자동으로 크기를 조절하기 때문에 데이터의 양에 맞게 유연하게 확장됩니다.
- 대규모의 데이터를 다룰 때도 메모리 오버헤드가 적고 성능이 우수합니다.
- 특정 작업에 유리
- 양 끝에서 빠르게 삽입 및 삭제가 필요할 경우, 특히 큐와 스택 모두를 다루는 상황에서 유리합니다.
LinkedList와 달리, 중간에 삽입하거나 삭제하는 작업은 적합하지 않지만, 양 끝에서의 작업이 빈번할 경우 ArrayDeque가 더 효율적입니다.
5-2.4. ArrayDeque와 LinkedList 비교
ArrayDeque와 LinkedList는 모두 Deque의 구현체로, 큐와 스택의 기능을 제공합니다. 하지만 두 클래스는 성능과 메모리 관리 측면에서 차이가 있습니다.
| 비교 항목 | ArrayDeque | LinkedList |
|---|
| 내부 구조 | 원형 배열 기반 | 이중 연결 리스트 기반 |
| 삽입/삭제 성능 | 앞뒤 삽입/삭제가 매우 빠름
(O(1), 단 배열 크기 증가 시 성능 저하) | 앞뒤 삽입/삭제가 빠름 (O(1)) |
| 메모리 오버헤드 | 배열 크기가 고정되어 있지 않고 유연하게 조정됨.
오버헤드 적음 | 각 노드가 추가 메모리를 사용 |
| 사용 시기 | 양 끝 삽입/삭제가 많을 때,
빠른 성능이 필요할 때 | 중간 삽입/삭제가 빈번할 때 |
| Null 값 허용 여부 | Null 값 허용 안 함 | Null 값 허용 |
마무리
- 이번 포스팅에서는
Queue와 Deque 인터페이스, 그리고 그 대표적인 구현체인 PriorityQueue, LinkedList, ArrayDeque에 대해 다루었습니다.
Queue는 FIFO(First-In, First-Out) 구조로 순서에 맞춰 작업을 처리할 때 사용되며, PriorityQueue는 Queue를 구현하긴 했지만 우선순위에 따라 처리되는 특별한 큐 구조로, 내부적으로 Heap(힙) 자료구조를 사용합니다.Deque는 양방향 큐로, 스택과 큐 두 가지 역할을 모두 할 수 있는 유연한 자료구조입니다. 대표적인 구현체로는 LinkedList와 ArrayDeque가 있으며, 양 끝에서 삽입과 삭제가 빈번한 작업에 유리합니다.
- 두 자료구조 모두 스레드 안전하지 않아서 멀티스레드 환경에서 사용할 경우 동기화가 필요할 수 있으며, 성능과 메모리 관리 측면에서 적합한 구현체를 선택하는 것이 중요합니다.
