algorithm/자료구조

우선순위 큐(Priority Queue)와 덱(Deque)

yongfront 2024. 3. 20. 14:03
반응형
SMALL

우선순위 큐(Priority Queue)와 덱(Deque, Double-Ended Queue)은 모두 추상 자료형(Abstract Data Type, ADT)으로, 데이터를 저장하고 접근하는 데 사용되는 컬렉션입니다. 그러나 그들이 데이터를 관리하고 접근하는 방식에는 중요한 차이가 있습니다.

우선순위 큐(Priority Queue)

우선순위 큐는 각 요소가 우선순위와 함께 저장되는 자료구조입니다. 요소들은 우선순위에 따라 정렬되며, 요소를 제거할 때는 가장 높은 우선순위를 가진 요소가 먼저 제거됩니다. 우선순위 큐는 힙(Heap) 자료구조를 사용하여 효율적으로 구현될 수 있습니다. 힙을 사용하는 경우, 요소의 추가와 제거(특히, 최소값 또는 최대값의 제거)가 O(logN) 시간 복잡도를 가집니다.

  • 사용 예: 다익스트라(Dijkstra) 최단 경로 알고리즘, 이벤트 기반 시뮬레이션, 작업 스케줄링 시스템 등

덱(Deque, Double-Ended Queue)

덱은 양쪽 끝에서 요소의 추가와 제거가 가능한 자료구조입니다. 스택(Stack)과 큐(Queue)의 일반화된 형태라고 볼 수 있으며, 덱을 사용하면 스택과 큐의 모든 연산을 하나의 자료구조로 통합할 수 있습니다. 덱의 구현은 동적 배열이나 연결 리스트를 사용할 수 있으며, 양쪽 끝에서의 요소 추가 및 제거 작업은 시간 복잡도를 가집니다(동적 배열을 사용할 경우 평균적으로 , 최악의 경우 일 수 있음).

  • 사용 예: 스크롤, 탐색, 스택 및 큐의 대체 구현, 팰린드롬 확인 알고리즘 등

차이점

  • 용도와 기능: 우선순위 큐는 요소들이 우선순위에 따라 정렬되어야 할 때 사용되며, 덱은 양쪽 끝에서의 추가와 제거가 필요할 때 사용됩니다.
  • 내부 구현: 우선순위 큐는 힙과 같은 자료구조를 사용하여 구현될 수 있으며, 덱은 동적 배열이나 연결 리스트로 구현됩니다.
  • 시간 복잡도: 우선순위 큐의 연산(특히 힙을 사용하는 경우)은 일반적으로 의 시간 복잡도를 가지며, 덱의 기본 연산은 시간 복잡도를 가집니다.

우선순위 큐와 덱은 각각 특정 유형의 문제 해결에 적합한 고유한 특성과 장점을 가지고 있습니다. 따라서 구현하고자 하는 애플리케이션의 요구 사항에 맞게 적절한 자료구조를 선택하는 것이 중요합니다.

 

우선순위 큐(Priority Queue)

우선순위 큐는 각 요소가 우선순위와 함께 저장되며, 우선순위가 가장 높은 요소가 먼저 제거됩니다. 이 예에서는 최소 힙을 사용한 우선순위 큐의 구현을 보여줍니다. 우선순위가 낮은 숫자일수록 높은 우선순위를 가지는 것으로 가정합니다.

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  // 요소 추가
  enqueue(value, priority) {
    const node = { value, priority };
    this.heap.push(node);
    this.heapifyUp();
  }

  // 요소 제거 및 반환
  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();
    return min.value;
  }

  // 힙 재구성 (상향식)
  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index].priority >= this.heap[parentIndex].priority) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  // 힙 재구성 (하향식)
  heapifyDown(index = 0) {
    let leftChildIndex, rightChildIndex, smallestChildIndex;

    while (true) {
      leftChildIndex = 2 * index + 1;
      rightChildIndex = 2 * index + 2;
      smallestChildIndex = index;

      if (leftChildIndex < this.heap.length && this.heap[leftChildIndex].priority < this.heap[smallestChildIndex].priority) {
        smallestChildIndex = leftChildIndex;
      }

      if (rightChildIndex < this.heap.length && this.heap[rightChildIndex].priority < this.heap[smallestChildIndex].priority) {
        smallestChildIndex = rightChildIndex;
      }

      if (smallestChildIndex === index) break;

      [this.heap[index], this.heap[smallestChildIndex]] = [this.heap[smallestChildIndex], this.heap[index]];
      index = smallestChildIndex;
    }
  }

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

덱(Deque)

덱은 양쪽 끝에서 요소의 삽입과 삭제가 가능한 일반화된 큐입니다. 덱은 스택과 큐의 일반화된 형태로 볼 수 있습니다.

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

  // 앞쪽에 요소 추가
  addFront(item) {
    this.items.unshift(item);
  }

  // 뒤쪽에 요소 추가
  addBack(item) {
    this.items.push(item);
  }

  // 앞쪽 요소 제거 및 반환
  removeFront() {
    return this.items.shift();
  }

  // 뒤쪽 요소 제거 및 반환
  removeBack() {
    return this.items.pop();
  }

  // 덱이 비어있는지 확인
  isEmpty() {
    return this.items.length === 0;
  }

  // 덱의 크기 반환
  size() {
    return this.items.length;
  }
}
728x90
반응형
LIST