Kako implementirati stog u vanilin JavaScript i ES6

Stog je naredio skup predmeta koji slijede posljednji u prvi van (LIFO) princip. Dodavanje i uklanjanje predmeta odvija se na istom kraju, tj. Na vrhu. Najnoviji elementi su na vrhu, a najstariji elementi na dnu.

Oko sebe imamo mnogo primjera hrpa poput hrpe knjiga, hrpe pladnjeva ili posuđa itd.

Stog koristi prevodioce u programskih jezika, uz računalne memorije za pohranu varijabli i funkcija poziva, a tekst editora za Poništi & Vrati poništeno operacije izvode.

Popis operacija izvedenih na Stacku

  • push () : dodaje jednu ili više stavki na vrh stoga.
  • pop () : Uklanja i vraća gornju stavku stoga.
  • peek () : Vraća gornju stavku stoga.
  • isEmpty () : Vraća Trueako je stog prazan, u Falsesuprotnom.
  • clear () : uklanja sve stavke iz stoga.
  • veličina () : Vraća duljinu stoga.

Stvaranje stoga

Klasičan pristup

Implementirat ćemo stog kao što je to na ostalim jezicima, osim JavaScript-a.

Za praćenje stavki koristit ćemo niz i dodatnu varijablu .

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

Gurnite stavku u stog

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

Otvorite stavku iz snopa

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

Zavirite u gornju stavku iz stoga

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

Provjerite je li stog prazan

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

Očistite stog

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

Veličina gomile

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

Kompletna implementacija stoga

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

Primjer

Sada ćemo stvoriti novu instancu onoga što smo implementirali i provjeriti radi li ispravno.

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

Stack implementacija s JavaScriptom

Implementirat ćemo stog s JavaScript nizom koji ima ugrađene metode poput push i pop.

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

Gurnite stavku u stog

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

Otvorite stavku iz snopa

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

Zavirite u gornju stavku iz stoga

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

Provjerite je li stog prazan

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

Očistite stog

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

Veličina gomile

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

Kompletna implementacija Stacka

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

Učini privatnost svojstava i metoda zatvaranjem i IIFE-om (odmah pozvano izražavanje funkcije).

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

Složite pomoću 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; }}

Složite pomoću 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; }}

Učini privatnost svojstava i metoda zatvaranjem i IIFE-om (odmah pozvanim izrazom funkcije) za Stack koristeći 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; } }})();

Složenost vremena

# Prosječno

Pristup: Θ (N)

Traži: Θ (N)

Umetak: Θ (1)

Izbriši: Θ (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.