JavaScript-Datenstrukturen und Algorithmen, Stapel und Warteschlangen

Ursache des Lernens

Ich bin einmal auf einen solchen Beitrag gestoßen, als ich V2EX durchstöberte.
Die Mathematik wird komplett dem Lehrer überlassen. Ich möchte einige grundlegende Mathematikkenntnisse erlernen, wahrscheinlich auf High-School-Niveau. Welche Bücher empfehlen Sie?
Der Verfasser der Nachricht verfügte nicht über Kurse für fortgeschrittene Mathematik an der Universität und war mit Front-End-Arbeit beschäftigt, als er zur Arbeit ging. Ich habe das Gefühl, dass meine mathematischen Kenntnisse fehlen, deshalb möchte ich Mathematik nachholen.
Nachdem ich den Beitrag gelesen habe, habe ich das Gefühl, dass er mir sehr ähnlich ist, da mein Hauptfach keine fortgeschrittene Mathematik erfordert und ich auch Front-End studiere. Ich habe auch die Schwierigkeiten gespürt, die durch den Mangel an mathematischen Kenntnissen entstehen. Da mein mathematisches Denken wirklich nicht sehr gut ist, beschloss ich gleichzeitig, hart zu arbeiten, um grundlegende Mathematik- und Computerkenntnisse zu erlernen.
Damals sagten einige Leute auch: „Welche Datenstrukturen und Algorithmen werden für das Frontend benötigt?“ Aber ich habe meine eigenen Ansichten zu diesem Thema.
Ich glaube nicht, dass das Front-End keine Kenntnisse wie Algorithmen benötigt. Meiner Meinung nach verfügt das Front-End über eine solide Computerbasis, was für die eigene Entwicklung äußerst vorteilhaft ist. Ich möchte Programmierer werden. Anstatt ein lebenslanger Junior-Frontend und Programmierer zu sein.
Es kann als Ermutigung für mich selbst angesehen werden. Schließlich bestimmen die Grundlagen die Obergrenze, und ich interessiere mich wirklich für Computer. Auch wenn das Lernen ermüdend ist, ist es auch sehr glücklich. Also ging ich online und kaufte das Buch „Learning JavaScript Data Structures and Algorithms“ und begann zusammen mit dem Buch „Dahua Data Structures“, das ich mir aus der Bibliothek ausgeliehen hatte, mit meinem Vorstudium über Datenstrukturen und Algorithmen.

Array-Operationen in JavaScipt

Der nächste Schritt ist der erste Teil der Datenstruktur, der Stack.
Der Stapel ist eine geordnete Sammlung, die dem Last-In-First-Out-Prinzip (LIFO, vollständiger Name: Last In First Out) folgt. Das oberste Element im Stapel ist immer das neueste Element.
Beispiel: Ein Stapel ist wie ein Stapel Bücher in einer Kiste. Wenn Sie das unterste Buch nehmen möchten, müssen Sie zuerst das oberste Buch entfernen. (Natürlich können Sie nicht zuerst das Buch unten nehmen.)

Implementierung des Stacks in JavaScipt
Erstellen Sie zunächst einen Konstruktor.

/**
 * 栈的构造函数
 */
function Stack() {

 // 用数组来模拟栈
 var item = [];
}

Nach dem Login kopieren

Der Stapel muss über die folgenden Methoden verfügen:
push(element(s)): Füge mehrere Elemente oben im Stapel hinzu
pop(): Entferne das oberste Element des Stapels und gib es zurück
peek(): Gibt das oberste Element des Stapels
zurück isAmpty: Überprüfen Sie, ob der Stapel leer ist. Wenn er leer ist, geben Sie true zurück
klar: alle Elemente vom Stapel entfernen
Größe: Gibt die Anzahl der Elemente im Stapel zurück.
Drucken: Zeigt den gesamten Inhalt des Stapels als Zeichenfolge
an Implementierung der Push-Methode
Erläuterung: Dem Stapel muss ein neues Element hinzugefügt werden, und die Elementposition befindet sich am Ende der Warteschlange. Mit anderen Worten: Wir können die Push-Methode des Arrays verwenden, um die Implementierung zu simulieren.

Umsetzung:

/**
 * 将元素送入栈，放置于数组的最后一位
 * @param {Any} element 接受的元素，不限制类型
 */
this.push = function(element) {
 items.push(element);
};

Nach dem Login kopieren

Implementierung der Pop-Methode

Erklärung: Es ist notwendig, das oberste Element des Stapels zu entfernen und gleichzeitig den entnommenen Wert zurückzugeben. Sie können die Pop-Methode des Arrays verwenden, um die Implementierung zu simulieren.
Umsetzung:

/**
 * 弹出栈顶元素
 * @return {Any} 返回被弹出的值
 */
this.pop = function() {
 return items.pop();
};

Nach dem Login kopieren

Implementierung der Peek-Methode
Hinweis: Die Anzeige des obersten Elements des Stapels kann mithilfe der Array-Länge erfolgen.
Umsetzung:

/**
 * 查看栈顶元素
 * @return {Any} 返回栈顶元素
 */
this.peek = function() {
 return items[items.length - 1];
}

Nach dem Login kopieren

Implementierung anderer Methoden
Hinweis: Die ersten drei sind der Kern der Stack-Methode, die übrigen Methoden werden hier gleichzeitig aufgelistet. Denn die unten besprochene Warteschlange wird sich stark mit diesem Teil überschneiden.
Umsetzung:

/**
 * 确定栈是否为空
 * @return {Boolean} 若栈为空则返回true,不为空则返回false
 */
this.isAmpty = function() {
 return items.length === 0
};

/**
 * 清空栈中所有内容
 */
this.clear = function() {
 items = [];
};

/**
 * 返回栈的长度
 * @return {Number} 栈的长度
 */
this.size = function() {
 return items.length;
};

/**
 * 以字符串显示栈中所有内容
 */
this.print = function() {
 console.log(items.toString());
};

Nach dem Login kopieren

Praktische Anwendung

Es gibt viele praktische Anwendungen des Stapels. Es gibt eine Funktion im Buch, die Dezimalzahlen in Binärzahlen umwandelt. (Wenn Sie nicht wissen, wie man binär rechnet, können Sie Baidu verwenden.) Im Folgenden finden Sie den Quellcode der Funktion.
Das Prinzip besteht darin, die umzurechnende Zahl einzugeben, fortlaufend durch zwei zu dividieren und zu runden. Und schließlich verwenden Sie eine While-Schleife, um alle Zahlen im Stapel für die Ausgabe zu einer Zeichenfolge zu verketten.

/**
 * 将10进制数字转为2进制数字
 * @param {Number} decNumber 要转换的10进制数字
 * @return {Number}      转换后的2进制数字
 */
function divideBy2(decNumber) {

 var remStack = new Stack(),
  rem,
  binaryString = '';

 while (decNumber > 0) {
  rem = Math.floor(decNumber % 2);
  remStack.push(rem);
  decNumber = Math.floor(decNumber / 2);
 }

 while (!remStack.isAmpty()) {
  binaryString += remStack.pop().toString();
 }

 return binaryString;
};

Nach dem Login kopieren

An diesem Punkt endet das Studium des Stapels. Da der Quellcode viele Kommentare enthält, wird der Inhalt des Quellcodes hier nicht veröffentlicht.

Warteschlange

Warteschlange und Stapel sind sehr ähnliche Datenstrukturen. Der Unterschied besteht darin, dass die Warteschlange zuerst eingeht (FIFO: First In First Out).
Zum Beispiel: Wenn man am Bahnhof Schlange steht, um Fahrkarten zu kaufen, gilt: Wer zuerst kommt, mahlt zuerst. (Diejenigen, die sich anstellen, werden nicht mitgezählt.)

Implementierung der Warteschlange in JavaScipt

Die Implementierung der Warteschlange ist der des Stapels sehr ähnlich. Der erste ist immer noch der Konstruktor:

/**
 * 队列构造函数
 */
function Queue() {
 var items = [];
}

Nach dem Login kopieren

Die Warteschlange muss über die folgenden Methoden verfügen:

enqueue(element(s)): Mehrere Elemente am Ende der Warteschlange hinzufügen
dequeue(): Entfernen Sie das erste Element der Warteschlange (d. h. das oberste Element)
front(): Gibt das erste Element der Warteschlange zurück, das das zuletzt hinzugefügte
ist Die übrigen Methoden sind die gleichen wie bei queue

Implementierung der Enqueue-Methode

Beschreibung: Mehrere Elemente am Ende der Warteschlange hinzufügen.

Umsetzung:

/**
 * 将元素推入队列尾部
 * @param {Any} ele 要推入队列的元素
 */
this.enqueue = function(ele) {
 items.push(ele);
};

Nach dem Login kopieren

Implementierung der Dequeue-Methode

Beschreibung: Entfernen Sie das erste Element aus der Warteschlange.

Umsetzung:

/**
 * 将队列中第一个元素弹出
 * @return {Any} 返回被弹出的元素
 */
this.dequeue = function() {
 return items.shift()
};

Nach dem Login kopieren

Implementierung der Front-Methode

Beschreibung: Gibt das erste Element der Warteschlange zurück, also das zuletzt hinzugefügte.

Umsetzung:

/**
 * 查看队列的第一个元素
 * @return {Any} 返回队列中第一个元素
 */
this.front = function() {
 return items[0];
};

Nach dem Login kopieren

以上的三个方法，就是队列这种数据结构的核心方法了。其实很好理解的。

实际应用
书上的是个击鼓传花的小游戏。原理就是循环到相应位置时，队列弹出那个元素。最后留下的就是赢家。
源代码如下:

/**
 * 击鼓传花的小游戏
 * @param {Array} nameList 参与人员列表
 * @param {Number} num   在循环中要被弹出的位置
 * @return {String}     返回赢家(也就是最后活下来的那个)
 */
function hotPotato(nameList, num) {
 var queue = new Queue();

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

 var eliminated = '';

 while (queue.size() > 1) {
  for (var i = 0; i < num; i++) {
   queue.enqueue(queue.dequeue());
  }

  eliminated = queue.dequeue();
  console.log(eliminated + " Get out!")
 }

 return queue.dequeue()
}

Nach dem Login kopieren

队列的学习到此就告一段落了。下一期将讲述另外一种数据结构: 链表。

感想

很多时候看书，直接看算法导论或者一些数据结构的书，都是很迷糊的。后来才发现，看书从自己能看懂的开始，由浅入深才是适合自己的学习方式。