Im vorherigen Blog habe ich die folgende Liste vorgestellt. Die Liste ist die einfachste Struktur, aber wenn Sie sich mit einigen komplexeren Strukturen befassen möchten, sieht die Liste zu einfach aus. Daher benötigen wir eine Datenstruktur, die der Liste ähnelt, aber komplexer ist - den Stapel. Der Stack ist eine effiziente Datenstruktur, da Daten nur oben im Stapel hinzugefügt oder gelöscht werden können, sodass dieser Vorgang sehr schnell und einfach zu implementieren ist.
1: Betrieb auf dem Stapel.
Ein Stack ist eine spezielle Liste. Die Elemente im Stapel können nur über ein Ende der Liste zugegriffen werden, und dieses Ende ist die Spitze des Stapels. Wenn Sie beispielsweise Geschirr in einem Restaurant waschen, können Sie zuerst den oberen Teller waschen. Nach dem Waschen des Geschirrs können Sie nur die Spitze des Geschirrstapels schneiden. Der Stapel wird als "LIFO-Datenstruktur" Spazy-In-First-Out "(LIFO) bezeichnet.
Da der Stapel die Eigenschaften des Back-Ins hat, kann kein Element, auf das nicht oben im Stapel zugekommen ist, nicht zugegriffen werden. Um Elemente mit niedrigem Stapel zu erhalten, muss das obige Element zuerst entfernt werden. Die beiden Hauptvorgänge, die wir mit dem Stapel ausführen können, sind, ein Element auf den Stapel zu schieben und ein Element auf den Stapel zu stecken. Beim Eingeben des Stapels können wir die Methode PUSP () -Methode verwenden, und wenn wir sie angeben, können wir die Pop () -Methode verwenden. Obwohl die POP () -Methode auf die Elemente oben im Stapel zugreifen kann, werden die Elemente oben im Stapel nach dem Aufrufen der Methode dauerhaft aus dem Stapel gelöscht. Eine andere Methode, die wir verwenden, ist Peek (), das nur das obere Element des Stapels zurückgibt, ohne ihn zu löschen.
Die tatsächlichen Säulendiagramme von Stapeleintrag und Stapelausgang sind wie folgt:
Push (), Pop () und Peek () sind die drei Hauptmethoden des Stapels, aber der Stapel hat andere Methoden und Eigenschaften. wie folgt:
Clear (): Entfernen Sie alle Elemente im Stapel.
Länge (): Notieren Sie die Anzahl der Elemente im Stapel.
Zwei: Die Implementierung des Stacks lautet wie folgt:
Wir können zunächst die Stack Class -Methode implementieren. wie folgt:
Die Codekopie lautet wie folgt:
Funktion stack () {
this.datastore = [];
this.top = 0;
}
Wie oben: DataStore speichert alle Elemente im Stapel. Die variable Top zeichnet die Position oben im Stapel auf und wird auf 0 initialisiert. Dies bedeutet, dass die Startposition des entsprechenden Arrays oben am Stapel 0 beträgt, wenn ein Element in den Stapel gedrückt wird. Der Wert dieser Variablen ändert sich entsprechend.
Wir haben auch die folgenden Methoden: push (), pop (), peek (), clear (), länge ();
1. Push () Methode; Beim Schieben eines neuen Elements in den Stapel muss es im Array gespeichert werden, das der variablen Oberseite entspricht, und dann wird der Top -Wert um 1 erhöht, sodass es auf die nächste Position im Array zeigt. Der folgende Code:
Die Codekopie lautet wie folgt:
Funktion Push (Element) {
this.datastore [this.top ++] = Element;
}
2. Die POP () -Methode ist entgegengesetzt zur PUSP () -Methode - sie gibt das obere Element zurück und zieht den Top -Wert durch 1. Der folgende Code:
Die Codekopie lautet wie folgt:
Funktion pop () {
kehre this.datastore [-this.top];
}
3. Die Peek () -Methode gibt das Element an der oberen 1-Position des Arrays zurück, dh das oberste 1-Element des Stapels;
Die Codekopie lautet wie folgt:
Funktion peek () {
zurück this.datastore [this.top - 1];
}
4. Länge () Methode Manchmal müssen wir wissen, wie viele Elemente es im Stapel gibt. Wir können die Anzahl der Elemente im Stapel zurückgeben, indem wir den variablen Top -Wert zurückgeben, wie im folgenden Code gezeigt:
Die Codekopie lautet wie folgt:
Funktionslänge () {
kehre diesen.Top zurück;
}
5. Clear (); Manchmal wollen wir den Stapel löschen und den Top -Wert der Variablen auf 0 festlegen. der folgende Code:
Die Codekopie lautet wie folgt:
Funktion clear () {
this.top = 0;
}
Alle Codes unten:
Die Codekopie lautet wie folgt:
Funktion stack () {
this.datastore = [];
this.top = 0;
}
Stack.prototype = {
// Drücken Sie ein neues Element in den Stapel
Push: Funktion (Element) {
this.datastore [this.top ++] = Element;
},
// Zugriff auf das obere Element des Stapels, das obere Element des Stapels wird dauerhaft gelöscht
pop: function () {
kehre this.datastore [-this.top];
},
// Gibt das Element an der Top-1-Position im Array zurück, dh das obere Element des Stapels
peek: function () {
zurück this.datastore [this.top - 1];
},
// Wie viele Elemente werden im Stapel gespeichert
Länge: function () {
kehre diesen.Top zurück;
},
// den Stapel löschen
klare: function () {
this.top = 0;
}
};
Beispiele für Demos sind wie folgt:
var stack = new stack ();
stack.push ("a");
stack.push ("b");
stack.push ("c");
console.log (stack.length ()); // 3
console.log (stack.peek ()); // C
var poped = stack.pop ();
console.log (knallt); // C
console.log (stack.peek ()); // B
Stack.push ("D");
console.log (stack.peek ()); // D
stack.clear ();
console.log (stack.length ()); // 0
console.log (stack.peek ()); // undefiniert
Im Folgenden können wir eine rekursive Definition einer faktoriellen Funktion implementieren. Zum Beispiel 5! Faktor 5! = 5 * 4 * 3 * 2 * 1;
Der folgende Code:
Die Codekopie lautet wie folgt:
Funktionsfakt (n) {
var s = neuer stack ();
while (n> 1) {
S.Push (n-);
}
var product = 1;
while (s.Length ()> 0) {
Produkt *= s.pop ();
}
Rückgabeprodukt;
}
console.log (Tatsache (5));
Der obige Code bedeutet: Geben Sie zuerst die Nummer 5 in die Funktion über, verwenden Sie eine while -Loop und vor dem Dekrementieren von 1 jederzeit 1 Push () der Funktion, die Sie am Stapel verwenden, bis die Variable n weniger als 1 beträgt. Dann definieren Sie ein Variablenprodukt. Bestimmen Sie, ob es nach der Länge () -Methode des Stapels größer als 0 ist und jedes Mal, wenn das Produkt* = s.pop () ausgeführt wird, gibt die POP () -Methode das obere Element des Stapels zurück und löscht das Element aus dem Stapel. Löschen Sie also jedes Mal, wenn Sie ausführen, ein Element, bis S.Length () <= 0. So product = 5*4*3*2*1. usw.