Queue 알고리즘

객체를 이용한 Queue 구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  //큐의 사이즈
  size() {
    return this.rear - this.front;
  }
  // 큐 내 요소 삽입
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  // 큐 내 요소 출력
  dequeue() {
    if (this.size() === 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }

  //큐의 모든 요소 출력
   allEle(){
     let ele = this.storage;
     let result = [];
     for(let key in ele){
       result.push(ele[key]);
     }
     return result.join(',');
   }
  //큐가 비어있는지 확인
   empty(){
     //사이즈로 볼 경우
     //if (this.size() === 0) {
     //  return 'empty Q';
     //} else { 
     //  return 'no';
     //}
     // this 인자 활용시
     return (this.front === this.rear) ? true : false;
   }

}

BFS를 큐를 통해 구현할 수 있나요?

• 참조

//자주쓰는 Queue 배열 코드(Example)
function bfsQ() {
  let Q = [
    [0, 0],
    [0, 1],
    [0, 2],
    [0, 3],
  ];
  function enQ(ele) {
    Q.push(ele)
  }
  function deQ() {
    let head = Q[0];
    Q = Q.slice(1);
    return head;
  }
  // 4 X 4 n-queens 간단 예시 with 수도코드
  while (Q.length > 0) {
    // [0, 0]
    let choice = deQ();
    // [0, 1], [0, 2], [0, 3],
    let row = choice[0];
    let col = choice[1];
    for (let col = 0; col < N; col++){
      if (map[row + 1][col]에 놓을 수 있냐?) {
        enQ([row + 1, col])
      }
    }
  }
}

JS - Queue 구현

• 참조1
• 참조2
• 참조3 - 큐의 사이즈가 정해져있을 경우