Стек — это простая линейная структура данных, которая работает как стопка тарелок ?️. Он следует принципу «Последним пришел — первым ушел» (LIFO). Думайте об этом как о стопке тарелок: вы можете добавлять или удалять тарелки только с вершины стопки.

Для лучшего понимания стека давайте отправимся в небольшое путешествие воображения?.
Представьте, что вы находитесь в модном ресторане ?️, а кухонный персонал готовится к насыщенному вечеру ?‍?. В зоне для посуды стоит высокая стопка тарелок, ожидающих использования. Когда приходят посетители и поступают заказы, персонал берет тарелки с верха стопки. Когда добавляются чистые тарелки, они оказываются прямо сверху. Эта простая система гарантирует, что тарелки внизу стопки, которые находились там дольше всего, используются последними, а только что очищенные тарелки сверху используются первыми ✨.

По сути, именно так работает структура данных Stack. Стек — это линейная структура данных, которая соответствует принципу «Последним поступил — первым обслужен» (LIFO). Как и в случае со стопкой тарелок, последний элемент, добавленный в стопку, удаляется первым.

Оглавление

В этом подробном руководстве по структуре данных стека мы рассмотрим следующие темы с помощью простого и удобного для новичков подхода:

1. Что такое стек?
2. Плюсы и минусы использования стека
3. Реальное применение стеков
4. Ключевые операции со стеком
5. Реализация стека в JavaScript
6. Заключение

Вы готовы? Давайте углубимся

Что такое стек?

Стек — это линейная структура данных, основанная на принципе «Последним поступил — первым отправлен» (LIFO). Это означает, что последний элемент, добавленный в стек, будет удален первым. Думайте об этом как о стопке книг: добавлять или удалять книги можно только с вершины стопки.

Плюсы и минусы использования стека

Прежде чем мы продолжим работу и напишем несколько кодов, полезно понять, где и где не следует использовать стек. В таблице ниже подробно описаны плюсы и минусы стека.

Ключевые операции со стеком

Основные операции, которые можно выполнять со стеком:

1. push(): добавляет элемент на вершину стека.
2. pop(): удаляет самый верхний элемент из стека.
3. peek(): возвращает верхний элемент стека, не удаляя его.
4. isEmpty(): проверяет, пуст ли стек.
5. size(): возвращает количество элементов в стеке.

Реальные применения стеков

Стеки используются повсюду в информатике и разработке программного обеспечения. Вот некоторые распространенные приложения:

1. Отменить функциональность: в текстовых редакторах или программах графического дизайна каждое действие помещается в стек. Когда вы нажимаете «Отменить», самое последнее действие извлекается из стека и отменяется.

2. История браузера: когда вы посещаете новую страницу, она помещается в стек. Кнопка «Назад» извлекает текущую страницу из стопки, открывая предыдущую.

3. Стек вызовов функций: в языках программирования вызовы функций управляются с помощью стека. Когда вызывается функция, она помещается в стек вызовов. Когда он возвращается, он оторвется.

4. Оценка выражений: стеки используются для оценки арифметических выражений, особенно в постфиксной записи.

5. Алгоритмы обратного отслеживания: в таких задачах, как решение лабиринтов или головоломок, стеки могут отслеживать пройденный путь, позволяя при необходимости легко вернуться назад.

Реализация стека в JavaScript

Теперь давайте реализуем стек на JavaScript. Важно знать, что существуют разные способы реализации стека в JavaScript. Один из распространенных способов реализации стека — использование массива, другой способ — использование связанного списка. В этой статье мы реализуем стек с использованием связанного списка (односвязного списка).

Реализация стека с использованием связанного списка

Надеюсь, вы еще помните, как работает связанный список? Возможно, вам придется ознакомиться с реализацией связанного списка в одной из наших предыдущих статей этой же серии.

Как реализовать односвязный список в JavaScript

Отличное решение? ・ 4 октября

#javascript #новички #программирование #дса

Теперь давайте начнем реализацию нашего стека с использованием односвязного списка. А не ___ ли нам?

Сначала мы создадим класс Node, который будет представлять отдельный элемент нашего стека.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Затем мы создадим класс Stack, который будет представлять наш стек.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here ?
}

Нажмите операцию

Операция push добавляет новый элемент на вершину стека. Он создает новый StackNode, устанавливает его следующий указатель на текущую вершину, а затем обновляет вершину, чтобы она указывала на этот новый узел. Наконец, он увеличивает размер.

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size  ;
  }

Поп-операция

Операция pop удаляет самый верхний элемент из стека. Сначала он проверяет, пуст ли стек. Если это так, он возвращает сообщение об ошибке. В противном случае он удаляет верхний элемент, обновляет верхний указатель на следующий узел и уменьшает размер. Наконец, он возвращает удаленный элемент.

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

Операция «Пик»

Операция просмотра возвращает верхний элемент, не удаляя его. Сначала он проверяет, пуст ли стек. Если это так, он возвращает сообщение об ошибке. В противном случае он возвращает данные верхнего элемента.

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

isEmpty Операция

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

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

Операция getSize

Операция getSize возвращает размер стека. Возвращает количество элементов в стеке.

  // Return the size of the stack
  getSize() {
    return this.size;
  }

Операция печати

Операция печати печатает стек. Он возвращает данные верхнего элемента.

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result  = current.data   " ";
      current = current.next;
    }
    console.log(result.trim());
  }

Пример использования

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

В этой реализации мы использовали структуру связанного списка (односвязный список) для представления нашего стека. Каждый элемент представляет собой узел со значением данных и ссылкой на следующий узел. На вершине стека всегда находится последний добавленный узел.

Заключение

Стеки — это фундаментальная структура данных в информатике, основанная на принципе «Последний пришел — первый вышел» (LIFO). Они используются в различных приложениях, включая управление вызовами функций, реализацию функций отмены и оценку арифметических выражений.

В этом уроке мы рассмотрели основы стеков, плюсы и минусы их использования, а также их реализацию в JavaScript (с использованием связанного списка). Понимание стеков — это не только знание того, как их реализовать, но и понимание того, когда они являются подходящим инструментом для решения проблемы.

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

Оставайтесь в курсе и на связи

Чтобы вы не пропустили ни одной части этой серии, а также связаться со мной для более углубленного обсуждения разработки программного обеспечения (веб-сайтов, серверов, мобильных устройств или парсинга/автоматизации), структур данных и алгоритмов, а также других интересных технологий. темы, подписывайтесь на меня:

• GitHub
• LinkedIn
• X (Твиттер)

Следите за обновлениями и удачи в программировании ?‍??