큐(Queue)

•FIFO(First In First Out: 선입선출) 원리에 따라 정렬된 컬렉션.
새원소는 뒤로 들어가서 앞에서 빠져나가는 구조로, 마지막에 추가된 원소는 큐의 뒷부분에서 제일 오래 기다려야 한다. 예) 매표소

1) 큐만들기

•enqueue(element) : 큐의 뒤쪽에 원소들을 추가한다.
•dequeue() : 큐의 첫번째 원소를 반환하고 큐에서 삭제한다.
•front() : 큐의 첫번째 요소를 반환하되 큐 자체는 그대로 둔다.
•isEmpty() : 큐가 비어있다면 true, 그 외에는 false를 반환한다.
•size() : 큐의 원소 개수를 반환한다.

class Queue {
  constructor() {
    this.items = [];
  }
  //뒤에 요소 추가
  enqueue = (elements) => {
    return this.items.push(elements);
  };
  //앞의 요소 삭제
  dequeue = () => {
    return this.items.shift();
  };
  //앞의 요소 참조
  front = () => {
    let front = this.items[0];
    return front;
  };
  //아이템의 길이
  size = () => {
    return this.items.length;
  };
  //배열이 비어있는지 불린값으로 확인
  isEmpty = () => {
    return this.items.length === 0;
  };
  //아이템 배열 전부 삭제
  clear = () => {
    return (this.items = []);
  };
  print = () => {
    console.log(this.items.toString());
  };
}

2) 우선순위 큐

•원소가 우선순위에 따라 추가/삭제, 우선순위의 값이 작을수록 앞자리도 이동시킨다.(1이 가장 높은 우숸순위를 갖는다.)

class PriorityQueue {
  constructor() {
    this.items = [];
    class QueueElement {
      constructor(element, priority) {
        this.element = element;
        this.priority = priority;
      }
    }
    this.enqueue = (element, priority) => {
      let queueElement = new QueueElement(element, priority);

      if (this.isEmpty()) {
        this.items.push(queueElement);
      } else {
        let add = false;
        //여기서 priority는 1이 가장 큰 순위다.
        for (let i = 0; i < this.items.length; i++) {
          if (queueElement.priority < this.items[i].priority) {
            this.items.splice(i, 0, queueElement);
            //아이템의 i번째에 해당하는 요소를 0번째 인덱스에 요소를 삽입
            add = true;
            break;
          }
        }
        if (!add) {
          this.items.push(queueElement);
        }
      }
    };
  }
  dequeue = () => {
    return this.items.shift();
  };
  size = () => {
    return this.items.length;
  };
  isEmpty = () => {
    return this.items.length === 0;
  };
  front = () => {
    let front = this.items[0];
    return front;
  };
  print = () => {
    console.log(this.items);
  };
}

3)환형 큐(뜨거운 감자 게임)

const hotPotato = (nameList, num) => {
  let queue = new Queue();

  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }
  let eliminated = "";
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();
    console.log(`${eliminated} 탈락`);
  }
  return queue.dequeue();
};