Что такое стек (Stack) как структура данных?

Question

Что такое стек (Stack) как структура данных?

Тип вопроса: Алгоритмы и структуры данных Вероятность: 26% Категория: Node.js Разработчик

Ответ

Стек (Stack) — это абстрактный тип данных, работающий по принципу LIFO (Last In, First Out): последний добавленный элемент извлекается первым. Основные операции: добавление (push) и удаление (pop) с вершины.

Реализация стека в JavaScript/Node.js:

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty');
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Пример использования
const callStack = new Stack();
callStack.push('main()');
callStack.push('processOrder()');
callStack.push('validatePayment()');

console.log(callStack.peek()); // 'validatePayment()'
console.log(callStack.pop());  // 'validatePayment()' - удаляется
console.log(callStack.peek()); // 'processOrder()'

Практическое применение в разработке на Node.js:

Call Stack: Сам JavaScript использует стек вызовов для отслеживания выполнения функций.

Отмена операций (Undo):

class TextEditor {
  constructor() {
    this.content = '';
    this.history = new Stack();
  }

  type(text) {
    this.history.push(this.content); // Сохраняем состояние
    this.content += text;
  }

  undo() {
    if (!this.history.isEmpty()) {
      this.content = this.history.pop(); // Восстанавливаем предыдущее состояние
    }
  }
}

Парсинг и валидация: Проверка корректности вложенных структур (например, JSON, HTML-тегов, скобок).

function isBalancedParentheses(str) {
  const stack = new Stack();
  const pairs = { '(': ')', '[': ']', '{': '}' };

  for (let char of str) {
    if (pairs[char]) {
      stack.push(char); // Открывающая скобка -> в стек
    } else if (Object.values(pairs).includes(char)) {
      // Закрывающая скобка
      if (stack.isEmpty() || pairs[stack.pop()] !== char) {
        return false;
      }
    }
  }
  return stack.isEmpty(); // Все скобки должны быть закрыты
}
console.log(isBalancedParentheses('({[]})')); // true
console.log(isBalancedParentheses('({[})'));  // false

Маршрутизация и Middleware: Фреймворки вроде Express.js неявно используют стек для обработки цепочки middleware.

Ответ 18+ 🔞

Давай разберем эту тему про стек, но без занудства, а как есть. Представь себе стопку тарелок, ёпта. Ту, которую поставил последней, ты и снимаешь первой. Всё, принцип понятен? Это и есть LIFO (Last In, First Out). Последний зашёл — первый вышел. Как в плохой очереди в какой-нибудь конторе, где постоянно лезут без очереди.

Вот смотри, на JavaScript это выглядит проще простого. Берём массив и используем его как стопку.

class Stack {
  constructor() {
    this.items = []; // Вот наша стопка тарелок, пока пустая
  }

  push(element) {
    this.items.push(element); // Ставим тарелку сверху. Всё.
  }

  pop() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty'); // А если тарелок нет, то какой смысл снимать? Ошибка, ядрёна вошь!
    }
    return this.items.pop(); // Снимаем верхнюю тарелку и отдаём.
  }

  peek() {
    if (this.isEmpty()) {
      return null; // Подсматриваем, что наверху. Если пусто — нуль.
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0; // Проверяем, не опустела ли стопка.
  }

  size() {
    return this.items.length; // Считаем, сколько там всего навалено.
  }
}

А где это, блядь, применяется? Да везде, чувак!

Стек вызовов (Call Stack). Сам JavaScript этим и живёт. Каждую новую функцию он кладёт наверх стека, выполняет, потом снимает. Если функций овердохуища и они друг в дружке, стек переполняется — получаем знаменитый "Stack Overflow". Всё гениальное просто.

Операция "Отмена" (Undo). Классика! Каждое действие сохраняем в стек.

class TextEditor {
  constructor() {
    this.content = '';
    this.history = new Stack(); // Сюда будем складывать прошлые состояния
  }

  type(text) {
    this.history.push(this.content); // Сохраняем, что было ДО того, как напечатали
    this.content += text;
  }

  undo() {
    if (!this.history.isEmpty()) {
      this.content = this.history.pop(); // Достаём предыдущее состояние и возвращаемся к нему
    }
  }
}

Напечатал хуйню — нажал Ctrl+Z, и всё вернулось. Волшебство, ёпта!

Проверка скобок. Вот тут реально полезная штука. Чтоб не было такого: ({[}) — это же пиздец, а не код.

function isBalancedParentheses(str) {
  const stack = new Stack();
  const pairs = { '(': ')', '[': ']', '{': '}' };

  for (let char of str) {
    if (pairs[char]) {
      stack.push(char); // Видим открывающую скобку — кидаем в стек.
    } else if (Object.values(pairs).includes(char)) {
      // Видим закрывающую скобку
      if (stack.isEmpty() || pairs[stack.pop()] !== char) {
        return false; // А если стек пуст или скобка не совпала — всё, приехали, выражение ебаное невалидное.
      }
    }
  }
  return stack.isEmpty(); // В конце стек должен быть пустым. Все открытые скобки закрылись.
}
console.log(isBalancedParentheses('({[]})')); // true
console.log(isBalancedParentheses('({[})'));  // false

Маршрутизация в Express.js. Когда пишешь миддлвары, они друг за другом выполняются, а потом в обратном порядке финишируют — это и есть работа стека, просто под капотом. Доверия ебать ноль к тем, кто этого не понимает.

Короче, стек — это одна из тех базовых структур, без которой нихуя не сделаешь. Простая, как три копейки, но если её правильно применять, решает пиздопроебибну проблем. Запомни: последний зашёл — первый вышел. Всё остальное — детали.