덱(Deque)

1. 덱(Deque)이란?

- 덱은 Double-Ended Queue로 큐와 유사한 형태지만 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.

- 앞쪽과 뒤쪽 어느 쪽에서도 데이터를 추가하거나 제거할 수 있어 상황에 따라 스택과 큐로 활용가능하다.

- 슬라이딩 윈도우, 브라우저 히스토리 등의 알고리즘에서 활용된다.

 

2. 주요 메소드

- addFirst(E element): 맨 앞에 요소를 삽입한다.

- addLast(E element): 맨 뒤에 요소를 삽입한다.

Deque<String> deque = new ArrayDeque<>();

deque.addFirst("Apple"); // 맨 앞에 "Apple" 추가
deque.addLast("Banana"); // 맨 뒤에 "Banana" 추가

 

- removeFirst(): 맨 앞의 요소를 삭제한다.

- removeLast(): 맨 뒤의 요소를 삭제한다.

Deque<String> deque = new ArrayDeque<>();

deque.offer("Apple");
deque.offer("Banana");
deque.offer("Cherry");

deque.removeFirst() // 첫 번째 요소인 "Apple" 제거
deque.removeLast() // 마지막 요소인 "Cherry" 제거

 

- peekFirst(): 맨 앞의 요소를 조회한다.

- peekLast(): 맨 뒤의 요소를 조회한다.

Deque<String> deque = new ArrayDeque<>();

deque.offer("Apple");
deque.offer("Banana");
deque.offer("Cherry");

deque.peekFirst() // 첫 번째 요소인 "Apple" 조회
deque.peekLast() // 마지막 요소인 "Cherry" 조회

 

3. 활용 알고리즘

3-1. 회전 큐

- 회전 큐 문제는 덱을 이용하여 1~N까지의 값을 target에 주어진 순서대로 값을 제거할 때 회전 연산(왼쪽 또는 오른쪽) 횟수를 최소화하는 문제이다.

public class RotatingQueue {
	public static void main(String[] args) {
    	// 큐의 총 크기
        int N = 10;
        // 제거할 순서
        int[] targets = {2, 9, 5};
        
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 1; i <= N; i++) {
        	deque.offer(i);
        }
        
        int operation = 0; // 회전 연산 횟수
        
        for(int target : targets) {
        	// target의 인덱스 찾기
        	int index = 0;
        	for(Integer num : deque) {
           		if(num == target) {
                	break;
                }
                index++;
            }
        
            int size = deque.size();

            // target을 앞으로 이동시키기 위한 최소 회전 연산 결정
            if(index <= size / 2) {
                // 왼쪽 회전: index만큼 앞에서 뒤로 이동
                for(int i = 0; i < index; i++) {
                    deque.offerLast(deque.pollFirst());
                    operation++;
                }
            } else {
                // 오른쪽 회전: (size - index)만큼 뒤에서 앞으로 이동
                for(int i = 0; i < size-index; i++) {
                    deque.offerFirst(deque.pollLast());
                    operation++;
                }
            }

           	// target 제거
        	deque.pollFirst();
        }
        
        System.out.println(operation);
    }
}