Jun 개발노트

Queue / 큐

February 16, 2020

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

Written by Junho You 배운것을 기록하자