Реализация стеков и очередей в JavaScript

переводить: сумасшедший технарь

оригинальный:code.TuTuCyprus.com/articles/big…

иллюстрировать: Эта колонка была впервые опубликована в общедоступном аккаунте: jingchengyideng.

Стеки и очереди — две наиболее часто используемые структуры данных в веб-разработке. Подавляющее большинство пользователей, даже веб-разработчики, не знают об этом удивительном факте. Если вы программист, послушайте меня с двумя вдохновляющими примерами: использование стеков для организации данных, реализация операций «отмены» в текстовых редакторах; использование очередей для обработки данных, реализация циклов событий веб-браузера для обработки событий (щелчок, наведение Гувер и др.).

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

куча

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

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

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

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

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

Теперь, когда у нас есть базовое представление о модели стека, следующим шагом будет определение двух операций над стеком:

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

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

Теперь приступим к написанию кода для стека!

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

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

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

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

методы стека (операции)

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

Способ 1/2: push(data)

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

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

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

Stack.prototype.push = function(data) {
    // increases the size of our storage
    var size = this._size++;
 
    // assigns size as a key of storage
    // assigns data as the value of this key
    this._storage[size] = data;
};

Когда мы реализуем метод push(data), нам нужно включить следующую логику: объявить размер переменной и присвоить ее this._size++. Укажите ключ размера this._storage и присвойте данным значение соответствующего ключа.

Если мы вызовем метод push(data) 5 раз, то размер стека будет равен 5. Когда они помещаются в стек в первый раз, данные будут храниться в пространстве, соответствующем имени ключа 1 в this._storage, Когда они помещаются в стек в пятый раз, данные будут храниться в пространство, соответствующее имени ключа 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() удовлетворяет четырем указанным выше пунктам. Во-первых, мы объявляем две переменные: размер используется для инициализации размера стека, а удаленные данные используются для хранения последних данных, добавленных в стек. Во-вторых, мы удаляем пару ключ-значение последних добавленных данных. В-третьих, мы уменьшаем размер стека на 1. В-четвертых, возвращаем удаленные из стека данные.

Если мы протестируем реализованный в настоящее время метод pop(), то обнаружим, что он применим к следующим случаям: если мы поместим данные в стек, размер стека увеличится на 1, а если мы вытолкнем() данные из стека, размер стека уменьшится на 1!

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

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;
    }
};

Из стека в очередь

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

очередь

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

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

Представьте немного дальше, что на этом билете стоит цифра «1». На следующем билете стоит цифра «2». Клиенты, получившие два билета, будут обслуживаться вторыми. (Если бы наша система продажи билетов работала как стопка, первый клиент, вошедший в стопку, был бы обслужен последним!)

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

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

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

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

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

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

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

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

метод очереди

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

Способ 1/3: размер ()

Этот метод имеет два эффекта:

Возвращает длину текущей очереди.
Держите правильный диапазон ключей в очереди.

Queue.prototype.size = function() {
    return this._newestIndex - this._oldestIndex;
};

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

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

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

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

Это oldIndex и используйте эти два атрибута newestIndex в очереди. Все это кажется запутанным — и теперь я все еще иногда чувствую себя запутанным. Следующий пример может помочь мне разобраться со всей логикой.

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

_newestindex представляет билет системы продажи билетов для клиентов.
_oldestindex представляет тикет системы тикетов сотрудников.

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

Когда клиент покупает билет, номер билета клиента получается из _newestIndex, и номер билета равен 1. Следующий номер тикета для клиентской тикетной системы — 2.
Сотрудники не покупают билеты, а текущий номер билета в системе продажи билетов для сотрудников — 1.
Получаем текущий тикет номер 2 в системе клиента, вычитаем номер 1 в системе сотрудника, и получается 1. Число 1 представляет собой количество билетов, которые все еще находятся в очереди и не были удалены.
Сотрудник получает билет из своей системы продажи билетов, этот билет представляет собой номер билета обслуживаемого клиента, полученный из _oldestIndex, число равно 1.
Повторите шаг 4, теперь разница равна 0 и других билетов в очереди нет.

Теперь свойство _newestindex может сообщить нам максимальный номер (ключ) билета, назначенного в очередь, а свойство _oldestindex может сообщить нам номер (ключ) билета, который первым попал в очередь.

После обсуждения size() давайте рассмотрим метод enqueue(data).

Способ 2/3: поставить в очередь (данные)

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

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

На основе этих двух функций мы напишем код для метода enqueue(data):

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

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

Выше приведен весь код метода enqueue(data) . Теперь давайте реализуем метод dequeue().

Метод 2/3: удаление из очереди()

Вот два функциональных пункта этого метода:

Удалить самые старые данные в очереди.
Свойство _oldestIndex увеличивается на 1.

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

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

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

Подобно проблеме, возникшей в первой реализации метода pop() стека, метод 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;
    }
};

Всякий раз, когда значения oldIndex и 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;
    }
};

заключительные замечания

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

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