javaScript로 Queue 구현

Queue(큐)

• FIFO(First In First Out / 선입선출) 원리에 따라 정렬된 자료구조
• 큐의 자료는 뒤로 들어가서 앞으로 빠져나가는 구조
• 프린터의 '출력물 인쇄 대기'에 큐가 응용됨

큐의 구조(출처: 나무위키)

메소드

• enqueue : 큐의 뒤쪽에 원소(들) 추가
• dequeue : 큐의 첫 번째(맨 앞) 원소를 반환하고 큐에서 삭제
• front : 큐의 첫 번째 원소를 반환
• isEmpty : 큐가 비어 있으면 true를, 아니면 false를 반환
• size : 큐의 원소 개수 반환

구현

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

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    return this.items.shift();
  }
 
  front() {
    return this.items[0];
  }

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

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

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

우선순위 큐

• 기본 큐의 변형으로, 원소가 우선순위에 따라 추가되고 삭제된다는 점이 다르다
• 병원 응급실에서 환자의 부상 정도에 따라 다른 우선순위를 설정하는 경우를 떠올릴 수 있다

구현

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

  enqueue(data, priority) {
    let queueElement = new this.QueueElement(data, priority);

    if (this.isEmpty()) {
      this.items.push(queueElement);
    } else {
      let added = false;
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement);
          added = true;
          break;
        }
      }
      if (!added) {
        this.items.push(queueElement);
      }
    }
  }
  
  // 나머지 메소드는 기본 큐와 같다
  
}

// 큐에 새로운 원소를 생성하기 위한 내부 클래스, 각각의 원소는 데이터와 우선순위를 가진다
PriorityQueue.prototype.QueueElement = class {
  constructor(data, priority) {
    this.data = data;
    this.priority = priority;
  }
};

시간 복잡도

• 검색 : O(n)
• 삽입 : O(1)
• 삭제 : O(1)