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

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

Массив: структура данных с произвольным доступом, к элементам которой можно получить доступ за постоянное время.

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

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

Стеки

Простым определением стека будет то, что это структура данных, которая следует принципу LIFO (последним пришел — первым обслужен). Однако трудно представить, что, представьте себе кучу тарелок, сложенных друг на друга, последняя тарелка, которая находится на вершине кучи, будет первой, если ее кто-то использует. В визуальном плане это стек. Набор данных, основанный на принципе ЛИФО. Основной задачей стеков является вставка и удаление элементов.

Временная сложность в соответствии с нотацией Big O

Двумя основными методами, составляющими стек, являются методы push() и pop(). Поскольку они оба отдают приоритет вставке и удалению элементов. Из-за этого они оба имеют порядок O (1) в соответствии с нотацией Big O, что означает, что они происходят в постоянное время. Поскольку стек увеличивается до размера n, каждому методу требуется одинаковое количество времени для выполнения операций.

Другие методы включают

  • просмотр: константа — O(1) — возвращает элемент на вершине стека
  • empty: константа — O(1) — возвращает логическое значение, если стек пуст или нет
  • size: Constant — O(1) — возвращает количество элементов в стеке

Есть много применений для стеков, вы даже не осознаете этого. Один из наиболее распространенных в JavaScript называется стеком вызовов/стеком выполнения. Подробнее об этой теме можно прочитать здесь.

Очереди

Очереди следуют принципу, отличному от стеков, они следуют принципу FIFO (First In, First Out). Представьте себе очередь покупателей у кассы, человек в самом начале будет первым из очереди, как только он / она завершит транзакцию. Именно так очередь ведет себя в мире структур данных.

Временная сложность в соответствии с нотацией Big O

Два основных метода, составляющих очередь, — это методы enqueue() и dequeue(). Подобно стекам, Queue отдает приоритет вставке и удалению элементов, поэтому методы enqueue() и dequeue() имеют порядок O(1) в соответствии с нотацией Big O.

Другие методы включают

  • peek: константа — O(1) — возвращает первый элемент очереди
  • size: Constant — O(1) — возвращает общее количество элементов в очереди