7 days of WordPress plugins, themes & templates - for free!* Unlimited asset downloads! Start 7-Day Free Trial
Advertisement
  1. Code
  2. JavaScript

Структуры данных в JavaScript: стек и очередь

Scroll to top
Read Time: 11 mins
This post is part of a series called Data Structures in JavaScript.
Data Structures With JavaScript: What's a Data Structure?
Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List

Russian (Pусский) translation by Masha Kolesnikova (you can also view the original English article)

Две из наиболее часто используемых структур данных в веб-разработке - это стеки и очереди. Многие пользователи Интернета, в том числе веб-разработчики, не знают об этом удивительном факте. Если вы один из этих разработчиков, тогда подготовьтесь к двум просветительским примерам: операция «отменить» текстового редактора использует стек для организации данных; Цикл событий веб-браузера, который обрабатывает события (клики и т.д.), использует очередь для обработки данных.

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

Стек

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

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

Этот процесс добавления тарелок сохранит последовательный порядок, когда каждая тарелка была добавлена в стек. Удаление тарелок из стека также сохранит последовательный порядок всех тарелок. Если тарелка удаляется из верхней части стека, каждая другая тарелка в стеке по-прежнему сохраняет правильный порядок в стеке. То, что я описываю, возможно, слишком выглядит чересчур подробно, но смысл заключается в том, как тарелки добавляются и удаляются в большинстве кафетерий!

Чтобы предоставить более технический пример стека, вспомним операцию «отменить» текстового редактора. Каждый раз, когда текст добавляется в текстовый редактор, этот текст помещается в стек. Первое дополнение к текстовому редактору представляет собой нижнюю часть стека; Последнее изменение представляет собой верхнюю часть стека. Если пользователь хочет отменить последнее изменение, верхняя часть стека будет удалена. Этот процесс можно повторить до тех пор, пока в стек не будет добавлено больше дополнений, это пустой файл!

Операции стека

Поскольку теперь у нас есть концептуальная модель стека, определим две операции стека:

  • push(data) добавляет данные.
  • pop() удаляет последние добавленные данные.

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

Теперь давайте напишем код для стека!

Свойства стека

Для нашей реализации мы создадим конструктор Stack. Каждый экземпляр Stack будет иметь два свойства: _size и _storage.

this._storage позволяет каждому экземпляру Stack иметь собственный контейнер для хранения данных; this._size отражает количество попыток передачи данных в текущую версию Stack. Если создается новый экземпляр Stack и данные помещаются в его хранилище, то this._size будет увеличиваться на 1. Если данные снова вставляются в стек, this._size будет увеличиваться до 2. Если данные удаляются из стека, то this._size будет уменьшаться до 1.

Методы стека

Нам нужно определить методы, которые могут добавлять (push) и удалять (pop) данные из стека. Начнем с добавления данных.

Метод 1 из 2: push(data)

(Этот метод можно использовать для всех экземпляров Stack, поэтому мы добавим его в прототип Stack.)

У нас есть два требования к этому методу:

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

Наше реализация push(data) включает в себя следующую логику. Объявите переменную с именем size и присвойте ей значение this._size ++. Определите size в качестве ключа this._storage. И определите data как значение соответствующего ключа.

Если бы наш стек вызывал push(data) пять раз, тогда размер нашего стека был бы 5. Первое добавление данных в стек присвоит этим данным ключ из 1 в этом ._storage. Пятый вызов push(data) присваивает этим данным ключ из 5 в this._storage. Мы только что присвоили порядок нашим данным!

Метод 2 из 2: pop()

Теперь мы можем передавать данные в стек; Следующий логический шаг - выталкивание (удаление) данных из стека. Забор данных из стека - это не просто удаление данных; Он удаляет только самые последние добавленные данные.

Вот наши цели для этого метода:

  1. Используйте текущий размер стека, чтобы получить самые последние добавленные данные.
  2. Удалите последние добавленные данные.
  3. Уменьшение _this._size на единицу.
  4. Верните последние удаленные данные.

pop() соответствует каждой из наших четырех целей. Сначала мы объявляем две переменные: size инициализируется размером стека, а deletedData присваивается последним данным, добавленным в стек. Во-вторых, мы удаляем пару ключ-значение наших последних добавленных данных. В-третьих, мы уменьшаем размер стека на 1. В-четвертых, мы возвращаем данные, которые были удалены из стека.

Если мы протестируем нашу текущую реализацию pop(), мы обнаружим, что она работает для следующего прецедента. Если мы вставляем данные push(data) в стек, размер стека увеличивается на единицу. Если мы достаем pop() данные из нашего стека, размер нашего стека уменьшается на единицу.

Однако возникает проблема, когда мы меняем порядок вызова. Рассмотрим следующий сценарий: мы вызываем pop(), а затем делаем push(data). Размер нашего стека меняется на -1, а затем на 0. Но правильный размер нашего стека равен 1!

Чтобы обработать этот вариант использования, мы добавим оператор if в pop().

С добавлением нашего оператора if тело нашего кода выполняется только при наличии данных в нашем хранилище.

Полная реализация стека

Наша реализация Stack завершена. Независимо от порядка, в котором мы ссылаемся на любой из наших методов, наш код работает! Вот окончательная версия нашего кода:

От стека к очереди

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

Очередь

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

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

Давайте далее предположим, что этот билет имеет номер «один», отображаемый на нем. Следующий билет имеет номер «два», отображаемый на нем. Клиент, который берет второй билет, будет обслуживаться вторым. (Если бы наша система билетов работала как стек, то клиент, который первым вступил в стек, был бы последним, который будет обслуживаться!)

Более практичным примером очереди является цикл событий веб-браузера. По мере запуска различных событий, таких как щелчок кнопки, они добавляются в очередь цикла событий и обрабатываются в том порядке, в котором они попали в очередь.

Операции очереди

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

  • enqueue(data) добавляет данные в очередь.
  • dequeue удаляет самые старые добавленные данные в очередь.

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

Теперь давайте напишем код для очереди!

Свойства очереди

Для нашей реализации мы создадим конструктор с именем Queue. Затем мы добавим три свойства: _oldestIndex, _newestIndex и _storage. Потребность в _oldestIndex и _newestIndex станет более понятной в следующем разделе.

Методы очереди

Теперь мы создадим три метода, разделяемых между всеми экземплярами очереди: size(), enqueue(data) и dequeue(data). Я опишу цели для каждого метода, покажу код для каждого метода, а затем объясню код для каждого метода.

Метод 1 из 3: size()

У нас есть две цели для этого метода:

  1. Вернуть правильный размер для очереди.
  2. Сохранить правильный диапазон ключей для очереди.

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

Используя нашу концептуальную модель стека, давайте представим, что мы добавляем пять тарелок в стек. Размер нашего стека равен пяти, и каждая тарелка имеет число от одного (первая добавленная тарелка) до пяти (последняя добавленная тарелка). Если мы удалим три тарелки, то у нас будет две тарелки. Мы можем просто вычесть три из пяти, чтобы получить правильный размер, который равен двум. Вот наиболее важный вопрос о размере стека: Текущий размер представляет собой правильный ключ, связанный с тарелкой наверху стека (2), а другой - в стеке (1). Другими словами, диапазон ключей всегда от текущего размера до 1.

Теперь давайте применим эту реализацию size стека к нашей очереди. Представьте, что пять клиентов берут билет из нашей системы билетов. У первого клиента есть билет, показывающий номер 1, а пятый клиент имеет билет с номером 5. С очередью сначала обслуживается клиент с первым билетом.

Давайте теперь представим, что первый клиент обслуживается и этот билет удаляется из очереди. Подобно стеку, мы можем получить правильный размер нашей очереди, вычитая 1 из 5. В нашей очереди в настоящее время есть четыре небронированных билета. Теперь возникает проблема: размер больше не соответствует правильным номерам билетов. Если мы просто вычтем один из пяти, мы будем иметь размер 4. Мы не можем использовать 4 для определения текущего диапазона оставшихся билетов в очереди. Есть ли у нас билеты в очереди с номерами от 1 до 4 или от 2 до 5? Ответ непонятен.

Это преимущество наличия следующих двух свойств в очереди: _oldestIndex и _newestIndex. Все это может показаться запутанным - меня все еще иногда они путают. Что помогает мне рационализировать все, это следующий пример, который я разработал.

Представьте, что в нашем гастрономе есть две системы продажи билетов:

  1. _newestIndex представляет собой билет из системы билетов клиентов.
  2. _oldestIndex представляет собой билет из системы билетов для сотрудников.

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

  1. Клиент берет билет. Номер билета клиента, который извлекается из _newestIndex, равен 1. Следующий билет, доступный в системе билета клиента, - 2.
  2. Сотрудник не берет билет, а текущий билет в системе билета сотрудника равен 1.
  3. Мы берем текущий номер билета в системе клиента (2) и вычитаем номер в системе сотрудников (1), чтобы получить номер 1. Число 1 представляет количество билетов, все еще находящихся в очереди, которые не были удалены.
  4. Сотрудник берет билет из своей системы продажи билетов. Этот билет представляет собой билет клиента, который обслуживается. Билет, который был получен, извлекается из _oldestIndex, который отображает номер 1.
  5. Мы повторяем шаг 4, и теперь разница равна нулю - в очереди больше нет билетов!

Теперь у нас есть свойство (_newestIndex), которое может указать нам наибольшее число (ключ), назначенное в очереди, и свойство (_oldestIndex), которое может рассказать нам самый старший номер индекса (ключа) в очереди.

Мы достаточно изучили size(), поэтому перейдем теперь к enqueue(data).

Метод 2 из 3: enqueue (data)

Для enqueue у нас есть две цели:

  1. Используйте _newestIndex в качестве ключа this._storage и используйте любые данные, добавляемые в качестве значения этого ключа.
  2. Увеличьте значение _newestIndex на 1.

На основе этих двух целей мы создадим следующую реализацию enqueue(data):

Тело этого метода содержит две строчки кода. В первой строке мы используем this._newestIndex для создания нового ключа для this._storage и назначения ему data. this._newestIndex всегда начинается с 1. На второй строке кода мы увеличиваем значение this._newestIndex на 1, которое обновляет его значение до 2.

Это весь код, который нам нужен для enqueue(data). Давайте теперь реализуем dequeue().

Метод 3 из 3: dequeue()

Вот цели для этого метода:

  1. Удалить самые старые данные в очереди.
  2. Увеличить _oldestIndex на 1.

В теле dequeue() мы объявляем две переменные. Первой переменной oldestIndex присваивается текущее значение очереди для this._oldestIndex. Второй переменной, deletedData, присваивается значение, содержащееся в this._storage[oldestIndex].

Затем мы удаляем самый старый индекс в очереди. После его удаления мы увеличиваем значение this._oldestIndex на 1. Наконец, мы возвращаем данные, которые мы только что удалили.

Подобно проблеме в нашей первой реализации pop() с стеком, наша реализация dequeue() не обрабатывает ситуации, когда данные удаляются до добавления каких-либо данных. Нам нужно создать условное выражение для обработки этого прецедента.

Всякий раз, когда значения oldestIndex и newestIndex не равны, мы выполняем ранее имевшуюся логику.

Полная реализация очереди

Наша реализация очереди завершена. Давайте рассмотрим весь код.

Заключение

В этой статье мы рассмотрели две линейные структуры данных: стеки и очереди. Стек хранит данные в последовательном порядке и удаляет последние добавленные данные; Очередь хранит данные в последовательном порядке, но удаляет самые старые добавленные данные.

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

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Code tutorials. Never miss out on learning about the next big thing.
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.