Deque

덱(deque, double-ended queue)은 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 자료구조로, 큐와 스택을 합친 형태이다.

코드 예시

// 간단한 함수형 Deque
type Deque<T> = T[]; // 덱을 배열 타입으로 정의, T는 제네릭 타입 매개변수

// 덱의 앞쪽에 요소를 추가하는 함수
const addFront = <T>(deque: Deque<T>, item: T): Deque<T> => 
  [item, ...deque]; // 새 요소를 맨 앞에, 기존 배열을 스프레드로 뒤에 붙임

// 덱의 뒤쪽에 요소를 추가하는 함수  
const addRear = <T>(deque: Deque<T>, item: T): Deque<T> => 
  [...deque, item]; // 기존 배열을 스프레드로 앞에, 새 요소를 맨 뒤에 붙임

// 덱의 앞쪽 요소를 제거하는 함수
const removeFront = <T>(deque: Deque<T>): [T | undefined, Deque<T>] => 
  [deque[0], deque.slice(1)]; // [제거된 첫 번째 요소, 첫 번째 제외한 나머지 배열]

// 덱의 뒤쪽 요소를 제거하는 함수
const removeRear = <T>(deque: Deque<T>): [T | undefined, Deque<T>] => 
  [deque[deque.length - 1], deque.slice(0, -1)]; // [마지막 요소, 마지막 제외한 배열]

// 덱의 앞쪽 요소를 확인만 하는 함수 (제거하지 않음)
const peekFront = <T>(deque: Deque<T>): T | undefined => 
  deque[0]; // 첫 번째 요소 반환, 빈 배열이면 undefined

// 덱의 뒤쪽 요소를 확인만 하는 함수 (제거하지 않음)
const peekRear = <T>(deque: Deque<T>): T | undefined => 
  deque[deque.length - 1]; // 마지막 요소 반환, 빈 배열이면 undefined

// 사용 예시
let deque: Deque<number> = []; // 숫자 타입의 빈 덱 생성

deque = addRear(deque, 1);     // 뒤쪽에 1 추가 → [1]
deque = addFront(deque, 0);    // 앞쪽에 0 추가 → [0, 1]  
deque = addRear(deque, 2);     // 뒤쪽에 2 추가 → [0, 1, 2]

console.log(deque);            // 전체 덱 출력: [0, 1, 2]
console.log(peekFront(deque)); // 앞쪽 요소 확인: 0
console.log(peekRear(deque));  // 뒤쪽 요소 확인: 2

const [front, newDeque] = removeFront(deque); // 앞쪽 요소 제거, 구조분해할당으로 받기
console.log(front);            // 제거된 요소: 0
console.log(newDeque);         // 남은 덱: [1, 2]

덱의 특징

장점

• 유연성: 스택 + 큐 기능을 모두 제공

• 양방향 접근: 앞뒤 어디서든 O(1) 시간에 접근 (연결리스트 기반)

• 다양한 활용: 슬라이딩 윈도우, 팰린드롬 검사 등

단점 (배열 기반)

• addFront, removeFront가 O(n) 시간 복잡도 (요소들을 이동해야 함)

활용 사례

팰린드롬 검사

function isPalindrome(str: string): boolean {
  let deque = str.split('');
  
  while (deque.length > 1) {
    const [front] = removeFront(deque);
    const [rear, newDeque] = removeRear(deque);
    deque = newDeque;
    
    if (front !== rear) return false;
  }
  return true;
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello"));   // false

슬라이딩 윈도우

// 최근 3개 요소의 합을 계속 계산
let window: Deque<number> = [];

function addToWindow(num: number): number {
  window = addRear(window, num);
  if (window.length > 3) {
    [, window] = removeFront(window);
  }
  return window.reduce((a, b) => a + b, 0);
}

// 사용 예시
console.log(addToWindow(1)); // 1 (window: [1])
console.log(addToWindow(2)); // 3 (window: [1, 2])
console.log(addToWindow(3)); // 6 (window: [1, 2, 3])
console.log(addToWindow(4)); // 9 (window: [2, 3, 4])

브라우저 히스토리

class BrowserHistory {
  private history: Deque<string> = [];
  private currentIndex = -1;

  visit(url: string): void {
    // 현재 위치 이후의 히스토리 제거
    this.history = this.history.slice(0, this.currentIndex + 1);
    this.history = addRear(this.history, url);
    this.currentIndex++;
  }

  back(): string | undefined {
    if (this.currentIndex > 0) {
      this.currentIndex--;
      return this.history[this.currentIndex];
    }
    return undefined;
  }

  forward(): string | undefined {
    if (this.currentIndex < this.history.length - 1) {
      this.currentIndex++;
      return this.history[this.currentIndex];
    }
    return undefined;
  }
}

결론

위와 같이 Deque은 양쪽 끝에서 자유롭게 삽입/삭제가 가능한 가장 유연한 자료구조로, 스택과 큐의 모든 기능을 포함한다.