큐- 4

이 내용은 'Learning JavaScript Data Structures and Algorithms'(로이아니 그로네르 저, 이일웅 역) 책의 내용을 제 생각과 함께 정리한 글입니다.

틀린 내용 혹은 수정이 필요한 내용이 있다면 말씀해주시면 감사하겠습니다.

• 큐는 FIFO(First In First Out = 선입선출) 원리에 따라 정렬된 컬렉션이다.

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

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

줄서기를 떠올려보자. 영화관에서 줄을 서 있을 때 맨 앞의 사람이 가장 먼저 표를 사는 것은 당연한 일이다.

큐 만들기

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

• enqueue(element) : 큐의 뒤쪽에 원소(들)를 추가한다.

• dequeue(): 큐의 첫 번째 원소(큐의 맨 앞쪽에 위치한 원소)를 반환하고 큐에서 삭제한다.

• front() : 큐의 첫 번째 원소를 반환하되 큐 자체는 그대로 놔둔다. (peek()과 비슷)

• isEmpty(): 큐가 비어있으면 true, 아니면 false를 반환한다.

• size(): 큐의 원소 개수를 반환한다. 배열의 length와 같다.

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.size = function () {
    return items.length;
  };
  this.print = function () {
    console.log(items);
  };
}

Queue와 Stack 클래스는 매우 유사하다. 적용하는 원리가 FIFO, LIFO로 다르기 때문에 dequeue와 마찬가지로 front메소드만 다르다.

• 결과를 확인해보자.

const queue = new Queue();

console.log(queue.isEmpty()); // true

queue.enqueue('John');
queue.enqueue('Jack');
queue.enqueue('Camilla');

queue.print(); // [ 'John', 'Jack', 'Camilla' ]
console.log(queue.size()); // 3
console.log(queue.isEmpty()); // false

queue.dequeue();
queue.dequeue();
queue.print(); // [ 'Camilla' ]

우선순위 큐

• 원소가 우선 순위에 따라 추가되고 삭제된다.

비행기 탑승을 떠올려보자. 1등석과 비즈니스석 승객은 항상 이코노미석 승객보다 우선순위가 높다.

• 우선순위 큐는 우선순위를 설정해 원소를 정확한 위치에 추가하는 것, 그리고 추가는 순서대로 하되 삭제만 우선순위에 따르는 것, 두 가지 방법으로 구현할 수 있다. 먼저 전자를 보자.

function PrirorityQueue() {
  let items = [];

  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority; // 우선순위(priority)가 추가됨
  }

  this.enqueue = function (element, priority) {
    let queueElement = new QueueElement(element, priority);

    if (this.isEmpty()) {
      items.push(queueElement); // 큐가 비어있다면 원소를 그냥 넣는다.
    }
    // general case
    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.isEmpty = function () {
    return items.length === 0;
  };
  this.print = function () {
    console.log(items);
  };
}

const priorityQueue = new PrirorityQueue();
priorityQueue.enqueue('John', 2);
priorityQueue.enqueue('Jack', 1);
priorityQueue.enqueue('Camilla', 3);
priorityQueue.print();

// 실행결과: [ QueueElement { element: 'Jack', priority: 1 },
//             QueueElement { element: 'John', priority: 2 },
//             QueueElement { element: 'Camilla', priority: 3 } ]

• 이러한 로직으로 구현한 우선순위 큐를 최소 우선순위 큐(min priority queue)라고 부르는데, 우선순위 값이 낮으면 낮을수록(1이 가장 높은 우선순위다) 앞자리로 이동하기 때문이다.

• 반대로 우선순위 값이 크면 클수록 앞자리로 보내는 최대 우선순위 큐(max priority queue)도 있다.

환형 큐 (뜨거운 감자 게임)

• 뜨거운 감자(Hot Potato)게임 은 환형 큐(Circular Queue)의 대표적인 예다.

• 원을 그리고 서 있는 아이들이 뜨거운 감자를 옆 사람에게 최대한 빨리 전달하다가, 갑자기 모두 동작을 멈추고 그 때 뜨거운 감자를 손에 들고 있는 아이를 벌칙으로 퇴장시키는 게임이다. 최후의 1인(승자)이 남을 때까지 게임은 계속된다.

• 이를 코드로 구현해보자.

// Circular Queue (Hot Potato Game)
// nameList: 게임에 참여한 사람들의 이름, num: 큐를 순회할 횟수
function hotPotato(nameList, num) {
  let queue = new Queue();

  for (let i = 0; i < nameList.length; i++) queue.enqueue(nameList[i]);

  let eliminated = '';
  // 최후의 1인이 남을 때까지
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) queue.enqueue(queue.dequeue()); // 맨 앞의 원소를 꺼내어 맨 뒤로 넣는다.
    eliminated = queue.dequeue(); // num만큼 반복이 끝난 후 뜨거운 감자를 들고 있던 사람을 퇴장시킨다.
    console.log(`${eliminated}을(를) 게임에서 퇴장시킵니다.`);
  }
  return queue.front(); // 마지막 사람이 승자가 된다.
}

const names = ['John', 'Jack', 'Camilla', 'Ingrid', 'Carl'];
const winner = hotPotato(names, 7);
console.log(`승자는 ${winner} 입니다.`);

// 결과
// Camilla을(를) 게임에서 퇴장시킵니다.
// Jack을(를) 게임에서 퇴장시킵니다.
// Carl을(를) 게임에서 퇴장시킵니다.
// Ingrid을(를) 게임에서 퇴장시킵니다.
// 승자는 John 입니다.

• hotPotato 함수의 num인자를 바꾸면 다른 결과를 반환할 것이다.