Стек — это простая структура данных, которая следует определенному порядку выполнения операций. Представьте себе стопку книг или тарелок, куда вы можете добавлять или удалять предметы только сверху. Это похоже на то, как структура данных стека работает в программировании.

В компьютерных науках стеки имеют фундаментальное значение, поскольку они формируют основу для более сложных структур данных. У них есть две основные операции: «Push» и «Pop». Push добавляет элемент на вершину стека, делая его новым верхним элементом. Pop удаляет верхний элемент из стека, открывая нижний элемент как новую вершину.

Как упоминалось ранее в аналогии с тарелками, стопка похожа на стопку тарелок, где вы можете только добавлять новые тарелки сверху или удалять тарелки сверху. Диаграмма подтверждает эту идею, показывая, что вы можете добавлять или удалять элементы только с вершины стека. Преимущество такого расположения заключается в том, что задействованные операции, такие как «push» и «pop», имеют описательные имена, которые позволяют легко понять их назначение и запомнить, как их использовать в стеке.

Есть еще две общие операции, связанные со стеками: «Peek» и «IsEmpty». Peek позволяет взглянуть на верхний элемент, не удаляя его. Это как заглянуть в верхнюю часть стопки книг. IsEmpty просто проверяет, пуст стек или нет.

Теперь давайте посмотрим, как стеки используются на практике. Одним из важных приложений является вычисление арифметических выражений. Например, когда мы оцениваем выражение «3 + 4 * 2», мы используем стек, чтобы отслеживать операторы в правильном порядке. Стек гарантирует, что умножение выполняется до сложения, точно так же, как решение математических задач в соответствии с порядком операций.

Стеки также необходимы для разбора синтаксиса в языках программирования. Они помогают нам убедиться, что открывающие и закрывающие скобки, такие как круглые или фигурные скобки, правильно сопоставлены и вложены друг в друга. Мы используем стек для отслеживания скобок, помещая открывающую скобку в стек и проверяя, соответствует ли она соответствующей закрывающей скобке. Это гарантирует правильность синтаксиса нашего кода.

Помимо этих применений, стеки используются в различных других сценариях. Например, управление вызовами функций похоже на отслеживание различных задач, которые вам необходимо выполнить. Когда функция вызывается, она добавляется в стек, а когда завершается, удаляется. Таким образом, функции выполняются в правильном порядке. Стеки также включают функцию отмены/возврата, позволяя вам отменить или повторить действия. Они полезны в алгоритмах, которые включают поиск или исследование различных путей, поскольку стек отслеживает предпринятые шаги. Наконец, стеки полезны в управлении памятью, помогая выделять и освобождать блоки памяти.

Вот пример того, как использовать стековые структуры данных в JavaScript.

class Stack {
  constructor() {
    this.items = [];
  }
  // Methods go here
}

Мы определяем класс Stack, используя синтаксис класса ES6 в этом сегменте. Функция-конструктор инициализирует массив элементов как пустой массив. Этот массив будет использоваться для хранения элементов стека.

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

Метод push используется для добавления элементов в стек. Он принимает параметр элемента и просто помещает элемент в массив элементов, используя метод push для массивов в JavaScript.

pop() {
  if (this.isEmpty()) {
    return "Underflow";
  }
  return this.items.pop();
}

Метод pop удаляет и возвращает верхний элемент из стека. Сначала он проверяет, пуст ли стек, используя метод isEmpty. Если стек пуст, он возвращает строку «Underflow», чтобы указать, что нет элементов для извлечения. В противном случае он использует метод pop для массивов, чтобы удалить и вернуть последний элемент из массива элементов.

peek() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
}

Метод peek возвращает верхний элемент стека, не удаляя его. Подобно методу pop, он сначала проверяет, пуст ли стек, используя метод isEmpty. Если стек пуст, возвращает строку «Стек пуст». В противном случае он извлекает последний элемент массива элементов, используя индекс this. items.length — 1 и возвращает его.

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

Метод isEmpty проверяет, пуст ли стек. Он просто сравнивает длину массива элементов с 0 и возвращает true, если он пуст, и false в противном случае.

printStack() {
  let str = "";
  for (let i = 0; i < this.items.length; i++) {
    str += this.items[i] + " ";
  }
  return str.trim();
}

Метод printStack возвращает строковое представление стека. Он инициализирует пустую строку str и выполняет итерацию по массиву элементов, используя цикл for. На каждой итерации он объединяет текущий элемент с пробелом в str. Наконец, он обрезает все пробелы в конце строки и возвращает их.

let stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.printStack()); // Output: 10 20 30
console.log(stack.peek()); // Output: 30
console.log(stack.pop()); // Output: 30
console.log(stack.printStack()); // Output: 10 20

В этом сегменте мы создаем новый экземпляр класса Stack, используя ключевое слово new, и присваиваем его переменной stack. Затем мы используем метод push, чтобы добавить в стек три элемента (10, 20 и 30). Наконец, мы демонстрируем некоторые операции, распечатывая стек, просматривая верхний элемент, извлекая элемент и снова печатая стек, чтобы наблюдать за изменениями.

Короче говоря, стеки универсальны и имеют множество применений в различных областях программирования. Они используются для оценки арифметических выражений, обеспечения правильного синтаксиса, управления вызовами функций, реализации действий отмены/возврата, помощи в алгоритмах поиска и помощи в управлении памятью. Понимание стеков позволяет разработчикам создавать эффективные алгоритмы, писать безошибочный код и легко решать сложные задачи.

Рекомендации

https://www.geeksforgeeks.org/stack-data-structure/

https://medium.com/javarevisited/when-to-use-stack-data-structure-9ac3dfa4d10