Как и было обещано в моей предыдущей статье, в этой статье я буду говорить о двух структурах данных, согласно названию, речь пойдет о стеках и очередях.
Прежде чем я углублюсь в это, давайте на самом деле определим некоторые важные слова в мире структур данных.
Массив: структура данных с произвольным доступом, к элементам которой можно получить доступ за постоянное время.
Связанный список: структура данных с последовательным доступом, где каждый элемент может быть доступен в определенном порядке.
Однако стеки и очереди полностью отличаются от массивов и связанных списков в том смысле, что они известны как структуры данных с ограниченным доступом. Мы можем создавать и то, и другое, стеки и очереди можно создавать с использованием как массива, так и реализации связанного списка, однако я лично буду использовать реализацию связанного списка на протяжении всей этой статьи.
Стеки
Простым определением стека будет то, что это структура данных, которая следует принципу 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) — возвращает общее количество элементов в очереди