JavaScriptデータ構造(2):キュー

1.What is Q？

Qを説明させてもらいましたが、今回はびっしり並んでいる様子を見ましたか?その上の写真はソウル駅です.これは祝日のために列車の切符を予約した様子です.汽車の切符の前売りの時は列に並んでいて、先に着いたら先に得ます.先着順の形式.

以上は英漢辞典に照会した結果です.一言で言えば、Qはマイナスです.そして、先着順が原則です.すなわち,先入先出(FIFO)または後入後出(LILO)が特徴である.キューはスタックと同様に抽象的なデータ構造であるため,先着順の原則を守ればデータのフォーマットは関係ない.

2.実装キュー

今回はES 6構文クラスを用いてキュー資料構造を実現する.
次はJavaScriptコードです.

class Queue {
  constructor() {
    this.storage = {}; // 여기에 담을 것이다.
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return Object.keys(this.storage).length;
  }
	
	// 큐에 데이터를 추가 할 수 있어야 합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
	// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (Object.keys(this.storage).length === 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

次に、上記のクラスに基づいて実際に適用された例を示します.

const queueData = new Queue;
queueData.enqueue('a'); //'a'를 넣는다
queueData.enqueue('b'); //'b'를 넣는다
queueData.enqueue('c'); //'c'를 넣는다
console.log(queueData); // {storage: {…}, front: 0, rear: 3}
// storage: {0: "a", 1: "b", 2: "c"}
console.log(queueData.size()); // 큐의 길이는 3
queueData.dequeue(); // 콘솔에는 'a'가 찍힌다
console.log(queueData); // {storage: {…}, front: 1, rear: 3}
// storage: {1: "b", 2: "c"}
// 즉 먼저 삽입된 'a'가 빠진 것을 알 수 있다.

3.キュー例：プリンタ

プリンタの印刷方法もキューに従います.先に注文した先印.しかし、これは終わりではありません.コンピュータの使用効率を向上させるためには、一時的に格納されるバッファ容量も考慮する必要があります.また,一度に最大同時保存する文書量も考慮する.したがって、queuePrinterという関数を作成し、すべてのドキュメントを印刷するのに要する最小時間を返します.因子は以下の通りである.

パラメータ1:bufferSize
番号付けタイプの印刷ジョブリストサイズ

ファクタ2:容量
番号付け印刷ジョブリストに追加可能な最大容量

パラメータ3:documents

配列で、番号付けタイプを要素とするドキュメントサイズがリストされます.
まず、ドキュメントの配置は順番に印刷しなければならないので、キューの形式であることがわかります.また、少なくとも時間がかかるので、時間をマークする変数も必要です.キューに0をフォーマットします.これまでのコードは次のとおりです.

function queuePrinter(bufferSize, capacities, documents) {
  let time = 0; // 걸린 시간(초)
  let queue = []; // 문서를 여기에 옮길 것이다.
  let totalBufferVolume = 0; // 문서가 버퍼에 들어갈 때 총 들어간 용량이다. 
  // queue에 bufferSize만큼 0을 삽입 (queue에 들어갈 요소의 고정 갯수를 만들어 주는 과정입니다.)
    for(let i = 0; i < bufferSize; i++){
        queue.push(0);
    }
}

ドキュメントを最初に印刷するときは(1秒)を考慮します.現在のドキュメントが何であるかを指定し、コピーではなくqueue配列にドキュメントの最初の受信配列を移動します.また、ドキュメントがバッファに移動されているため、totalBufferVolumeでも変更された値が変更されます.そして、秒を表す時間変数に1(1秒経過)を加算します.ここまでのコードは以下の通りです.

  let currentDocument = documents.shift();
  queue.unshift(currentDocument);
  queue.pop(); // 이는 queue의 배열의 length를 일정하게 하게 만드는 스킬이다.
  totalBufferVolume += currentDocument;
  time++;

今から1秒後、仕事を繰り返すだけでいいです.繰り返し条件は、ドキュメント内のバッファの合計容量が0より大きいことです.印刷が完了すると、バッファに入る総容量はゼロになるからです.2秒から合計バッファの容量を変更します.新しい書類があるからです.また、新しいドキュメントがバッファに入る場合がありますが、容量が不足してバッファに入れない場合があります.それぞれの状況をエンコードすればいいです.次は1秒後の場合の符号化です.

while (totalBufferVolume) {
  // totalBufferVolume(총 용량)에 queue의 마지막 배열을 빼준다.
  totalBufferVolume -= queue.pop();
  // document의 맨 앞의 요소를 일단 빼고, 현재 문서로 저장한다.
  currentDocument = documents.shift();
  // 여기서 용량에 따라서 분기점이 생긴다.
  // 만약 여유공간이 있다면
  if (currentDocument + totalBufferVolume <= capacities) {
    // queue에 currentDocument 삽입 후 총 용량에 현재 문서의 용량을 더해준다.
    queue.unshift(currentDocument);
    totalBufferVolume += currentDocument;
  } else { // 용량이 모자른 경우
    // documents에 현재 문서를 맨 앞에 다시 넣어준다.(shift해준것을 다시 복구)
    documents.unshift(currentDocument);
    queue.unshift(0);// 추가된 문서가 없기 때문에 맨 앞의 queue에 0을 추가
  }
  time++; // 1초의 경우처럼 마지막에 시간을 1초 추가해준다.
}

次にcountに戻ります.総コードは次のとおりです.

function queuePrinter(bufferSize, capacities, documents) {
  let time = 0; // 걸린 시간(초)
  let queue = []; // 문서를 여기에 옮길 것이다.
  let totalBufferVolume = 0; // 문서가 버퍼에 들어갈 때 총 들어간 용량이다. 
  // queue에 bufferSize만큼 0을 삽입 (queue에 들어갈 요소의 고정 갯수를 만들어 주는 과정입니다.)
    for(let i = 0; i < bufferSize; i++){
        queue.push(0);
    }
  
  let currentDocument = documents.shift();
  queue.unshift(currentDocument);
  queue.pop(); // 이는 queue의 배열의 length를 일정하게 하게 만드는 스킬이다.
  totalBufferVolume += currentDocument;
  time++;
  
  while (totalBufferVolume) {
  // totalBufferVolume(총 용량)에 queue의 마지막 배열을 빼준다.
    totalBufferVolume -= queue.pop();
  // document의 맨 앞의 요소를 일단 빼고, 현재 문서로 저장한다.
    currentDocument = documents.shift();
  // 여기서 용량에 따라서 분기점이 생긴다.
  // 만약 여유공간이 있다면
    if (currentDocument + totalBufferVolume <= capacities) {
    // queue에 currentDocument 삽입 후 총 용량에 현재 문서의 용량을 더해준다.
      queue.unshift(currentDocument);
      totalBufferVolume += currentDocument;
    } else { // 용량이 모자른 경우
    // documents에 현재 문서를 맨 앞에 다시 넣어준다.(shift해준것을 다시 복구)
      documents.unshift(currentDocument);
      queue.unshift(0);// 추가된 문서가 없기 때문에 맨 앞의 queue에 0을 추가
    }
    time++; // 1초의 경우처럼 마지막에 시간을 1초 추가해준다.
  }
  return time;
}