큐는 FIFO(first in first out) 선입선출 원리에 따라 정렬된 컬렉션이다.

새 원소는 뒤로 들어가서 앞에서 빠져나가는 구조이다.

따라서 마지막에 추가된 원소는 큐의 뒷부분에서 제일 오래 기다려야 한다.

큐 만들기

큐에서 사용할 메서드는 다음과 같다.

enqueue() : 큐의 뒤쪽에 원소를 추가한다. dequeue() : 큐의 첫 번쨰 우너소를 반환하고 큐에서 삭제한다. front() : 큐의 첫 번쨰 원소를 반환하되 큐 자체는 그대로 둔다. isEmpty() : 큐가 비어있으면 true, 그 외에는 false를 반환한다. size() : 큐의 원소 개수를 반환한다.

function Queue() {
  var items = [];
  // 큐에 원소를 추가하는 메서드로 큐의 뒤쪽에만 추가할 수 있다.
  this.enqueue = function(element) {
    items.push(element);
  };
  this.dequeue = function() {
    return items.shift();
  };
  this.front = function() {
    return items[0];
  };
  this.isEmpty = function() {
    return items.length === 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size = function() {
    return items.length;
  };
  this.print = function() {
    console.log(items.toString());
  };
}

우선순위 큐

원소가 우선순위에 따라 추가되고 삭제되는 점이 다르다.

우선순위 큐는 우선순위를 설정해 원소를 정확한 위치에 추가하는 것, 그리고 추가는 순서대로 하되 삭제만 우선순위에 따르는 것

두 가지 방법으로 구현할 수 있다.

// 정확한 위치에 추가하는 방식
function PriorityQueue() {
  var items = [];
  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }
  this.enqueue = function(element, priority) {
    var queueElement = new QueueElement(element, priority);
    if (this.empty()) {
      items.push(queueElement);
    } else {
      var added = false;
      for (var 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);
      }
    }
  };
}

이러한 로직으로 구현한 우선순위 큐를 최소 우선순위 큐라고 부른다.

환영 큐

function hotPotato(nameList, num) {
  var queue = new Queue();
  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }
  var eliminated = "";
  while (queue.size() > 1) {
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();
    console.log(eliminated + "을 뜨거운 감자 게임에서 퇴장시킵니다.");
  }
  return queue.dequeue();
}