[알고리즘] 큐 (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입니다.