So implementieren Sie einen Stack in Vanilla JavaScript und ES6

Ein Stapel ist eine geordnete Sammlung von Elementen, die dem LIFO-Prinzip ( Last In First Out ) folgen. Das Hinzufügen und Entfernen von Gegenständen erfolgt am selben Ende, dh oben. Die neuesten Elemente befinden sich oben und die ältesten Elemente unten.

Wir haben viele Beispiele für Stapel um uns herum, wie einen Stapel Bücher, einen Stapel Tabletts oder Geschirr usw.

Ein Stapel wird von Compilern in Programmiersprachen, im Computerspeicher zum Speichern von Variablen und Funktionsaufrufen und in Texteditoren zum Ausführen von Rückgängig- und Wiederherstellungsvorgängen verwendet.

Liste der Operationen, die am Stapel ausgeführt wurden

  • push () : Fügt ein einzelnes oder mehrere Elemente oben im Stapel hinzu.
  • pop () : Entfernt das oberste Element des Stapels und gibt es zurück.
  • peek () : Gibt das oberste Element des Stapels zurück.
  • isEmpty () : Gibt zurück, Truewenn der Stapel leer ist, Falseandernfalls.
  • clear () : Entfernt alle Elemente aus dem Stapel.
  • size () : Gibt die Länge des Stapels zurück.

Stapel erstellen

Ein klassischer Ansatz

Wir werden einen Stack so implementieren , wie er in anderen Sprachen als JavaScript implementiert ist.

Wir werden ein Array und eine zusätzliche Variable verwenden , um die Elemente zu verfolgen.

function Stack(){ var items = []; var top = 0; //other methods go here }

Schieben Sie einen Gegenstand in den Stapel

//Push an item in the Stackthis.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value

Nimm einen Gegenstand aus dem Stapel

//Pop an item from the Stackthis.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation

Spähen Sie den obersten Gegenstand aus dem Stapel

//peek an item in the Stackthis.peek = function(){ return items[top - 1]; }

Überprüfen Sie, ob der Stapel leer ist

//Is stack emptythis.isEmpty = function(){ return top === 0; }

Löschen Sie den Stapel

//clear the stackthis.clear= function(){ top = 0; }

Größe des Stapels

//Size of the Stackthis.size = function(){ return top; }

Vollständige Implementierung des Stacks

function Stack(){ var items = []; var top = 0; //other methods go here 
 //Push an item in the Stack this.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value 
 //Pop an item from the Stack this.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation 
 //Peek top item of the Stack this.peek = function(){ return items[top - 1]; } 
 //Is Stack empty this.isEmpty = function(){ return top === 0; } 
 //Clear the Stack this.clear = function(){ top = 0; } 
 //Size of the Stack this.size = function(){ return top; }
}

Beispiel

Wir werden jetzt eine neue Instanz von dem erstellen, was wir implementiert haben, und prüfen, ob es richtig funktioniert.

var stack = new Stack(); //creating new instance of Stack stack.push(1); stack.push(2); stack.push(3); console.log(stack.peek()); console.log(stack.isEmpty()); console.log(stack.size()); console.log(stack.pop()); console.log(stack.size()); stack.clear(); console.log(stack.isEmpty()); 
Output: 3 false 3 3 2 true

Stapelimplementierung mit JavaScript

Wir werden einen Stack mit einem JavaScript- Array implementieren, das eingebaute Methoden wie Push und Pop enthält.

function Stack(){ var items = []; //other methods go here }

Schieben Sie einen Gegenstand in den Stapel

//push an item in the Stackthis.push = function(element){ items.push(element); }

Nimm einen Gegenstand aus dem Stapel

//Pop an item from the Stackthis.pop = function(){ return items.pop(); }

Spähen Sie den obersten Gegenstand aus dem Stapel

//Peek top item of the Stackthis.peek = function(){ return items[items.length - 1]; }

Überprüfen Sie, ob der Stapel leer ist

//Is Stack emptythis.isEmpty = function(){ return items.length === 0; }

Löschen Sie den Stapel

//Clear the Stackthis.clear = function(){ items.length = 0; }

Größe des Stapels

//Size of the Stackthis.size = function(){ return items.length; }

Vollständige Implementierung von Stack

function Stack(){ var items = []; //other methods go here 
 //Push a item in the Stack this.push = function(element){ items.push(element); } 
 //Pop a item from the Stack this.pop = function(){ return items.pop(); } 
 //Peek top item of the Stack this.peek = function(){ return items[items.length - 1]; }
 //Is Stack empty this.isEmpty = function(){ return items.length === 0; } 
 //Clear the Stack this.clear = function(){ items.length = 0; } 
 //Size of the Stack this.size = function(){ return items.length; } 
}

Machen Sie die Eigenschaften und Methoden mit Closure und IIFE (Sofort aufgerufener Funktionsausdruck) privat .

var Stack = (function () { return function Stack(){ var items = []; //other methods go here 
 //Push an item in the Stack this.push = function(element){ items.push(element); } 
 //Pop an item from the Stack this.pop = function(){ return items.pop(); } 
 //Peek top item from the Stack this.peek = function(){ return items[items.length - 1]; } 
 //Is Stack empty this.isEmpty = function(){ return items.length === 0; } 
 //Clear the Stack this.clear = function(){ items.length = 0; } //Size of the Stack this.size = function(){ return items.length; } }})();

Mit ES6 stapeln.

class Stack{ constructor(){ this.items = []; } //other methods go here //Push an item in the Stack push = function(element){ this.items.push(element); }
//Pop an item from the Stack pop = function(){ return this.items.pop(); } //Peek top item from the Stack peek = function(){ return this.items[this.items.length - 1]; }
//Is Stack empty isEmpty = function(){ return this.items.length === 0; }
//Clear the Stack clear = function(){ this.items.length = 0; } //Size of the Stack size = function(){ return this.items.length; }}

Mit ES6 WeakMap stapeln.

const items = new WeakMap();class Stack{ constructor(){ items.set(this, []); } //other methods go here //Push an item in the Stack push = function(element){ let temp = items.get(this); temp.push(element); }
//Pop an item from the Stack pop = function(){ let temp = items.get(this); return temp.pop(); } //Peek top item from the Stack peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
//Is Stack empty isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
//Clear the Stack clear = function(){ let temp = items.get(this); temp.length = 0; } //Size of the Stack size = function(){ let temp = items.get(this); return temp.length; }}

Privatisieren der Eigenschaften und Methoden mit Closure und IIFE (Sofort aufgerufener Funktionsausdruck) für Stack mithilfe von ES6 WeakMap.

let Stack = (() => { const items = new WeakMap(); return class Stack{ constructor(){ items.set(this, []); }
//other methods go here //Push an item in the Stack push = function(element){ let temp = items.get(this); temp.push(element); }
//Pop an item from the Stack pop = function(){ let temp = items.get(this); return temp.pop(); }
//Peek top item from the Stack peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
//Is Stack empty isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
//Clear the Stack clear = function(){ let temp = items.get(this); temp.length = 0; }
//Size of the Stack size = function(){ let temp = items.get(this); return temp.length; } }})();

Zeitliche Komplexität

# Durchschnitt

Zugang: Θ (N)

Suche: Θ (N)

Einfügen: Θ (1)

Löschen: Θ (1)

# Worst

Access: O(N)

Search: O(N)

Insert: O(1)

Delete: O(1)

Space Complexity

# Worst: O(N)

There are lots of problems where Stack can be the perfect data structure needed for the solution.

  • The base converter algorithm
  • Balanced Parentheses

If you liked this article, please give it some ?and share it! If you have any questions related to this feel free to ask me.

For more like this and algorithmic solutions in Javascript, follow me on Twitter. I write about ES6, React, Nodejs, Data structures, and Algorithms on learnersbucket.com.