Як реалізувати стек у ванільних JavaScript та ES6

Стек являє собою упорядковану сукупність елементів , які слідують за Last In First Out принципу (ЛІФО). Додавання та вилучення предметів відбувається в тому ж кінці, тобто вгорі. Найновіші елементи знаходяться вгорі, а найстаріші елементи - внизу.

У нас є багато прикладів стеки навколо нас , як стопка книг, стопки тарілок або тарілок і т.д.

Стек використовується укладачами в мовах програмування, з допомогою комп'ютерної пам'яті для зберігання змінних і викликів функцій, а також в текстових редакторах для виконання відмін & операції повторного виконання .

Список операцій, що виконуються в 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.