데크 (deque, double-ended queue)는 요소를 양 끝에서 추가하거나 제거할 수 있는 자료 구조입니다. 데크는 스택과 큐의 기능을 모두 가지고 있어서, 데이터를 양쪽 끝에서 조작할 수 있습니다. 이러한 특징 때문에 데크는 여러 다양한 알고리즘과 문제 해결에 활용됩니다.

데크의 기본적인 동작

• 양쪽 끝에서 추가 (push) 및 제거 (pop): 데크는 양쪽 끝에서 원소를 추가하거나 제거할 수 있습니다.
• 양쪽 끝 조회 (peek): 데크의 양쪽 끝에서 원소를 조회할 수 있습니다.

데크의 활용

데크의 유연성과 다양한 기능을 통해 많은 문제에 적용됩니다. 몇 가지 예시로는 다음과 같은 경우가 있습니다:

• 최대 슬라이딩 창 (maximum sliding window) 문제: 고정된 크기의 창이 주어지면 그 창을 움직여가며 각 창에서 최대값을 구하는 문제를 풀 때 데크를 사용할 수 있습니다.
• 팰린드롬 (palindrome) 관련 문제: 문자열이나 배열이 회문인지 판별하는 문제를 풀 때 데크를 활용할 수 있습니다.
• 트리 순회(Tree traversal): 이진 트리의 순회 과정에서 데크를 활용하여 너비 우선 탐색 (BFS)을 구현할 수 있습니다.

자바스크립트에서 데크 구현

다음은 자바스크립트에서 데크를 배열을 활용하여 구현하는 예시 코드입니다.

class Deque {
  constructor() {
    this.items = [];
  }

  pushFront(element) {
    this.items.unshift(element);
  }

  pushBack(element) {
    this.items.push(element);
  }

  popFront() {
    return this.items.shift();
  }

  popBack() {
    return this.items.pop();
  }

  peekFront() {
    return this.items[0];
  }

  peekBack() {
    return this.items[this.items.length - 1];
  }

  size() {
    return this.items.length;
  }

  isEmpty() {
    return this.items.length === 0;
  }

  clear() {
    this.items = [];
  }
}

마치며

데크는 데이터를 양쪽 끝에서 조작할 수 있는 유용한 자료 구조입니다. 이러한 특성을 활용하여 문제를 해결하거나 알고리즘을 구현할 때 데크를 적절히 활용함으로써 효율적인 솔루션을 찾을 수 있습니다.