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
True
hvis Stack er tom,False
ellers. - 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 .