Статьи

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

Январь 6, 2019
Конечный продукт
Что вы будете создавать

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

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

Стек

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
function Stack() {
    this._size = 0;
    this._storage = {};
}

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

Методы стека

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

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

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

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

  1. Каждый раз, когда мы добавляем данные, мы хотим увеличить размер нашего стека.
  2. Каждый раз, когда мы добавляем данные, мы хотим сохранить порядок, в котором они были добавлены.
1
2
3
4
5
6
7
8
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) включает следующую логику. Объявите переменную с именем 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. Вернуть самые последние удаленные данные.
01
02
03
04
05
06
07
08
09
10
11
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() , мы обнаружим, что она работает для следующего варианта использования. Если мы push(data) в стек, размер стека увеличивается на единицу. Если мы pop() данные из нашего стека, размер нашего стека уменьшается на единицу.

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

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

01
02
03
04
05
06
07
08
09
10
11
12
13
Stack.prototype.pop = function() {
    var size = this._size,
        deletedData;
 
    if (size) {
        deletedData = this._storage[size];
 
        delete this._storage[size];
        this._size—;
 
        return deletedData;
    }
};

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

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

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

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

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

Очередь

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

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

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

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

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

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

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

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

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

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

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

1
2
3
4
5
function Queue() {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

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

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

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

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

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

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

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

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

Метод 2 из 3: постановка в enqueue(data)

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

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

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

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

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

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

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

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

  1. Удалить самые старые данные в очереди.
  2. _oldestIndex на единицу.
1
2
3
4
5
6
7
8
9
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. Наконец, мы возвращаем только что удаленные данные.

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

01
02
03
04
05
06
07
08
09
10
11
12
13
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 не равны, мы выполняем логику, которая у нас была раньше.

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

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
    }
};

Вывод

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

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

44
Share: