Heim > Artikel > Web-Frontend > So implementieren Sie einen Stack in JavaScript

So implementieren Sie einen Stack in JavaScript

不言Original: 2018-07-11 16:54:124552Durchsuche

In diesem Artikel wird hauptsächlich die Verwendung von JavaScript zum Implementieren eines Stapels vorgestellt, der einen bestimmten Referenzwert hat. Jetzt können Freunde in Not darauf verweisen.

Was ist ein Stapel?

Ein Stapel ist eine geordnete Sammlung, die dem Last-In-First-Out (LIFO)-Prinzip folgt.
Neu hinzugefügte oder zu löschende Elemente werden am Ende des Stapels gespeichert, das als Oberseite des Stapels bezeichnet wird, und das andere Ende wird als Unterseite des Stapels bezeichnet.
Im Stapel befinden sich neue Elemente oben im Stapel und alte Elemente unten im Stapel

Beispiele aus dem wirklichen Leben

Im Leben gibt es viele Beispiele für Stacks. Beispielsweise werden von den in der Küche gestapelten Tellern immer zuerst die oben gestapelten verwendet; wenn der Inhalt des Eingabefelds gelöscht wird, werden die Kugeln im Magazin immer zuerst gelöscht, so wie sie sind später geladen. ....

Manuell einen Stapel implementieren

Erstellen Sie zunächst eine Klasse zur Darstellung des Stapels

function Stack () { }

Wir müssen eine Datenstruktur auswählen, um die Elemente zu speichern Im Stapel können Sie das Array auswählen

function Stack(){
    var items = [];     //用来保存栈里的元素
}

Als nächstes einige Methoden zum Stapel hinzufügen

push(element(s));   //添加新元素到栈顶
pop();              //移除栈顶的元素，同时返回被移除的元素
peek();             //返回栈顶的元素，不对栈做任何修改
isEmpty();          //如果栈里没有任何元素就返回true，否则false
clear();            //移除栈里的所有元素
size();             //返回栈里的元素个数,类似于数组的length属性

Die erste Methode, die wir implementieren müssenpush. Beim Hinzufügen neuer Elemente zum Stapel ist eines sehr wichtig: Bei dieser Methode wird nur der obere Teil des Stapels hinzugefügt, der das Ende des Stapels darstellt. Daher können Sie es so schreiben:

this.push = function (element) {
    items.push(element);
}

Mit der Push-Methode des Arrays können Sie neue Elemente am Ende der Oberseite des Stapels hinzufügen.

Als nächstes implementieren Sie die Methode pop, um Elemente aus dem Stapel zu entfernen. Der Stapel folgt dem LIFO-Prinzip (last in, first out). Was entfernt wird, ist das letzte hinzugefügte Element. Daher können Sie die Pop-Methode des Arrays verwenden.

this.pop = function () {
    return items.pop();
}

Auf diese Weise folgt dieser Stack natürlich dem LIFO-Prinzip

Jetzt fügen wir diesem Stack weitere Hilfsmethoden hinzu.

Wenn Sie wissen möchten, welches Element zuletzt zum Stapel hinzugefügt wurde, können Sie die Methode peek verwenden. Diese Methode gibt das Element oben im Stapel zurück

this.peek = function () {
    return items[items.length-1];
}

Da die Klasse ein Array zum Speichern der Elemente verwendet, verwenden Sie hier für den Zugriff auf das letzte Element des Arrays length-1

Die nächste zu implementierende Methode ist isEmpty. Wenn der Stapel leer ist, wird true zurückgegeben, andernfalls wird false zurückgegeben:

this.isEmpty = function () {
    return items.length == 0;
}

Mit der Methode isEmpty können Sie einfach feststellen, ob der Stapel leer ist.

Ähnlich wie die Längeneigenschaft des Arrays können wir auch die Länge des Stapels implementieren.

this.size = function () {
    return items.length;
}

Da der Stapel intern ein Array zum Speichern von Elementen verwendet, entspricht die Länge des Arrays der Länge des Stapels.

implementiert die clear-Methode und die Clear-Methode wird verwendet, um alle Elemente im Stapel zu löschen. Die einfachste Implementierungsmethode ist:

this.clear = function () {
    items = [];
}

Tatsächlich können Sie die Pop-Methode auch mehrmals aufrufen, sie ist jedoch nicht so einfach und schnell wie diese Methode.

Um schließlich den Inhalt des Stapels zu überprüfen, müssen Sie eine Hilfsmethode implementieren: print. Es werden alle Elemente im Stapel an die Konsole ausgegeben:

this.print = function () {
    console.log(items.toString());
}

An diesem Punkt haben wir vollständig einen Stack erstellt!

Der vollständige Code des Stapels

function Stack(){

    var items = [];     //用来保存栈里的元素

    this.push = function (element) {
        items.push(element);
    }

    this.pop = function () {
        return items.pop();
    }

    this.peek = function () {
        return items[items.length-1];
    }

    this.isEmpty = function () {
        return items.length == 0;
    }

    this.size = function () {
        return items.length;
    }

    this.clear = function () {
        items = [];
    }

    this.print = function () {
        console.log(items.toString());
    }
}

Verwenden Sie die Stack-Klasse

Der Stack wurde erstellt, testen wir ihn

Zuerst initialisieren Sie die Stack-Klasse. Überprüfen Sie dann, ob der Stapel leer ist.

var stack = new Stack();
console.log(stack.isEmpty());         //控制台输出true

Fügen Sie als Nächstes ein Element zum Stapel hinzu:

stack.push(5);
stack.push(8);

Wenn Sie die Peek-Methode aufrufen, wird offensichtlich 8 ausgegeben, da es sich oben befindet des Stapelelements:

console.log(stack.peek());            //控制台输出8

Ein weiteres Element hinzufügen:

stack.push(11);
console.log(stack.size());            //控制台输出3

Wir fügen dem Stapel weitere 11 hinzu. Wenn die Größenmethode aufgerufen wird, ist die Ausgabe 3, da sich drei Elemente auf dem Stapel befinden (5, 8 und 11). Wenn Sie zu diesem Zeitpunkt die Methode isEmpty aufrufen, wird eine falsche Ausgabe angezeigt (da der Stapel zu diesem Zeitpunkt nicht leer ist). Fügen Sie abschließend ein weiteres Element hinzu:

stack.push(15);

Rufen Sie dann die Pop-Methode zweimal auf, um zwei Elemente aus dem Stapel zu entfernen:

stack.pop();
stack.pop();
console.log(stack.size());            //控制台输出2
stack.print();                        //控制台输出[5,8]

An diesem Punkt ist der Funktionstest des gesamten Stapels abgeschlossen .

Verwenden Sie den Stapel, um das Problem zu lösen

Verwenden Sie den Stapel, um die Hexadezimalkonvertierung abzuschließen.

Im wirklichen Leben verwenden wir hauptsächlich die Basis 10, aber in der Informatik ist die Binärzahl sehr wichtig, da alles im Computer durch die Binärzahlen 0 und 1 dargestellt wird. In Computerkursen an Universitäten wird zunächst die Basiskonvertierung gelehrt. Nehmen wir als Beispiel die Binärdatei:

So implementieren Sie einen Stack in JavaScript

function pideBy2 (decNumber) {

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

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

    while (!remStack.isEmpty()) {  //{5}
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

Wenn in diesem Code das Ergebnis die Bedingung erfüllt, durch 2 teilbar zu sein (Zeile {1}), erhalten wir den Strom Ergebnis und der Rest von 2 wird auf den Stapel gelegt (Zeilen {2}, {3}). Dann lassen Sie das Ergebnis gleichmäßig durch 2 dividieren (Zeile {4})

Hinweis: JavaScript hat einen Zahlentyp, unterscheidet jedoch nicht zwischen Ganzzahlen und Gleitkommazahlen. Verwenden Sie daher die Funktion Math.floor, damit die Divisionsoperation nur den ganzzahligen Teil zurückgibt.

Abschließend verwenden Sie die Pop-Methode, um alle Elemente aus dem Stapel zu entfernen und die gepoppten Elemente zu einer Zeichenfolge zu verketten (Zeile {5}).

Testen Sie es:

console.log(pideBy2(520));      //输出1000001000
console.log(pideBy2(10));       //输出1010
console.log(pideBy2(1000));     //输出1111101000

Als nächstes können Sie den obigen Algorithmus einfach ändern, sodass er Dezimalzahlen in jede Basis konvertieren kann. Neben der Umwandlung von Dezimalzahlen und der Teilbarkeit durch 2 in Binärzahlen können Sie auch andere beliebige Basen als Parameter übergeben, wie den folgenden Algorithmus:

function baseConverter (decNumber, base) {

    var remStack = new Stack(),
    rem,
    baseString = '';
    digits = '0123456789ABCDEF';     //{6}

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

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];  //{7}
    }

    return baseString;
}

在将十进制转成二进制时，余数是0或1；在将十进制转成八进制时，余数时0-8之间的数；但是将十进制转成十六进制时，余数时0-9之间的数字加上A、B、C、D、E、F（对应10、11、12、13、14和15）。因此，需要对栈中的数字做个转化才可以（行{6}、{7}）。

来测试一下输出结果：

console.log(baseConverter(1231,2));      //输出10011001111
console.log(baseConverter(1231,8));      //输出2317
console.log(baseConverter(1231,16));     //输出4CF

显然是正确的。

小结

我们用js代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多，比如平衡圆括号和汉诺塔。

以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！

In Verbindung stehende Artikel

Mehr sehen