Deque — 양쪽에서 넣고 빼는 만능 자료구조

         ← 삽입/삭제                삽입/삭제 →
  front [  A  |  B  |  C  |  D  ] rear
         → 삽입/삭제                삽입/삭제 ←

import java.util.Deque;
import java.util.ArrayDeque;

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

// 앞에서 삽입/삭제
deque.addFirst("A");     // [A]
deque.addFirst("B");     // [B, A]
deque.removeFirst();     // B 반환, [A]

// 뒤에서 삽입/삭제
deque.addLast("C");      // [A, C]
deque.removeLast();      // C 반환, [A]

// Stack처럼 사용
deque.push("X");         // addFirst와 같음
deque.pop();             // removeFirst와 같음

// Queue처럼 사용
deque.offer("Y");        // addLast와 같음
deque.poll();            // removeFirst와 같음

// 조회 (제거하지 않음)
deque.peekFirst();       // 앞 요소 확인
deque.peekLast();        // 뒤 요소 확인

// ArrayDeque 내부 (간략화)
public class ArrayDeque<E> {
    Object[] elements;  // 원형 배열
    int head;           // 앞쪽 인덱스
    int tail;           // 뒤쪽 인덱스
}

인덱스: [0] [1] [2] [3] [4] [5] [6] [7]
데이터:  D   E   .   .   .   A   B   C
              ↑ tail     head ↑

Deque<String> deque = new LinkedList<>();
// 각 요소가 노드 객체로 할당됨
// 노드마다 prev, next 포인터 존재

배열: [1, 3, -1, -3, 5, 3, 6, 7], k = 3
결과: [3, 3, 5, 5, 6, 7]

// 매 윈도우마다 k개를 비교
for (int i = 0; i <= n - k; i++) {
    int max = Integer.MIN_VALUE;
    for (int j = i; j < i + k; j++) {
        max = Math.max(max, arr[j]);
    }
    result.add(max);
}

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // 인덱스를 저장

    for (int i = 0; i < n; i++) {
        // 윈도우 범위를 벗어난 요소 제거
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // 현재 값보다 작은 요소는 더 이상 최댓값이 될 수 없으므로 제거
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.addLast(i);

        // 윈도우가 완성된 시점부터 결과 기록
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

// ForkJoinPool 내부 동작 (개념적)
// 각 워커 스레드가 자신의 Deque에서 작업을 꺼냄
// 자신의 Deque가 비면 다른 스레드의 Deque 뒤쪽에서 작업을 "훔쳐옴"

ForkJoinPool pool = new ForkJoinPool();
pool.submit(() -> {
    // 이 작업은 특정 스레드의 Deque에 들어감
    // 해당 스레드가 바쁘면 다른 스레드가 이 작업을 가져갈 수 있음
});

// 0-1 BFS: Dijkstra 대신 Deque로 O(V + E)에 해결
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(start);

while (!deque.isEmpty()) {
    int u = deque.pollFirst();
    for (Edge e : graph[u]) {
        if (dist[u] + e.weight < dist[e.to]) {
            dist[e.to] = dist[u] + e.weight;
            if (e.weight == 0) {
                deque.addFirst(e.to);  // 가중치 0이면 앞에 추가
            } else {
                deque.addLast(e.to);   // 가중치 1이면 뒤에 추가
            }
        }
    }
}

// 요청 처리 순서 관리
@Component
public class RequestBuffer {
    // 최근 요청을 앞에, 오래된 요청을 뒤에서 제거
    private final Deque<Request> buffer = new ArrayDeque<>();

    public synchronized void addRequest(Request request) {
        buffer.addFirst(request);
        if (buffer.size() > MAX_SIZE) {
            buffer.removeLast(); // 오래된 요청 제거
        }
    }

    // 최근 N개 요청 조회
    public List<Request> getRecent(int n) {
        return buffer.stream().limit(n).collect(Collectors.toList());
    }
}

// 스레드 안전한 Deque가 필요할 때
Deque<String> safeDeque = new ConcurrentLinkedDeque<>();