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

Структурирование данных при помощи JavaScript: Стек и очередь Наиболее часто используемыми в веб-программировании структурами данных являются стек и очередь. При этом многие не знают этого удивительного факта.

Стек

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

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

В виде более технологичного примера стека можно без проблем привести операцию «Отменить»(Undo) в текстовом редакторе. Каждый раз, когда текст вводится в текстовый редактор, он помещается в стек. Самое первое изменение текста представляет собой дно стека; самое последнее — вершину. Если посетитель хочет отменить самое последнее изменение, удаляется верх стека. Этот процесс может повторяться до тех пор, пока не останется ни одного изменения.

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

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

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

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

Сейчас давайте напишем программный код для стека.

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

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

function Stack() { this._size = 0; this._storage = {};}

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

Способы стека

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

Способ push(data)

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

Требования к данному способу:

  1. Каждый раз, когда мы добавляем данные, размер стека должен увеличиваться;
  2. Каждый раз, когда мы добавляем данные, порядок стека должен сохранять последовательность:
Stack.prototype.push = function(data) { // увеличение размера хранилища var size = this._size++; // назначает размер в виде ключа хранилища // назначает данные в виде значения этого ключа this._storage[size] = data;};

Объявляем переменную size и присваиваем ей значение this._size ++. Устанавливаем переменную size в виде ключа this._storage, data — в виде значения соответствующего ключа.

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

Способ 2 из 2: pop()

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

Цели для этого способа:

  1. Использовать текущий размер стека, чтобы приобрести последние добавленные элементы;
  2. Удалить последние добавленные элементы;
  3. Уменьшить _this._size на один;
  4. Вернуть последние удаленные данные.
Stack.prototype.pop = function() { var size = this._size, deletedData;   deletedData = this._storage[size];    delete this._storage[size];    this.size--;    return deletedData;};

pop() выполняет все перечисленные нами задачи. Мы объявляем две переменные: size инициализируется значением размера стека; deletedData назначается для последних добавленных в стек данных. Далее мы удаляем несколько ключ-значение из последних добавленных элементов. После этого мы уменьшаем размер стека на 1, и возвращаем данные, которые были удалены из стека.

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

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

Чтобы решить эту проблему, мы добавим в pop() оператор if:

Stack.prototype.pop = function() {    var size = this._size,        deletedData;    if(size) {        deletedData = this._storage[size];        delete this._storage[size];        this._size--;        return deletedData;    }};

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

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

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

function Stack() {    this._size = 0;    this._storage = {};}Stack.prototype.push = function(data) {    var size = ++this._size;    this._storage[size] = data;};Stack.prototype.pop = function() {    var size = this._size,        deletedData;    if(size) {        deletedData = this._storage[size];        delete this._storage[size];        this._size--;        return deletedData;    }};

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

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

Очередь

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

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

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

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

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

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

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

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

Сейчас давайте напишем код для очереди.

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

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

function Queue() {    this._oldestIndex = 1;    this._newestIndex = 1;    this._storage = {};}

Способы очереди

Сейчас мы создадим три способа, распространяющиеся на все экземпляры очереди: size(), enqueue(data) и dequeue(data).

Способ size()

Цели этого способа:

  1. Вернуть корректный размер очереди;
  2. Сохранить правильный диапазон ключей для очереди.
Queue.prototype.size = function() {    return this._newestIndex - this._oldestIndex;};

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

Представим, что мы добавляем в стек пять тарелок. Размер нашего стека — пять, и каждая тарелка имеет в себя соответствующий ей номер от 1(первая добавленная тарелка) до 5(последняя добавленная тарелка). Если мы уберем три тарелки, то у нас останется две тарелки.

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

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

Давайте представим, что первый покупатель обслужен и этот талон удаляется из очереди. По аналогии со стеком мы можем приобрести корректный размер очереди путем вычитания 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, и сейчас разница равна нулю — в очереди больше нет талонов;
  6. Сейчас у нас есть свойство (_newestIndex), которое указывает наибольшее число (ключ), назначенное в очереди, и свойство (_oldestIndex), которое указывает самый первый порядковый номер (ключ) в очереди.

Способ enqueue(data)

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

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

Мы создадим следующую реализацию enqueue(data) :

Queue.prototype.enqueue = function(data) {    this._storage[this._newestIndex] = data;    this._newestIndex++;};

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

Способ dequeue()

Задачи для этого способа:

  1. Удалить старые элементы из очереди;
  2. Увеличить _oldestIndex на один:
Queue.prototype.dequeue = function() {    var oldestIndex = this._oldestIndex,        deletedData = this._storage[oldestIndex];    delete this._storage[oldestIndex];    this._oldestIndex++;    return deletedData;};

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

Далее мы удаляем самый старый индекс в очереди. А далее увеличиваем this._oldestIndex на 1. В конце мы возвращаем данные, которые только что удалили.

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

Queue.prototype.dequeue = function() {    var oldestIndex = this._oldestIndex,        newestIndex = this._newestIndex,        deletedData;    if (oldestIndex !== newestIndex) {        deletedData = this._storage[oldestIndex];        delete this._storage[oldestIndex];        this._oldestIndex++;        return deletedData;    }};

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

Окончательная реализация очереди

Наша реализация очереди завершена:

function Queue() {    this._oldestIndex = 1;    this._newestIndex = 1;    this._storage = {};}Queue.prototype.size = function() {    return this._newestIndex - this._oldestIndex;};Queue.prototype.enqueue = function(data) {    this._storage[this._newestIndex] = data;    this._newestIndex++;};Queue.prototype.dequeue = function() {    var oldestIndex = this._oldestIndex,        newestIndex = this._newestIndex,        deletedData;    if (oldestIndex !== newestIndex) {        deletedData = this._storage[oldestIndex];        delete this._storage[oldestIndex];        this._oldestIndex++;        return deletedData;    }};

Заключение

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *