[자료구조] 덱(Deque)

[덱/데크]

양쪽에서 삽입과 삭제를 모두 처리할 수 있고, 스택과 큐의 특징을 모두 갖고 있는 것.

덱(Deque)는 Dobule-Ended Queue의 약자로, 큐의 FIFO와 스택의 LIFO를 모두 만족 시킬 수 있다.

자바에서 덱을 구현하는 Deque 자료형은 큐와 마찬가지! 인터페이스고, 큐를 확장해 정의되어 있다고 한다.

주로 사용하는 실제 구현은 LinkedLIst와 ArrayDeque로 할 수 있다고 한다.

동작

• addFirst(e) : 덱의 앞쪽에 요소를 추가한다.
• addLast(e) : 덱의 뒤쪽에 요소를 추가한다.
• removeFirst() : 덱의 앞쪽에서 요소를 제거하고 그 값을 반환한다.
• removeLast() : 덱의 뒤쪽에서 요소를 제거하고 그 값을 반환한다.
• peekFirst() : 덱의 앞쪽 요소를 조회한다.
• peekLast() : 덱의 뒤쪽 요소를 조회한다.

활용

• 탐색 알고리즘에서 작업 목록을 관리하거나, 최근 사용된 항목을 추적하는 캐싱 메커니즘에 사용할 수 있다.
• 양방향 삽입, 삭제를 활용해 양쪽에서 데이터를 추가하거나 제거해야 하는 시나리오에 유용하다.

효율성

• ArrayDeque는 동적 배열을 활용하여 구현되어, 배열의 크기 조정이 필요 없는 상황에서 빠른 접근 속도를 제공한다.
• LinkedLIst는 이중 연결 리스트를 기반으로 구현되어, 요소의 삽입과 삭제가 빈번히 발생하는 상황에서 더 효율적이다.

자바 Deque

 Deque<Integer> deque = new LinkedList<>(Arrays.asList(4, 5));
 
 //삽입
 deque.addFirst(3); // [3,4,5]
 deque.addLast(6); // [3,4,5,6]
 deque.offerFirst(2); // [2,3,4,5,6]
 deque.offerLast(7); // [2,3,4,5,6,7]
 
 //삭제
 deque.removeFirst(); // [3,4,5,6,7]
 deque.removeLast(); // [3,4,5,6]
 
 //조회
 System.out.println(deque.getFirst()); // 3
 System.out.println(deque.peekFirst()); // 3
 System.out.println(deque.getLast()); // 6
 System.out.println(deque.peekLast()); // 6