キュー-4

この文章は『JavaScriptデータ構造とアルゴリズムを学ぶ』という本の内容をまとめた.
間違いや修正が必要な内容があれば、お知らせください.

キューはFIFOの原理に従って並べ替えられた集合である.

新しい要素は、後ろから入って前から退出する構造です.

したがって、最後に追加した要素は、キューの後ろで最長時間待つ必要があります.

並んでいる光景を思い出してみましょう.映画館に並んでいるとき、一番前の人が最初に切符を買うのは当然です.

キューの作成

キューで使用する方法は次のとおりです.

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' ]

優先キュー

要素は優先順位で追加・削除される.

飛行機に乗った光景を思い出す.ファーストクラスとビジネスクラスの乗客はいつもエコノミークラスの乗客より優先されている.

優先キューは、優先度を設定することによって要素を正しい位置に追加することと、追加順に行うが削除優先度のみで行うことの両方が可能である.まず電子を見てみましょう.

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 } ]

このような論理で実装される優先度キューは、優先度値が低い(1が最高優先度)ほど優先度が高いため、最小優先度キュー(minpriorityqueue)と呼ばれる.

逆に、優先度値が大きいほど、前のビットに送信される最大優先度キュー(max priority queue)も多くなります.

リングQ(ホットポテトゲーム)

ホットジャガイモゲームはリングキューの代表的な例です.

円を描いた子供たちが熱いジャガイモを一番早く隣の人に渡し、突然全員が動きを止め、その時熱いジャガイモを手にした子供を退場させるゲーム.ゲームは最後の一人(勝者)が残るまで続けられる.

コードで実現しましょう.

// 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因子を変更すると、他の結果が返されます.