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

2015-10-19 0 ∞ 2

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

Стек

Стек

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

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

В качестве более технологичного примера стека можно привести операцию "Отменить" (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.

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

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

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()

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

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

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

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()

Цели этого метода:

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

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. Представьте себе, что наша система обслуживания клиентов имеет две системы выдачи талонов:

_newestIndex - для обслуживания клиентов;
_oldestIndex - для обслуживания сотрудников.

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

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

Метод enqueue(data)

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

Использовать _newestIndex в качестве ключа для this._storage и использовать любые добавляемые данные в качестве значения этого ключа;
Увеличить значение _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()

Задачи для этого метода:

Удалить старые элементы из очереди;
Увеличить _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;
    }
};

Заключение

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

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

LovingUA

Скажите, зачем реализация через конструктор, если намного проще все реализовать через встроенные методы массива ?

Ответить

Петр

➞ LovingUA

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