Сложные типы данных. Стек и очередь.

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

Стек

Стек - коллекция элементов, работающая по принципу LIFO (Last-In First-Out). Самой простым примером стека, который позволит тебе понять логику его работы является... корзина для белья! Да, та самая, в которую ты каждый вечер кидаешь свою одежду.

Принцип стека достаточно прост - мы имеем прямой доступ только к последнему добавленному элементу (Майка 6). Продолжая говорить метафорами - дотянуться до самой нижней майки ты можешь только тогда, когда достанешь все остальные.
Соответственно, для реализации стека нам необходимо только два метода - push (кинуть майку наверх корзины) и pop (достать верхнюю майку). Вот пример реализации класса Stack на Typescript:

export class Stack<T> { 
  private items: Array<T>

  getCount() { 
    return this.items.length 
  }
  
  push(elem: T) { 
    this.items.push(elem) 
  }

  pop() { 
    if (this.items.length) { 
      return this.items.pop() 
    } else { 
      throw new Error('Empty stack!') 
    } 
  }

  constructor() { 
    this.items = [] 
  } 
}

Да, многие скажут, что это не стек в чистом виде. В некотором плане, мы ограничены возможностями Javascript при разработке таких структур. В других языках, в которых есть возможность работать с памятью напрямую - мы бы не использовали массивы для имитации стека. К примеру, в C++ каждый элемент представлял бы собой объект, имеющий два поля: value - непосредственно, данные, и next - ссылка на следующий в стеке элемент. Это позволяло бы классу Stack не хранить данные внутри экземпляра, достаточно было бы хранить ссылку на верхний элемент стэка. Для сильно придирчивых - в конце статьи оставлю ссылку на реализации стэка, очереди и других структур в чистом (насколько это мне позволит JS) виде.

Очередь

Теперь поговорим об очередях. Общая суть - тот же стек, только принцип FIFO (First-In First-Out). То есть, мы теперь имеем доступ не к верхнему элементу, а к нижнему. Пример - очередь в магазине. Ты подошел на кассу первый - из магазина выйдешь тоже первый. Элемент имеет такую же структуру, что и в стеке, но оглавление указывает на начало списка. Упрощенную реализацию с помощью массивов приведу здесь, для истинных программистов - ссылка будет в конце статьи.

export class Queue<T> { 
  private items: Array<T>

  getCount() { 
    return this.items.length 
  }
  
  push(elem: T) { 
    this.items.push(elem) 
  }

  pop() { 
    if (this.items.length) { 
      this.items.reverse()
      const popElem = this.items.pop() 
      this.items.reverse()
      
      return popElem
    } else { 
      throw new Error('Empty queue!') 
    } 
  }

  constructor() { 
    this.items = [] 
  } 
}

В упрощенной реализации единственная разница со стеком будет в строчках с reverse(). Она обусловленна тем, что доставать элемент нам нужно с низа, а не с верха, как в стеке. Реализация для гуру будет отличаться более существенно и есть поле для дебатов.
Подходов к реализации достаточно много. Самым простым путём является хранение двух указтелей - на начало и конец очереди. Это облегчит реализации push и pop методов. Однако, она идёт в разрез с определением очереди - доступ должен быть только к первому элементу.

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

На практике

Теперь поговорим немного о практическом применении во Frontend.

Возможно, писать руками тебе эти структуры и не придется, однако, знать о них очень и очень важно, поскольку, весь JS работает на стеках и очередях (вспомни Event Loop). Очередь микрозадач, стек вызовов - реально представляют из себя ОЧЕРЕДЬ и СТЕК соответственно, а не просто названы так для красоты. В реальных же кейсах, это может пригодиться, если ты будешь писать собственный wrapper для API вызовов, и тебе придется самостоятельно организовывать кастомную асинхронную структуру вызовов методов API. Случай достаточно нетривиальный, однако, имеет место быть. В рядовых задачах, связанных с интерфейсами и шаблонной логикой работы с API ты, скорее всего, не столкнёшься с такими кейсами.

Заключение

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

Для трушных кодеров - ссылка на песочницу с примерами реализации.

Ставь реакцию, подписывайся на канал, зови друзей - дальше будет еще интереснее!