JavaScript キューの原理と使用例の詳細な説明-jsチュートリアル-php.cn

キューは一種のリストです。違いは、キューはキューの最後にのみ要素を挿入し、キューの先頭にある要素を削除できることです。キューは、スタック (後入れ先出し) とは異なり、データを先入れ先出しの順序で並べて格納するために使用されます。スタックでは、スタックにプッシュされた最後の要素が最初に処理されます。行列は、レストランに食事をするためにたくさんの人が並んでいて、前にいた人が最初に食事を受け取るときのようなものだと想像できます。初心者は後ろにのみ並ぶことができます。彼らの番が来るまで。この記事では、主に JavaScript のデータ構造とアルゴリズムにおけるキューの原理と使用法を紹介し、キューの概念と原理をより詳細に説明し、JavaScript でキューを実装および使用する際の関連する操作テクニックと注意事項を例の形で分析します。困っている人は次を参照してください。皆さんのお役に立てれば幸いです。

1: キューの操作

キューには 2 つの主要な操作があります。キューの末尾に新しい要素を挿入するenqueue() メソッドと、キューの先頭にある要素を削除するdequeue() メソッド。さらに、キューの先頭を読み取る要素もあります。このメソッドは front() メソッドと呼ばれます。このメソッドは head 要素と他のメソッドを返します。

上記の説明を見て、配列には、上記のメソッドと同様の機能を持つメソッドが 2 つあると思われるかもしれません。配列の push() メソッドも、配列に新しい要素を追加します。配列 shift() メソッドは配列の最初の要素を削除できます。次のコード: push()方法也是往数组后面加入新元素，数组中shift()方法则可以删除数组里面的第一个元素。如下代码：

var arrs = [];
arrs.push("a");
arrs.push("b");
console.log(arrs); // ["a","b"];
arrs.shift();
console.log(arrs); // [&#39;b&#39;];

ログイン後にコピー

下面我们可以使用上面的数组中的push()和shift()的2个方法来封装我们的队列Queue类；

1. 我们可以先定义一个构造函数Queue类，如下：

function Queue() {
  this.dataStore = [];
}

ログイン後にコピー

如上：this.dataStore = [];

function enqueue(element) {
   this.dataStore.push(element);
}

ログイン後にコピー

以下では、上記の配列で push() と shift() の 2 つのメソッドを使用して、キュー Queue クラスをカプセル化できます。

1. まず、次のようにコンストラクター Queue クラスを定義します。

function dequeue() {
  return this.dataStore.shift()
}

ログイン後にコピー

上記と同様: this.dataStore = []; 空の配列が使用される場合、キューが格納されます。

2. チームの末尾に要素を追加する方法は次のとおりです:

function front() {
  return this.dataStore[0];
}

ログイン後にコピー

3. チームの先頭の要素を削除する方法は次のとおりです:

function back() {
  return this.dataStore[this.dataStore.length - 1];
}

ログイン後にコピー

4. チームの先頭の要素を読み取る方法は次のとおりです。

function toString() {
  var retStr = "";
  for(var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i] + "\n";
  }
  return retStr;
}

ログイン後にコピー

5. 次のようにキューの最後にある要素を読み取ります。

function empty(){
  if(this.dataStore.length == 0) {
    return true;
  }else {
    return false;
  }
}

ログイン後にコピー

6. 内のすべての要素を表示します。キュー

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  }
};

ログイン後にコピー

7. キューが空かどうかを次のように判断します:

var q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.toString()); // a b c
q.dequeue();
console.log(q.toString()); // b c
console.log("Front of queue:" +q.front()); // b
console.log("Back of queue:" +q.back()); // c

ログイン後にコピー

以下は完了です。 JS コードは次のとおりです:

var nums = ["50","12","95","7","90","3","74","81","91","72"];

ログイン後にコピー

これで、上記のコードをテストできます。次のように:

queues[0] = 50 或者 90
queues[1] = 81 或者 91
queues[2] = 12 或者 72
queues[3] = 3
queues[4] = 74
queues[5] = 95
queues[6] 
queues[7] = 7
queues[8]
queues[9]

ログイン後にコピー

2: キューを使用してデータを並べ替える

たとえば、数値を 0 ~ 99 まで並べ替える場合、原則として、最初に数値を 1 の位で並べ替え、次に数値を並べ替えます。また十の位に。各数値を対応する桁の値に応じて異なるボックスに分割し、1 桁の数値については剰余法が使用され、10 桁目の数値については除算法が使用されます。このソートが呼び出されます。「基数ソート」。これは最速のソート方法ではありませんが、キューを使用するいくつかの興味深い方法について説明しています。

たとえば、次の配列:

nums = [50,90,81,91,12,72,3,74,95,7]

ログイン後にコピー

1. 基数ソート - 単位ソートの後、数値は別のボックスに分配されます。 (JS では、これをさまざまな Queue インスタンスクラスに割り当てることができます)。以下のように

queues[5] = 50
queues[9] = 90
queues[8] = 81
queues[9] = 91
queues[1] = 12
queues[7] = 72
queues[0] = 3
queues[7] = 74
queues[9] = 95
queues[0] = 7

ログイン後にコピー

ボックスの順序に従って、数字の最初の 1 の桁を並べ替えた結果は次のとおりです。

nums = [3,7,12,50,72,74,81,90,91,95];

ログイン後にコピー

2. 次に、10 の位の値に従って、最後の並べ替え後の結果は、ボックス内の異なる値に割り当てられます。次のように:

/*
* 根据个位或十位上的数值，将数字分配到相应队列的函数
* @param digit
* digit=1 表示先按个位来分配
* digit = 10 表示是按十位来分配的
* @param n 表示循环比较多少次 一般数组几个数字就比较多少次
*/
distribute: function(nums,queues,n,digit){
   for(var i = 0; i < n; ++i) {
    if(digit == 1) {
      queues[nums[i] % 10].enqueue(nums[i]);
     }else {
      queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
     }
   }
}

ログイン後にコピー

最後に、ボックス内の数字を取り出して、並べ替えられた数字である新しいリストを作成します。以下のように:

は次のように生成できます:

// 收集数字的函数
collect: function(queues,nums,n) {
  var i = 0;
  for(var digit = 0; digit < n; ++digit) {
    while(!queues[digit].empty()) {
      nums[i++] = queues[digit].dequeue();
    }
  }
}

ログイン後にコピー

上記のようにキューリストボックスを使用すると、このアルゴリズムを実装できます。各キューは番号に対応し、すべてのキューを配列に保存します。そして fetch を使用します。剰余演算と除算演算により、一の位と十の位が決まります。アルゴリズムの残りの部分では、対応するキューに数値を追加し、1 桁の値に基づいてそれらを並べ替え、次に 10 桁の値に基づいて並べ替え、その結果として並べ替えられた数値を追加します。

以下は、一の位または十の位の値に基づいて、対応するキューに番号を割り当てる関数です。

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  },
  /*
   * 根据个位或十位上的数值，将数字分配到相应队列的函数
   * @param digit
   * digit=1 表示先按个位来分配
   * digit = 10 表示是按十位来分配的
   * @param n 表示循环比较多少次 一般数组几个数字就比较多少次
   */
  distribute: function(nums,queues,n,digit){
    for(var i = 0; i < n; ++i) {
      if(digit == 1) {
        queues[nums[i] % 10].enqueue(nums[i]);
      }else {
        queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
      }
    }
  },
  // 收集数字的函数
  collect: function(queues,nums,n) {
    var i = 0;
    for(var digit = 0; digit < n; ++digit) {
      while(!queues[digit].empty()) {
        nums[i++] = queues[digit].dequeue();
      }
    }
  },
  dispArray: function(arr) {
    for(var i = 0; i < arr.length; ++i) {
      console.log(arr[i]);
    }
  }
};

ログイン後にコピー

以下はキューから数値を収集する関数です:

var q = new Queue();
  q.enqueue("a");
  q.enqueue("b");
  q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue:" +q.front());
console.log("Back of queue:" +q.back());
var queues = [];
for(var i = 0; i < 10; ++i) {
   queues[i] = new Queue();
}
var nums = ["50","12","95","7","90","3","74","81","91","72"];
console.log("before radix sort: ");
console.log(nums);
q.distribute(nums,queues,10,1);
q.collect(queues,nums,10);
q.dispArray(nums);
console.log("分割线");
q.distribute(nums,queues,10,10);
q.collect(queues,nums,10);
q.dispArray(nums);

ログイン後にコピー

上記では多くのステップが省略されているため、説明があまり明確ではないかもしれません。まずフローチャートを見てみましょう。フローチャートと組み合わせると、最後に、すべての JS コードを組み合わせることで、「基数ソート」の基本原理を理解できます

🎜🎜次のように: 🎜🎜🎜🎜rrreee🎜 以下は、「基数ソート」の JS コードをテストします: 🎜🎜🎜🎜

var q = new Queue();
  q.enqueue("a");
  q.enqueue("b");
  q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue:" +q.front());
console.log("Back of queue:" +q.back());
var queues = [];
for(var i = 0; i < 10; ++i) {
   queues[i] = new Queue();
}
var nums = ["50","12","95","7","90","3","74","81","91","72"];
console.log("before radix sort: ");
console.log(nums);
q.distribute(nums,queues,10,1);
q.collect(queues,nums,10);
q.dispArray(nums);
console.log("分割线");
q.distribute(nums,queues,10,10);
q.collect(queues,nums,10);
q.dispArray(nums);

ログイン後にコピー