덱(Deque)이란?
덱(Deque)이란 양끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서, 큐와 스택의 성질을 모두 가지고 있는 자료구조이다.
양쪽에서 모두 삽입과 삭제가 가능하기 때문에 First,Last로 앞에서 처리할지 뒤에서 처리할지를 결정 할 수 있으며 보다 자유롭게 사용이 가능한 큐라고 이해해도 무방하겠다.
중복 원소를 허용하며 크기 제한이 없는 것도 특징이다.
덱의 특징
덱은 기본적으로 큐이기 때문에, 큐처럼 구현체를 만들어 사용하여야 한다.
java.util.Deque 인터페이스를 구현한 클래스를 사용하면 되며 일반적으로는 ArrayDeque와 LinkedList를 사용한다.
덱의 주요 메서드는 다음과 같다.
- addFirst(E e) / offerFirst(E e): 덱의 맨 앞에 원소를 추가합니다. addFirst는 요소를 추가할 수 없는 경우 예외를 발생시키지만, offerFirst는 예외를 발생시키지 않고 실패 시 false를 반환합니다.
- addLast(E e) / offerLast(E e): 덱의 맨 뒤에 원소를 추가합니다. addLast는 요소를 추가할 수 없는 경우 예외를 발생시키지만, offerLast는 예외를 발생시키지 않고 실패 시 false를 반환합니다.
- removeFirst() / pollFirst(): 덱의 맨 앞에 있는 원소를 삭제하고 반환합니다. removeFirst는 덱이 비어있을 때 예외를 발생시키지만, pollFirst는 예외를 발생시키지 않고 실패 시 null을 반환합니다.
- removeLast() / pollLast(): 덱의 맨 뒤에 있는 원소를 삭제하고 반환합니다. removeLast는 덱이 비어있을 때 예외를 발생시키지만, pollLast는 예외를 발생시키지 않고 실패 시 null을 반환합니다.
- getFirst() / peekFirst(): 덱의 맨 앞에 있는 원소를 반환합니다. getFirst는 덱이 비어있을 때 예외를 발생시키지만, peekFirst는 예외를 발생시키지 않고 실패 시 null을 반환합니다.
- getLast() / peekLast(): 덱의 맨 뒤에 있는 원소를 반환합니다. getLast는 덱이 비어있을 때 예외를 발생시키지만, peekLast는 예외를 발생시키지 않고 실패 시 null을 반환합니다.
- remove(Object o): 주어진 원소 o를 덱에서 삭제합니다. 해당 원소가 여러 개 있으면 맨 앞에 있는 것만 삭제합니다.
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args){
//Deque의 선언
Deque<Integer> arr = new LinkedList<>();
//Deque의 삽입
arr.offerFirst(1);
arr.addFirst(1);
//Deque의 맨 앞 요소 반환
arr.peekFirst(); //삽입 실패시 false 반환
arr.getFirst(); //삽입 실패시 Exception 발생
//Deque의 맨 앞 요소 반환 및 제거
arr.pollFirst(); //비어있을 시 null 반환
arr.removeFirst(); //비어있을 시 Exception 발생
//Deque의 맨 뒷 요소 삽입
arr.offerLast(1); //삽입 실패 시 false 반환
arr.addLast(1); //삽입 실패 시 Exception 발생
//Deque의 주어진 원소 삭제
arr.remove(); //주어진 원소 삭제, 여러개가 있으면 맨 앞의 요소를 제거
}
}보다시피 First와 Last를 이용하여 입/출력을 앞에서부터 할지 뒤에서 부터 할지가 결정이 가능하다.
그만큼 사용이 용이하기 때문에 여러 곳에서 유용하게 사용할 수 있다.
ArrayDeque와 LinkedList
앞서 설명했듯이 Deque는 Queue처럼 구현체를 선택하고 사용하여야한다.
그럼 ArrayDeque와 LinkedList를 비교해 보고 어떤 장/단점이 있고 어떤 상황에서 무엇이 더 유리한 것인지 살펴보자.
1.ArrayDeque
ArrayDeque는 이름에서 알 수 있듯 배열을 기반으로 구현되어있다.
따라서, 임의의 인덱스에 빠르게 접근할 수 있으며 고정 크기 배열로 구현되어 일반적으로 메모리 사용량이 작다.
또한 단일 스레드 환경에서 사용하기 때문에 스레드 안정성을 고려할 필요가 없다.
다만, 배열 기반인 만큼 고정적인 크기를 가지기 때문에 동적으로 조절하기가 어렵고 크기 초과 시 새 배열을 생성하고 기존 데이터를 복사해야 한다는 단점이 있다.
2.LinkedList
LinkedList는 List기반인 만큼 동적으로 크기를 조절할 수 있다는 것이 가장 큰 장점이다.
또한, 노드 간의 연결만 수정하면 되기 때문에 중간에 요소를 추가하거나 제거 하는 경우 ArrayDeque 보다 처리가 빠르다는 장점이 있다.
단점은 우선 각 요소가 자체 노드를 가지고 있어 메모리 사용량이 높고 임의의 인덱스에 접근하는 경우 처음부터 순차적으로 탐색해야 하기 때문에 시간이 조금 더 오래 걸린다.
요약 하자면 요소의 추가 및 제거가 빈번하고 크기가 동적으로 변해야 하는 경우에는 LinkedList가 ArrayDeque보다 더 좋은 성능을 보인다.
하지만 임의의 위치에 빠르게 접근해야하고 굳이 동적으로 구현할 필요가 없다면 ArrayDeque가 더 좋은 선택지가 될 것이다.