Queue / 큐

Queue 큐

1. 정의 : FIFO(선입선출 / 먼저 온 사람 먼저 나가기)따라 정렬된 컬렉션이다.

2. 사용처 : 브라우져 이벤트 큐, 프린터 인쇄 순서

3. 기능

   • enqueue(item) : 원소 추가()
   • dequeue() : 첫 번째 원소를 반환하고 삭제
   • front() : 첫 번째 원소를 반환하고 삭제 안함(Stack의 peek()이랑 비슷)
   • isEmpty() : 큐가 비워 있으면 true, 아니면 false
   • size() : 큐의 모든 원소 갯수
   • cleat() : 큐의 모든 원소 제거

4. 코드 구현

   class Queue {
       constructor() {
           this._arr = []
       }
       enqueue(item) {
           this._arr.push(item)
       }
       dequeue() {
           return this._arr.shift()
       }
       front() {
           return this._arr[0]
       }
       isEmpty() {
           return this._arr.length === 0
       }
       size() {
           return this.arr.length
       }
       clear() {
           this._arr = []
       }
       print() {
           console.log(this._arr.toString())
       }
   }

5. 우선순위 큐

   • 정의 : 원수가 우선순위에 따라 추가되고 삭제된다
   • 구조 : 트리구조와 비슷하다(크기가 아니라 우선순위에 따라 정렬되니까)
   • 예 : 비행기 우선순위 입장, 응급실 진료 순서

   function MinPriorityQueue() {
       const items = []
   
       function QueueElement(element, priority) {
           this.element = element
           this.priority = priority
       }
   
       this.enqueue = function (element, priority) {
           let queueElement = new QueueElement(element, priority)
   
           if (this.isEmpty()) {
               items.push(queueElement)
           } else {
               let added = false
               for (let i = 0; i < items.length; i++) {
                   if (queueElement.priority < items[i].priority) {
                       items.splice(i, 0, queueElement)
                       added = true
                       break
                   }
               }
   
               // splice 예제
               // const months = ['Jan', 'March', 'April', 'June'];
               // months.splice(1, 0, 'Feb');
               // inserts at index 1
               // console.log(months);
               // expected output: Array ["Jan", "Feb", "March", "April", "June"]
   
               if (!added) {
                   items.push(queueElement)
               }
           }
       }
   }

6. 환영 큐(뜨거운 감자 게임)

   • 룰 : 뜨거운 감자를 돌리다가 마지막에 가진 사람이 퇴장하는 게임

   function hotPotato(nameList, num) {
       const 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()
   }