[JAVA]Java에서의 Deque 소개

🖥️ 1. Java에서의 Deque 소개

Deque는 "double ended queue"의 약자로, 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 선형 컬렉션입니다. Java에서는 Deque 인터페이스를 통해 이 구조를 정의하고 있으며, 이는 java.util 패키지 안에 위치해 있습니다.

기본 작동 원리

Deque 인터페이스는 요소를 두 개의 끝에 추가하거나 제거할 수 있게 해주므로, 스택이나 큐의 기능을 모두 구현할 수 있습니다. 이러한 특성 덕분에 매우 유연한 데이터 구조로서 다양한 상황에서 활용될 수 있습니다.

스택처럼 사용할 때는 push(), pop(), peek() 메서드를 사용하고,
큐처럼 사용할 때는 addLast(), removeFirst(), peekFirst() 등을 사용합니다.

---

추가 메소드
- addFirst(E e): 데크의 앞쪽에 요소를 추가합니다. 공간이 없으면 IllegalStateException을 던집니다.
- addLast(E e): 데크의 뒤쪽에 요소를 추가합니다. 이 메소드는 add(E e)와 동일하게 동작합니다.
- offerFirst(E e): 데크의 앞쪽에 요소를 추가하며, 추가에 성공하면 true를 반환하고, 실패하면 false를 반환합니다.
- offerLast(E e): 데크의 뒤쪽에 요소를 추가합니다.

제거 메소드
- removeFirst(): 데크의 첫 번째 요소를 제거하고 반환합니다. 데크가 비어있으면 NoSuchElementException을 던집니다.
- removeLast(): 데크의 마지막 요소를 제거하고 반환합니다.
- pollFirst(): 데크의 첫 번째 요소를 제거하고 반환하며, 데크가 비어있으면 null을 반환합니다.
- pollLast(): 데크의 마지막 요소를 제거하고 반환하며, 데크가 비어있으면 null을 반환합니다.

조회 메소드
- getFirst(): 데크의 첫 번째 요소를 조회합니다. 데크가 비어있으면 NoSuchElementException을 던집니다.
- getLast(): 데크의 마지막 요소를 조회합니다.
- peekFirst(): 데크의 첫 번째 요소를 조회하며, 데크가 비어있으면 null을 반환합니다.
- peekLast(): 데크의 마지막 요소를 조회하며, 데크가 비어있으면 null을 반환합니다.

---

🛠️ 2. Java에서 Deque의 구현체

Java에서는 Deque 인터페이스를 여러 방식으로 구현하고 있습니다. 주요 구현체로는 ArrayDeque와 LinkedList가 있으며, 각각의 특성과 사용 케이스가 조금씩 다릅니다.

ArrayDeque

ArrayDeque는 배열을 사용하여 Deque의 요소들을 관리합니다. 이 구현체는 null 값을 허용하지 않으며, 내부적으로 동적 배열을 사용하여 요소들을 저장합니다.

• 장점: 배열을 사용하기 때문에 인덱스를 통한 빠른 요소 접근이 가능하며, 메모리 사용이 상대적으로 효율적입니다.
• 단점: 요소가 가득 찼을 때 배열 크기를 조정해야 하므로, 크기 조정 작업 중에는 성능 저하가 발생할 수 있습니다.

ArrayDeque deque = new ArrayDeque<>();  
deque.addFirst("Hello");  
deque.addLast("World");  
String first = deque.removeFirst(); // "Hello"  
String last = deque.removeLast(); // "World"  

LinkedList

LinkedList는 이중 연결 리스트를 사용하여 Deque의 요소들을 관리합니다. 각 요소는 앞뒤 요소와의 연결 정보를 포함하고 있습니다.

• 장점: 요소의 추가 및 제거가 빠르며, 양 끝에서의 작업은 상수 시간 내에 이루어집니다.
• 단점: 요소 접근 시에는 순차적 접근을 해야 하므로 인덱스로의 빠른 접근이 불가능합니다.

LinkedList deque = new LinkedList<>();  
deque.addFirst("Java");  
deque.addLast("Python");  
String first = deque.getFirst(); // "Java"  
String last = deque.getLast(); // "Python"  

---

📌 3. 정리

Java의 Deque 인터페이스는 스택과 큐의 기능을 합친 유연한 데이터 구조를 제공합니다. 주요 구현체인 ArrayDeque와 LinkedList는 각각의 상황에 따라 선택해서 사용할 수 있으며, 사용자의 요구에 맞게 효율적으로 데이터를 관리할 수 있습니다. 데이터의 추가 및 제거가 빈번한 애플리케이션에서는 LinkedList를, 빠른 접근이 필요한 경우에는 ArrayDeque를 사용하는 것이 좋습니다.