Sådan implementeres en stak i vanilje JavaScript og ES6

En stak er en ordnet samling af varer, der følger LIFO-princippet ( Last In First Out ). Tilføjelse og fjernelse af genstande finder sted i samme ende, dvs. øverst. De nyeste elementer er øverst, og de ældste elementer er nederst.

Vi har mange eksempler på stakke omkring os som en bunke bøger, en stak bakker eller fade osv.

En stak bruges af kompilatorer i programmeringssprog, af computerhukommelse til at gemme variabler og funktionsopkald og i teksteditorer til at udføre og fortryde handlinger.

Liste over operationer udført på Stack

  • push () : Tilføjer et enkelt eller flere elementer til toppen af ​​stakken.
  • pop () : Fjerner og returnerer det øverste element i stakken.
  • peek () : Returnerer det øverste element i stakken.
  • isEmpty () : Returnerer Truehvis Stack er tom, Falseellers.
  • clear () : Fjerner alle elementerne fra stakken.
  • størrelse () : Returnerer længden af ​​stakken.

Oprettelse af en stak

En klassisk tilgang

Vi skal implementere en stak som hvordan den implementeres på andre sprog bortset fra JavaScript.

Vi bruger en matrix og en ekstra variabel til at holde styr på elementerne.

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

Skub et element i stakken

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

Pop et element fra stakken

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

Kig topemne fra stakken

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

Kontroller, om stakken er tom

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

Ryd stakken

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

Størrelsen på stakken

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

Komplet implementering af stakken

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

Eksempel

Vi opretter nu en ny forekomst af det, vi har implementeret, og kontrollerer, om det fungerer korrekt.

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

Stakimplementering med JavaScript

Vi skal implementere en stak med et JavaScript- array, der har indbyggede metoder som push og pop.

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

Skub et element i stakken

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

Pop et element fra stakken

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

Kig topemne fra stakken

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

Kontroller, om stakken er tom

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

Ryd stakken

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

Størrelsen på stakken

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

Komplet implementering af 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; } 
}

Gør egenskaberne og metoderne private med lukning og IIFE (øjeblikkelig påkaldt funktionsudtryk).

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

Stak ved hjælp af ES6.

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

Stak ved hjælp af ES6 WeakMap.

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

Gør egenskaberne og metoderne private med lukning og IIFE (øjeblikkelig påkaldt funktionsudtryk) til Stack ved hjælp af 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; } }})();

Tidskompleksitet

# Gennemsnit

Adgang: Θ (N)

Søg: Θ (N)

Indsæt: Θ (1)

Slet: Θ (1)

# Værst

Adgang: O (N)

Søg: O (N)

Indsæt: O (1)

Slet: O (1)

Rumkompleksitet

# Værst : O (N)

Der er mange problemer, hvor Stack kan være den perfekte datastruktur, der er nødvendig for løsningen.

  • Grundkonverteringsalgoritmen
  • Balancerede parenteser

Hvis du kunne lide denne artikel, så giv den lidt? Og del den! Hvis du har spørgsmål i forbindelse med dette, er du velkommen til at stille mig.

For mere som dette og algoritmiske løsninger i Javascript, følg mig på Twitter . Jeg skriver om ES6, React, Nodejs, Datastrukturer og Algoritmer på learnersbucket.com .