Jun 개발노트

Queue / 큐

2020-02-16

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