[알고리즘] 큐 (Queue)

카테고리 : 컴퓨터 공학
태그: cs · 컴퓨터 공학 · algorithm · 자료구조 · 큐 · Queue · FIFO · 선입선출 · 우선순위 큐

1. 큐

  • FIFO(first In first out)
  • 선입 선출
  • ex) 출력문 인쇄 대기

2. 큐 만들기

1) 큐 클래스 생성

function Queue(){
    // property & method 기술하기
}

2) 큐의 원소를 담아둘 자료 구조

var item = [];

3) 큐에 필요한 메서드 정리

  • enqueue(‘원소들’) : 큐의 뒤쪽에 원소 추가
  • dequeue() : 큐의 첫 번째 원소를 반환하고 큐에서 삭제
  • front() : 큐 첫번째의 원소를 반환하고 해당 원소 제거를 제거 하지 않음 ( 스택 변경 X)
  • isEmpty() : 큐 원소가 한개도 없으면 True / 스택 크기가 0보다 크면 False 반환
  • size() : 큐의 원소 개수 반환

4) Queue 클래스

function Queue() {
    let items = [];

    this.enqueue = function(element){
        items.push(element);
    }

    this.dequeue = function(){
        // shift()는 배열의 첫번째 요소를 제거하고 반환함 / pop()은 배열의 마지막 요소를 제거하고 반환함
        return items.shift();
    }

    this.front = function(){
        return items[0];
    }

    this.isEmpty = function(){
        return items.length === 0;
    }

    this.size = function(){
        return items.length;
    }

    this.clear = function(){
        items = [];
    }

    this.print = function(){
        console.log(items.toString());
    }
}

let queue = new Queue();
console.log(queue.isEmpty()); // outputs true

queue.enqueue("DongNyeong");
queue.enqueue("DongNyeong2");
queue.enqueue("DongNyeong3");
queue.print(); // outputs [DongNyeong, DongNyeong2, DongNyeong3]
console.log(queue.size()); // outputs 3
console.log(queue.isEmpty()); // outputs false
queue.dequeue();  //output DongNyeong removed DongNyeong from the queue
queue.dequeue();  //output DongNyeong2 removed DongNyeong2 from the queue
queue.print(); // outputs DongNyeong3

2) 우선순위 큐 활용

  • 비행기 퍼스트 클래스 / 비즈니스 클래스 / 이코노미 클래스 순으로 우선순위를 매기는 경우
  • 응급실에서 중상 환자에 따라 우선 순위에 따라 진료실로 보내는 경우
function PriorityQueue() {
    let 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;
                }
            }
            if(!added){
                items.push(queueElement);
            }
        }
        this.print();
    }
    this.isEmpty = function(){
        return items.length === 0;
    }

    this.print = function(){
        console.log(items.toString());
    }
}

let priorityQueue = new PriorityQueue();
priorityQueue.enqueue("DongNyeong", 2);
priorityQueue.enqueue("DongNyeong2", 1);
priorityQueue.enqueue("DongNyeong3", 1);

3) 환형 큐(Circulator Queue) 활용

  • hotpotato 게임
  • 뜨거운 감자를 옆 사람에게 최대한 빠르게 전달하다 , 갑자기 동작을 멈추고 뜨거운 감자를 손에 들고 있는 아이를 벌칙으로 퇴장 시키는 게임
function 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 + '님이 Hot Potato 게임에서 제외되었습니다.');
    }
    return queue.dequeue();
}

let names = ['dongnyeong1','dongnyeong2','dongnyeong3','dongnyeong4','dongnyeong5'];
let winner = hotPotato(names, 7);
console.log('승자는: ' + winner + '입니다.'); //승자는: dongnyeong1입니다.

//dongnyeong3님이 Hot Potato 게임에서 제외되었습니다.
//dongnyeong2님이 Hot Potato 게임에서 제외되었습니다.
//dongnyeong5님이 Hot Potato 게임에서 제외되었습니다.
//dongnyeong4님이 Hot Potato 게임에서 제외되었습니다.
//승자는: dongnyeong1입니다.