Оволодіння стеками в JavaScript

Стек — це одна з основних структур даних, що широко використовується в програмуванні. Вона працює за принципом LIFO (Last In, First Out), що означає «останній доданий — перший вийнятий». Уявіть собі стопку тарілок, де ви додаєте нові тарілки зверху, а також забираєте їх зверху. Таким чином, ви не можете забрати тарілку з середини, не прибравши спочатку ті, що зверху.

Основними операціями стека є Push (додавання елемента на верх) і Pop (видалення верхнього елемента). Інші корисні операції включають Peek (перегляд верхнього елемента без його видалення), isEmpty (перевірка, чи порожній стек) і Size (отримання кількості елементів у стеці).

Розглянемо реалізацію стека в JavaScript за допомогою масиву:

class Stack {  
 constructor() {  
 this.items = [];  
 }  

 // Додаємо елемент до стеку  
 push(element) {  
 this.items.push(element);  
 }  

 // Видаляємо та повертаємо верхній елемент  
 pop() {  
 if (this.isEmpty()) return null;  
 return this.items.pop();  
 }  

 // Переглядаємо верхній елемент  
 peek() {  
 return this.isEmpty() ? null : this.items[this.items.length - 1];  
 }  

 // Перевіряємо, чи порожній стек  
 isEmpty() {  
 return this.items.length === 0;  
 }  

 // Повертаємо кількість елементів у стеці  
 size() {  
 return this.items.length;  
 }  

 // Вивести вміст стеку  
 print() {  
 console.log(this.items.join(' '));  
 }  
}

Приклад використання стека:

const stack = new Stack();  

stack.push(10);  
stack.push(20);  
stack.push(30);  

stack.print(); // 10 20 30  

console.log(stack.pop()); // 30  
console.log(stack.peek()); // 20  
console.log(stack.size()); // 2

Однак для більшого контролю (наприклад, для оптимізації пам'яті) можна реалізувати стек за допомогою об'єкта:

class CustomStack {  
 constructor() {  
 this.count = 0;  
 this.storage = {};  
 }  

 push(value) {  
 this.storage[this.count] = value;  
 this.count++;  
 }  

 pop() {  
 if (this.count === 0) return undefined;  
 this.count--;  
 const result = this.storage[this.count];  
 delete this.storage[this.count];  
 return result;  
 }  

 peek() {  
 return this.storage[this.count - 1];  
 }  

 size() {  
 return this.count;  
 }  

 isEmpty() {  
 return this.count === 0;  
 }  
}

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

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

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

Продовжуйте вдосконалювати свої знання — і виправляйте ці баги! 😉

Перекладено з: Mastering Stacks in JavaScript