Как да внедрите стек във ванилов JavaScript и ES6

А стека е подредена съвкупност от елементи, които следват Последно първа изходяща принципа (LIFO). Добавянето и премахването на предмети се извършва в същия край, т.е. в горната част. Най-новите елементи са отгоре, а най-старите елементи са отдолу.

Имаме много примери за стекове около нас като купчина книги, купчина подноси или съдове и т.н.

А Stack се използва от компилатори в езиците за програмиране, чрез компютърна памет за съхранение на променливите и извиквания на функции, както и в текстови редактори за извършване на връщане и операции ремонтирам.

Списък на операциите, извършени в стека

  • push () : Добавя един или няколко елемента в горната част на стека.
  • pop () : Премахва и връща горния елемент от стека.
  • peek () : Връща най-горния елемент от стека.
  • isEmpty () : Връща, Trueако стекът е празен, в Falseпротивен случай.
  • clear () : Премахва всички елементи от стека.
  • size () : Връща дължината на стека.

Създаване на стек

Класически подход

Ще приложим стек като начина, по който се прилага на други езици, освен JavaScript.

Ще използваме масив и допълнителна променлива, за да следим елементите.

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

Натиснете елемент в стека

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

Изпратете елемент от стека

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

Погледнете най-горния елемент от стека

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

Проверете дали стекът е празен

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

Изчистете стека

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

Размер на стека

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

Пълно изпълнение на стека

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

Пример

Сега ще създадем нов екземпляр на това, което сме внедрили и ще проверим дали работи правилно.

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

Внедряване на стека с JavaScript

Ще приложим стек с JavaScript масив, който има вградени методи като push и pop.

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

Натиснете елемент в стека

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

Изпратете елемент от стека

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

Погледнете най-горния елемент от стека

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

Проверете дали стекът е празен

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

Изчистете стека

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

Размер на стека

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

Пълно изпълнение на стека

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

Предоставяне на свойствата и методите частни със затваряне и IIFE (незабавно извикан израз на функция)

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

Стек с 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; }}

Стек с помощта на 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; }}

Предоставяне на свойствата и методите частни със затваряне и IIFE (незабавно извикано изразяване на функция) за стека с помощта на 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; } }})();

Сложност във времето

# Средно аритметично

Достъп: Θ (N)

Търсене: Θ (N)

Вмъкване: Θ (1)

Изтриване: Θ (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.