# 덱 (Deque)
정의
Deque(덱 혹은 데크)은 Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조(양방향 대기열)입니다.
- 덱은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택으로 사용할 수도 있고, 큐로도 사용할 수 있습니다.
- 특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 합니다.
# 데이터 삽입&삭제 속도
O(1)- 입구 데이터를 바로 삽입하고, 출구에서 바로 삭제(꺼내기)하면 됩니다.
# 데이터 탐색 속도
O(n)- 찾는 데이터가 존재하는지 투입된 순서대로 순차 검색이 필요합니다.
- 따라서 운이 안 좋으면 저장된 모든 값을 확인해야 할 수 도 있습니다.
# 자바에서의 Deque
Deque인터페이스이며, 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있습니다.
import java.util.Deque;
import java.util.ArrayDeque;
public class Sample {
public static void main(String[] args) {
// 덱 만들기
Deque<Integer> deque = new ArrayDeque<>();
// 값을 앞에 삽입
deque.offerFirst(1);
deque.addFirst(2); // 문제가 있으면 NullPointerException
// 값을 뒤에 삽입
deque.offerLast(5);
deque.addLast(3); // 문제가 있으면 NullPointerException
deque.add(4); // 문제가 있으면 NullPointerException
// 가장 앞의 값 찍먹하기
deque.peek();
deque.peekFirst();
deque.getFirst(); // 문제가 있으면 NullPointerException
deque.element(); // 문제가 있으면 NoSuchElementException
// 가장 뒤의 값 찍먹하기
queue.getLast(); // 문제가 있으면 NullPointerException
queue.peekLast();
// 값을 순서대로 삭제하기 (꺼내기)
deque.pollFirst();
deque.poll();
deque.removeFirst(); // 문제가 있으면 NoSuchElementException
deque.remove(); // 문제가 있으면 NoSuchElementException
// 값을 마지막부터 삭제하기
deque.pollLast();
deque.removeLast(); // 문제가 있으면 NoSuchElementException
}
}
