Ausführliche Erläuterung der Prinzipien der JavaScript-Warteschlange und Anwendungsbeispiele-js-Tutorial-php.cn

Eine Warteschlange ist eine Art Liste. Der Unterschied besteht darin, dass eine Warteschlange nur Elemente am Ende der Warteschlange einfügen und Elemente am Anfang der Warteschlange löschen kann. Warteschlangen werden zum Speichern von Daten in der Reihenfolge „First In, First Out“ verwendet, was sich von Stapeln (Last In, First Out) unterscheidet. Im Stapel wird das zuletzt auf den Stapel geschobene Element zuerst verarbeitet. Wir können uns die Warteschlange jetzt so vorstellen, als würden wir in ein Restaurant gehen, um zu essen. Viele Leute stehen zum Essen an und die Person vorne bekommt ihr Essen zuerst. Neulinge können sich nur hinten anstellen. bis sie an der Reihe sind. In diesem Artikel werden hauptsächlich die Prinzipien und die Verwendung von Warteschlangen in JavaScript-Datenstrukturen und -Algorithmen vorgestellt, die Konzepte und Prinzipien von Warteschlangen ausführlicher erläutert und die zugehörigen Betriebstechniken und Vorsichtsmaßnahmen für die Implementierung und Verwendung von Warteschlangen in JavaScript anhand von Beispielen analysiert In Not können Sie sich auf Next beziehen. Ich hoffe, es kann allen helfen.

1: Operationen in der Warteschlange

Die Warteschlange hat zwei Hauptoperationen: das Einfügen neuer Elemente am Ende der Warteschlange enqueue ( )-Methode und die dequeue()-Methode, die das Element an der Spitze der Warteschlange löscht. Darüber hinaus haben wir auch eine Methode, die das Element an der Spitze der Warteschlange liest Wir können die front()Methode aufrufen. Diese Methode gibt das Head-Element und andere Methoden zurück.

Nachdem wir die obige Beschreibung gelesen haben, denken viele von uns möglicherweise an Arrays. Es gibt auch zwei Methoden in Arrays, die ähnliche Funktionen wie die oben genannten Methoden haben. Die push()-Methode in Array fügt auch neue Elemente hinzu des Arrays. Die shift()-Methode kann das erste Element im Array löschen. Der folgende Code:

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

Nach dem Login kopieren

Unten können wir die beiden Methoden push() und shift() im Array oben verwenden, um unsere Warteschlangenklasse zu kapseln; >

1. Wir können zunächst eine Konstruktor-Warteschlangenklasse wie folgt definieren:

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

Nach dem Login kopieren

Wie oben:

Wenn das Array leer ist, werden alle Elemente in der Warteschlange werden elementar gespeichert. this.dataStore = [];

2. Die Methode zum Hinzufügen eines Elements zum Ende der Warteschlange ist wie folgt:

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

Nach dem Login kopieren

3. Die Methode zum Löschen des Elements des Leiters der Warteschlange lautet wie folgt:

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

Nach dem Login kopieren

4. Die Elemente zum Lesen des Leiters des Teams lauten wie folgt:

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

Nach dem Login kopieren

5. Die Elemente, um den Schwanz des Teams zu lesen, sind wie folgt:

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

Nach dem Login kopieren

6 die Warteschlange

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

Nach dem Login kopieren

7. Bestimmen Sie wie folgt, ob die Warteschlange leer ist:

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

Nach dem Login kopieren

Das Folgende ist der vollständige JS-Code wie folgt:

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

Nach dem Login kopieren

Wir sind jetzt Sie können den obigen Code testen: wie folgt:

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

Nach dem Login kopieren

2: Verwenden Sie Warteschlangen zum Sortieren von Daten

Beim Sortieren von Zahlen von 0 bis 99 gilt beispielsweise das Prinzip: Zuerst Sortieren Sie die Zahlen nach der Einerstelle und sortieren Sie dann die Zahlen nach der Zehnerstelle erneut. Jede Zahl wird entsprechend dem Wert der entsprechenden Ziffer in verschiedene Felder unterteilt, und dann wird die Restmethode für die Zahlen in der Einerstelle und die Divisionsmethode für die Zahlen in der 10. Stelle verwendet. Dann wird diese Sortierung aufgerufen „Radix-Sortierung“ Es ist nicht die schnellste Sortiermethode, beschreibt aber einige interessante Möglichkeiten, Warteschlangen zu verwenden.

Zum Beispiel das folgende Array:

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

Nach dem Login kopieren

1. Nach der Basissortierung – Einheitensortierung werden die Zahlen in verschiedene Felder verteilt. (In JS können wir es verschiedenen Queue-Instanzklassen zuweisen.) Wie folgt

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]

Nach dem Login kopieren

Gemäß der Reihenfolge der Kästchen sind die Ergebnisse nach dem Sortieren der ersten Ziffern der Zahlen wie folgt:

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

Nach dem Login kopieren

2. Ordnen Sie dann die Ergebnisse der letzten Sortierung entsprechend dem Wert an der Zehnerstelle verschiedenen Kästchen zu. Wie folgt:

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

Nach dem Login kopieren

Nehmen Sie abschließend die Zahlen aus der Box, um eine neue Liste zu erstellen, die die sortierte Zahl darstellt. Wie folgt:

kann wie folgt generiert werden:

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

Nach dem Login kopieren

Mit dem Warteschlangenlistenfeld wie oben kann dieser Algorithmus implementiert werden. Wir benötigen 10 Warteschlangen, jede Die Warteschlange entspricht einer Zahl, speichert alle Warteschlangen in einem Array und verwendet Rest- und Divisionsoperationen, um die Einer- und Zehnerstellen zu bestimmen. Der Rest des Algorithmus fügt die Zahlen der entsprechenden Warteschlange hinzu, ordnet sie basierend auf dem Einsenwert neu, sortiert sie dann basierend auf dem Zehnerwert und fügt als Ergebnis die sortierten Zahlen hinzu.

Die folgende Funktion weist Zahlen basierend auf dem Wert an der Einer- oder Zehnerstelle der entsprechenden Warteschlange zu.

/*
* 根据个位或十位上的数值，将数字分配到相应队列的函数
* @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]);
     }
   }
}

Nach dem Login kopieren

Die folgende Funktion dient zum Sammeln von Nummern aus der Warteschlange wie folgt:

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

Nach dem Login kopieren

Aufgrund der oben genannten Auslassungen gibt es viele Schritte und die Beschreibung ist möglicherweise nicht sehr klar. Schauen wir uns zunächst das Flussdiagramm an, kombinieren es mit dem Flussdiagramm und kombinieren es schließlich mit dem gesamten JS-Code, um das Grundprinzip zu verstehen von „Radix-Sortierung“; unten können wir uns das folgende Prozessbild ansehen:

Schließlich sind alle JS-Codes wie folgt:

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

Nach dem Login kopieren

Das Folgende ist der „Radix-Sort“-JS-Code zum Testen; der folgende Code:

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);

Nach dem Login kopieren