Hogyan rakjunk be verem vanília JavaScript-be és ES6-ba

A verem a Last In First Out (LIFO) elvét követő elemek rendezett gyűjteménye . Az elemek hozzáadása és eltávolítása ugyanabban a végén, azaz a tetején történik. A legfrissebb elemek felül, a legrégebbi elemek pedig alul vannak.

Számos példa van arra, hogy verem van körülöttünk, például egy halom könyv, egy halom tálca vagy edény stb.

A verem a fordítók által használt programozási nyelvekben, a számítógép memóriájában a változók és a függvényhívások tárolására, a szövegszerkesztõkben pedig a visszavonási és újragyártási mûveletek végrehajtására.

A Stacken végrehajtott műveletek listája

  • push () : Egy vagy több elemet ad a verem tetejére.
  • pop () : Eltávolítja és visszaküldi a verem legfelső elemét.
  • peek () : Visszaadja a Verem legfelső elemét.
  • isEmpty () : Akkor tér vissza, Trueha a verem üres, Falsekülönben.
  • clear () : Az összes elem eltávolításra kerül a veremből.
  • size () : A verem hosszát adja vissza.

Verem létrehozása

Klasszikus megközelítés

Olyan halmot fogunk bevezetni, mint ahogyan a JavaScript-en kívül más nyelveken is megvalósítják.

Egy tömböt és egy extra változót fogunk használni az elemek nyomon követésére.

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

Tegyen egy elemet a verembe

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

Tegyen fel egy elemet a Veremből

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

Kukucskáljon a legfelső elemre a veremből

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

Ellenőrizze, hogy a Verem üres-e

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

Törölje a veremet

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

A verem mérete

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

A Verem teljes megvalósítása

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

Példa

Most létrehozunk egy új példányt arról, amit megvalósítottunk, és ellenőrizzük, hogy megfelelően működik-e.

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

Verem megvalósítása JavaScript-sel

Verem fogunk bevezetni egy JavaScript tömbben, amely beépített módszerekkel rendelkezik, például push és pop.

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

Tegyen egy elemet a verembe

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

Tegyen fel egy elemet a Veremből

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

Kukucskáljon a legfelső elemre a veremből

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

Ellenőrizze, hogy a Verem üres-e

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

Törölje a veremet

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

A verem mérete

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

A Stack teljes megvalósítása

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

A tulajdonságok és módszerek priváttá tétele bezárással és IIFE (azonnali hívott funkciókifejezéssel).

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

Verem az ES6 segítségével.

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

Verem az ES6 WeakMap segítségével.

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

A tulajdonságok és módszerek priváttá tétele bezárással és IIFE (azonnali hívott funkciókifejezés) a veremhez az ES6 WeakMap segítségével.

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

Idő komplexitás

# Átlagos

Hozzáférés: Θ (N)

Keresés: Θ (N)

Beszúrás: Θ (1)

Törlés: Θ (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.