de Prashant Yadav
Cum se implementează o stivă în JavaScript vanilat și ES6
A grămadă este o colecție comandată de articole care urmează Last In First Out (LIFO) principiul. Adăugarea și îndepărtarea articolelor au loc la același capăt, adică în partea de sus. Cele mai noi elemente sunt în partea de sus, iar cele mai vechi elemente sunt în partea de jos.
Avem multe exemple de stive în jurul nostru ca o grămadă de cărți, un teanc de tăvi sau vase etc.
A Grămadă este utilizat de compilatoare în limbaje de programare, de memorie de calculator pentru a stoca variabile și apeluri de funcții, și în editorii de text pentru a efectua operații de anulare și refacere.
Lista operațiunilor efectuate pe Stack
- Apăsați(): Adaugă un singur sau mai multe articole în partea de sus a stivei.
- pop (): Elimină și returnează elementul de sus al stivei.
- arunca o privire(): Returnează elementul de sus al stivei.
-
este gol(): Se intoarce
Truedacă Stack este gol,Falsein caz contrar. - clar(): Elimină toate articolele din stivă.
- mărimea(): Returnează lungimea stivei.
Crearea unei stive
O abordare clasică
Vom implementa un grămadă cum ar fi modul în care este implementat în alte limbi în afară de JavaScript.
Vom folosi un matrice si un variabilă suplimentară pentru a urmări obiectele.
function Stack(){ var items = []; var top = 0; //other methods go here }Împingeți un obiect în stivă
//Push an item in the Stackthis.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the valueScoateți un articol din Stack
//Pop an item from the Stackthis.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operationAruncați o privire pe elementul superior din stivă
//peek an item in the Stackthis.peek = function(){ return items[top - 1]; }Verificați dacă Stack este gol
//Is stack emptythis.isEmpty = function(){ return top === 0; }Ștergeți stiva
//clear the stackthis.clear= function(){ top = 0; }Dimensiunea stivei
//Size of the Stackthis.size = function(){ return top; }Implementarea completă a stivei
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; }}Exemplu
Acum vom crea o nouă instanță a ceea ce am implementat și vom verifica dacă funcționează corect.
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 trueImplementarea stivei cu JavaScript
Vom implementa o stivă cu un JavaScript matrice care are metode încorporate precum Apăsați și pop.
function Stack(){ var items = []; //other methods go here }Împingeți un obiect în stivă
//push an item in the Stackthis.push = function(element){ items.push(element); }Scoateți un articol din Stack
//Pop an item from the Stackthis.pop = function(){ return items.pop(); }Aruncați o privire pe elementul superior din stivă
//Peek top item of the Stackthis.peek = function(){ return items[items.length - 1]; }Verificați dacă Stack este gol
//Is Stack emptythis.isEmpty = function(){ return items.length === 0; }Ștergeți stiva
//Clear the Stackthis.clear = function(){ items.length = 0; }Dimensiunea stivei
//Size of the Stackthis.size = function(){ return items.length; }Implementarea completă a 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; } }Facerea proprietăților și metodelor private cu închidere și IIFE (Expresia funcției invocată imediat).
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; } }})();Stiva folosind 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; }}Stiva folosind 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; }}Facerea proprietăților și metodelor private cu închidere și IIFE (Expresie funcție imediat invocată) pentru utilizarea Stack 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; } }})();Complexitatea timpului
# In medie
Acces: Θ (N)
Căutare: Θ (N)
Inserați: Θ (1)
Șterge: Θ (1)
# Cel mai rău
Acces: O (N)
Cauta pe)
Inserați: O (1)
Șterge: O (1)
Complexitatea spațială
# Cel mai rău: PE)
Există o mulțime de probleme în care Stack poate fi structura de date perfectă necesară soluției.
Dacă ți-a plăcut acest articol, te rog dă-i câteva? Și împărtășește-l! Dacă aveți întrebări legate de acest lucru, nu ezitați să mă întrebați.
Pentru mai multe astfel de soluții și soluții algoritmice în Javascript, urmați-mă Stare de nervozitate. Scriu despre ES6, React, Nodejs, Structuri de date, și Algoritmi pe learnersbucket.com.
