JavaScript 자료구조 - Queue

ryu·2020년 3월 26일
5

Queue

JavaScript로 Queue 구현하기 (ES6)

  • Array 를 사용하여 Queue 를 구현할 수 있습니다.
  • Array의 push() 메소드로 enqueue 를,
    shift() 메소드로 dequeue 를 구현
    할 수 있습니다. ✨
class Queue {
  constructor() {
    this.store = [];
  }
  
  enqueue(item) {
    this.store.push(item);
  }
  
  dequeue() {
    return this.store.shift();
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue();   // 1

JavaScript로 Priority Queue 구현하기 (ES6)

  • Priority Queue (우선순위큐) 는 선입선출 방식이 아닌, 우선순위를 기준으로 우선순위가 높은 요소를 먼저 삭제하는 큐 입니다.
  • splice() 메소드로 dequeue 를 구현합니다.

Score 가 높은 학생을 먼저 추출해낸다는 방식으로 Priority Queue 를 구현해보았습니다.

class PriorityQueue {
  constructor() {
    this.store = [];
  }
  
  enqueue(item) {
    this.store.push(item);
  }
  
  dequeue() {
    let entry = 0;
    this.store.forEach((item, index) => {
      if (this.store[entry].score < this.store[index].score) {
        entry = index;
      }
    });
    return this.store.splice(entry, 1);
  }
}

class Student {
  constructor(name, score) {
    this.name = name;
    this.score = score;
  }
}

const priorityQueue = new PriorityQueue();
const pengsoo = new Student('Pengsoo', 10);
const kim = new Student('MJKim', 5);
const ryu = new Student('Ryu', 3);

priorityQueue.enqueue(pengsoo);
priorityQueue.enqueue(kim);
priorityQueue.enqueue(ryu);

priorityQueue.dequeue();   // Student('Pengsoo', 10)
profile
안녕하세요~ 현재 현대자동차에서 AI 연구원으로 일하고있고, 이전에는 카카오 AI플랫폼팀에서 웹개발자로 일했습니다. FrontEnd 에 관심이 많고, Youtube '개발자 쿠키' 채널을 운영하고 있습니다. 🍪

1개의 댓글

comment-user-thumbnail
2020년 5월 6일

안녕하세요 자바스크립트로 우선순위큐를 어떻게 구현할 수 있을까 찾다 발견했습니다. 역시 자바스크립트도 클래스로 정리하니 깔끔하네요. 몇가지 궁금한점이 있어 댓글남깁니다.

첫번째는..일반적으로 Queue는 삽입, 삭제연산이 시간복잡도 O(1)로 이루어지도록 구현이 되어야 할 것 같은데요. enqueue는 배열의 push연산으로 O(1)에 작동하는 반면, dequeue에서는 배열의 shift 연산을 이용하면 가장 앞의 요소를 제거하고 나머지 뒤의 요소들의 인덱스를 한칸씩 당겨야 하므로 O(n)이 소요되어 자료구조의 목적에 비해 조금 효율적이지 않은 구현이되지 않을까 싶습니다.

두번째는..우선순위 큐의 경우 구현에 따라 달라지겠지만 일반적으로 목적에 따라 삽입의 경우 O(logn), 삭제의 경우 O(1)이 되도록 구현이 되어야 할것 같습니다. dequeue에서 forEach를 수행하는 동안 O(n)이 되어버리고 더불어 아래 splice에서도 인덱스 재배열을 위해 O(n)이 소요될것 같은데 dequeue에서 O(n)이 소요된다면 정렬을 통해서 값을 찾아내는 것보다 효율이 낮아지지 않을까 생각해봅니다.

질문드린부분은 파이썬이나 C++언어들의 구현체에 기반한 건데요 혹시나 자바스크립트에서는 배열의 구현이 다를수도 있기 때문에 혹시 제가 잘못 알고있는것인지 해서 문의드립니다. 좋은하루 되세요!

답글 달기