데큐(Deque)

데큐(Deque, Double-endend Queue)란?

데큐는 "Double-ended Queue"의 약자로, 큐의 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다. 일반적인 큐는 FIFO(First In First Out) 방식으로, 데이터를 한쪽 끝에서 삽입하고, 다른 한쪽 끝에서 데이터를 삭제합니다. 하지만 데큐는 양쪽 끝에서 모두 삽입 및 삭제가 가능하다는 점에서 유연성을 제공합니다. 이러한 특성 덕분에, 여러 상황에서 더 효율적이고 강력한 연산을 제공할 수 있습니다.

데큐의 주요 연산

• enqueueFront(item): 큐의 앞쪽에 데이터를 삽입
• enqueueBack(item): 큐의 뒤쪽에 데이터를 삽입
• dequeueFront(): 큐의 앞쪽에서 데이터를 삭제하고 반환
• dequeueBack(): 큐의 뒤쪽에서 데이터를 삭제하고 반환
• peekFront(): 큐의 앞쪽에서 데이터를 확인
• peekBack(): 큐의 뒤쪽에서 데이터를 확인
• isEmpty(): 큐가 비어 있는지 확인
• size(): 큐의 크기 확인

데큐의 특징

특징	설명
메모리 구조	선형 구조(배열 또는 연결 리스트 기반)
접근 방식	양쪽 끝에서 삽입 및 삭제 가능
삽입/삭제 속도	O(1) (양 끝에서 삽입과 삭제 모두 상수 시간이 걸림)
사용 예시	슬라이딩 윈도우, 문자열 회전, 양방향 큐 등

 

데큐 활용 예시

1. 슬라이딩 윈도우에서 최대값 찾기

- 주어진 배열에서 크기가 k인 슬라이딩 윈도우 내에서 최대값을 구하세요.

function maxSlidingWindow(nums, k) {
    const deque = [];  // 데큐 사용
    const result = [];
  
    for (let i = 0; i < nums.length; i++) {
        // 윈도우 범위를 벗어난 값 제거
        while (deque.length > 0 && deque[0] < i - k + 1) {
            deque.shift();
        }
      
        // 현재 값보다 작은 값들을 제거 (내림차순 유지)
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
      
        deque.push(i);  // 현재 인덱스를 데큐에 추가
  
        // 윈도우가 완성되면 최대값을 결과에 추가
        if (i >= k - 1) {
            result.push(nums[deque[0]]);  // 데큐의 첫 번째 인덱스는 최대값
        }
    }
  
    return result;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));  // [3, 3, 5, 5, 6, 7]

 

2. LRU 캐시 구현

• 캐시 크기가 capacity로 주어집니다.
• get(key)와 put(key, value) 연산을 처리해야 합니다.
• get(key) 연산은 키가 존재하면 값을 반환하고, 존재하지 않으면 -1을 반환합니다.
• put(key, value) 연산은 키가 이미 캐시 안에 있으면 값을 업데이트하고, 없으면 새로 삽입합니다. 캐시가 꽉 찬 경우, 가장 오래된 항목을 제거합니다.

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;  // 캐시의 최대 크기
        this.cache = new Map();     // 캐시 저장을 위한 맵
        this.order = [];            // 캐시 접근 순서를 저장하는 데큐
    }

    get(key) {
        // 캐시에서 키가 존재하지 않으면 -1 반환
        if (!this.cache.has(key)) {
            return -1;
        }

        // 캐시에서 키를 찾으면 가장 최근에 사용한 것으로 처리
        this._moveToFront(key);
        return this.cache.get(key);
    }

    put(key, value) {
        // 키가 이미 존재하면 값을 업데이트하고 가장 최근으로 처리
        if (this.cache.has(key)) {
            this.cache.set(key, value);
            this._moveToFront(key);
            return;
        }

        // 캐시 크기가 초과되면 가장 오래된 항목을 제거
        if (this.cache.size >= this.capacity) {
            const oldestKey = this.order.pop();  // 가장 오래된 키
            this.cache.delete(oldestKey);        // 해당 키 삭제
        }

        // 새로운 키를 삽입하고 가장 최근으로 처리
        this.cache.set(key, value);
        this.order.unshift(key);  // 가장 앞에 삽입
    }

    // 캐시에서 해당 키를 가장 최근으로 이동
    _moveToFront(key) {
        const index = this.order.indexOf(key);
        if (index !== -1) {
            this.order.splice(index, 1);  // 기존 위치에서 제거
        }
        this.order.unshift(key);  // 가장 앞에 추가
    }
}

// 사용 예시
const lruCache = new LRUCache(3);
lruCache.put(1, 1);  // 캐시: {1=1}
lruCache.put(2, 2);  // 캐시: {1=1, 2=2}
lruCache.put(3, 3);  // 캐시: {1=1, 2=2, 3=3}
console.log(lruCache.get(1));  // 1, 캐시: {2=2, 3=3, 1=1} (1을 가장 최근으로)
lruCache.put(4, 4);  // 캐시: {3=3, 1=1, 4=4}, 2가 삭제됨
console.log(lruCache.get(2));  // -1, 2는 캐시에서 삭제됨