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();
   
   }