Стек — В TypeScript и C#

Это означает, что последний или недавний элемент, который мы добавляем в стек, является первым элементом, который мы сможем извлечь. Представьте, что вы складываете 10 книг друг на друга. Вы можете взять только верхнюю книгу из стопки, которая была добавлена ​​недавно.

Ниже приведены основные функции, поддерживаемые любой реализацией стека:

• push:метод, позволяющий добавлять элементы данных в стек.
• pop: метод, позволяющий удалить элемент из стека. Это будет верхний элемент в стеке.
• Peek: метод, который позволит нам просмотреть верхний элемент стека, не удаляя его из стека. В некоторых реализациях для этого используется свойство top или first.
• size: свойство для хранения количества элементов в стеке. В некоторых реализациях это также называется Count или Length.

Теперь перейдем к деталям реализации. Стек может быть реализован многими способами. Один из способов — реализовать структуру данных Array. Мы можем добавлять элементы в конец массива и удалять их из конца массива. Но когда дело доходит до динамического изменения размера, массив менее эффективен. Итак, мы реализуем Stack, используя концепции связанных списков.

Определение класса элемента стека

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

Определение класса стека

Класс стека будет иметь несколько свойств.

• first: свойство для хранения ссылки на первый/верхний/головной элемент в стеке.
• last: свойство для хранения ссылки на последний/хвостовой элемент в стеке.
• size: свойство для хранения подсчета общего количества элементов в стеке.

Все, что нам нужно сделать сейчас, это реализовать необходимые методы.

Толкать()

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

Step 1: Add a new node to the list with value 1
         1
Step 2: Add another node to the list with value 2
         2 → 1
Step 3: Add another node to the list with value 3
         3 → 2 → 1

Обратите внимание, что все новые элементы, которые мы добавляем на каждом этапе, находятся в начале списка. Давайте напишем псевдокод для того же самого:

• Создайте метод push, который принимает число в качестве параметра.
• Создайте новый Element для переданного значения.
• Убедитесь, что размер стека равен нулю. Если это так, установите свойства first, last в стеке для нового элемента.
• Если нет, установите наш новый Element.next так, чтобы он указывал на первый элемент. Затем установите first для нового элемента.
• Увеличьте size на 1.

Теперь попробуйте написать код для метода push, прежде чем прокрутить вниз, чтобы увидеть мой.

Поп()

В этом методе мы удалим первый/верхний элемент из стека. Это означает, что мы должны удалить заголовок нашего связанного списка. Давайте посмотрим на пример здесь для лучшего понимания.

Step 1: Let's start with this stack
         3 → 2 → 1
Step 2: Pop an element from the stack. We will return 3 and set 2 as           the first element.
         2 → 1
Step 3: Pop an element form the stack. We will return 2 and set 1 as the first element.
         1

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

• Создайте новый метод с именем pop(), который будет возвращать число.
• Убедитесь, что размер стека size равен нулю. Если это так, верните ноль.
• Если в нашем стеке есть элементы, сохраните значение первого элемента во временной переменной с именем prevFirst.
• Установите элемент first как prevFirst.next.
• Удалите prevFirst из стека, установив для prevFirst.next значение null
• Верните элемент prevFirst.

Вот и все. Мы сделали. Посмотрим, сможешь ли ты это закодировать. Ниже приведен код:

заглянуть()

Это проще всего. Все, что нам нужно сделать, это вернуть значение нашего свойства first, которое мы постоянно обновляли при выполнении операций push и pop. Итак, давайте перейдем непосредственно к коду.

peek() : number {
  if(this._size === 0)
    return null;
   
   return this._first;
}

Большой O из стека

Стек — одна из самых эффективных структур данных, которую вы можете найти, если все, что вам нужно делать, это добавлять элементы и удалять элементы сверху.

Вставка/удаление:по свойствам стека, LIFO; и мы реализуем стек, используя связанный список, большой O для этих операций всегда O(1). Это связано с тем, что добавление/удаление элемента из головы связанного списка всегда занимает всего 1 операцию.

Доступ/Поиск. Чтобы найти элемент по определенному индексу или проверить, существует ли элемент в стеке, мы должны линейно просмотреть все элементы. Из-за этого эти операции имеют большой O из O(n).

Я надеюсь, что это дало вам понимание концепций стека и его временной сложности. Вы можете найти весь код здесь, на GitHub, где есть код на машинописном языке и C#. Хлопайте и делитесь, если вам это нравится.

Далее: Реализация очереди