Структурирование данных с помощью 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 = 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; delete this._storage; 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; delete this._storage; this._size--; return deletedData; } };

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

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

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

function Stack() { this._size = 0; this._storage = {}; } Stack.prototype.push = function(data) { var size = ++this._size; this._storage = data; }; Stack.prototype.pop = function() { var size = this._size, deletedData; if (size) { deletedData = this._storage; delete this._storage; 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 = 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; delete this._storage; this._oldestIndex++; return deletedData; };

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

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

What You"ll Be Creating

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

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

Стек

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

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

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

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

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

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

• 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) данные из стека. Начнем с добавления данных.

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

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

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

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

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

Наше реализация 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. Верните последние удаленные данные.

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

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

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

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

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

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

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

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

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

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

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

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

Очередь

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

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

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

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

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

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

• 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: size()

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

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

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. Следующий билет, доступный в системе билета клиента, - 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) :

Queue.prototype.enqueue = function(data) { this._storage = 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.

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

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

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

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

Queue.prototype.dequeue = function() { var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex !== newestIndex) { deletedData = this._storage; delete this._storage; 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 = data; this._newestIndex++; }; Queue.prototype.dequeue = function() { var oldestIndex = this._oldestIndex, newestIndex = this._newestIndex, deletedData; if (oldestIndex !== newestIndex) { deletedData = this._storage; delete this._storage; this._oldestIndex++; return deletedData; } };

Заключение

Cho is a full-stack web-application developer. He dislikes mean people but likes the MEAN stack (MongoDB, ExpressJS, AngularJS, Node.js). During a typical week, he"ll be coding in JavaScript, writing about JavaScript, or watching movies NOT about JavaScript.

Stacks, queues and deques are the most basic of the slightly more advanced data structures you will meet. The good news is that they are very, very easy to implement in JavaScript.

JavaScript Data Structures

Contents

1. * First Draft

JavaScript has a really useful Array object that can be used to create some of the most basic data structures - stacks and queues. In this short article we take a look at how to create stacks and queues and describe some aspects of why they are useful.

The LIFO stack

It is always difficult to know which stack is the most basic but the LIFO or Last In First Out stack is perhaps the most commonly used.

A simple array object already has the two basic methods needed to create a LIFO stack push and pop.

The push method will add any object to the top of the stack and the pop method will remove it. To treat an array as a LIFO stack you simply create an instance and use push and pop.

var stack=new Array();
stack.push("A);
stack.push("B");
stack.push("C"
alert(stack.pop());
alert(stack.pop());
alert(stack.pop());

If you try this out you will see the alerts display "C", "B" and "A". This is the key property of a LIFO stack - it reverses the order of the data you store on it. You pushed A, B and then C byt you got back C, B and then A.

You can use any Array object as a LIFO stack and it is sometimes useful to treat an array as a stack for a while and then go back to working with it as an array. If you really want to create a stack object that can only be used as a stack then you have to encapsulate an Array and expose only the push and pop methods.

function Stack()
{
this.stac=new Array();
this.pop=function(){
return this.stac.pop();
}
this.push=function(item){
this.stac.push(item);
}
}

If you make the stac Array object private using a closure say then the only operations allowed on Stack are push and pop.

var stack=new Stack();
stack.push("A");
stack.push("B");
stack.push("C");

alert(stack.pop());
alert(stack.pop());
alert(stack.pop());

and again you will see the data retrieved in the order "C", "B", "A".

Notice that while we refer to the "top of the stack" push adds the object to the "end" of the array and pop removes the final element.

That is if the array has three items already stored i.e. array, array and array then push() stores its object in array.

Also notice that if you try to pop a value that doesn"t exist i.e. pop an empty stack the result is undefined. You could test for this error in the Stack object and throw an exception or some other error if the user attempts to pop an empty stack.

A typical stack will often allow you to manipulate the stack pointer say or peek at the value on the top of the stack i.e. retrieve it without removing it but these "non-stack" operations are generally not necessary.

Also notice that as you can push and pop any object onto the stack you can use it in very sophisticated ways. For example, if you need to store an object on the stack long with the time it was created you don"t need to create a more complex Stack object because you can simply push a composite object:

Push({MyData,Time});

Also notice that there is no need to worry about problems of enumeration - because you don"t naturally ever need to enumerate a stack structure.

The FIFO stack or Queue

The close relative of the LIFO stack is the FIFO - First In First Out stack - also known as the Queue because it mimics the behaviour of a queue in the real world. That is you store an item on the back of the queue and retrieve it from the front.

Once again the Array object provides methods that enable us to create a Queue directly. The unshift method adds an item to the front of the Array. To create a queue we have to remove items from the end of the Array and this we can do using the pop method again.

That is to treat an Array as a queue all we have to do is

var Q=new Array();
Q.unshift("A);
Q.unshift("B");
Q.unshift("C");

alert(Q.pop());
alert(Q.pop());
alert(Q.pop());

If you try this out you will see the data retrieved in the order "A", "B" and "C". That is a queue or a FIFO stack doesn"t change the order of the data the items are retrieved in the order that they were stored.

A queue is useful when ever you have data to deal with and not enough time to deal with it all. You simply add the data you can"t deal with to the queue and deal when it when you can. The queue ensures that it is dealt with in the order it arrived. Another name for a queue is a buffer.

If you want to create a queue object you can follow the basic idea used for the LIFO stack:

Function Queue()
{
this.stac=new Array();
this.dequeue=function(){
return this.stac.pop();
}
this.enqueue=function(item){
this.stac.unshift(item);
}
}

Var Q=new Queue();
Q.enqueue("A");
Q.enqueue("B");
Q.enqueue("C");

Alert(Q.dequeue());
alert(Q.dequeue());
alert(Q.dequeue());

The methods enqueue and dequeue aren"t standard names but they are often used. Another controversy is over whether you join the head or start of the queue ot the tail or end of the queue. It all depends on how you think about it and as long as you get the basic FIFO action it all works.

As in the case of a stack trying to remove something from an empty queue returns undefined. You can also queue complex objects and augment the queue with additional methods to return the number of items in the queue and even the nth item in the queue.

There are more complex types of queue that you can implement but these are less commonly encountered.

For example, the priority queue works int he same way but when you enqueue an item you can also specify its priority. When items are dequeued they are returned in priority order rather than the order that they arrived in. You can implement a priority queue either by keeping the array sorted in priority order or simply search for the value to be returned in an unsorted list.

You can also use more complex data structures to implement a priority queue such as the heap - see a future article for details.

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

В первом приближении массивы - это привычная и популярная структура данных. Но работа с ними как со стеком придает им не предусмотренные синтаксисом языка возможности. Добавление/удаление посредством JavaScript push/pop в конец или unshift/shift в начало не только удобно, но и практично.

Использование методов

Массив можно пополнять новыми элементами при помощи метода push. Результатом этого метода будет новое количество элементов массива. Обратная процедура - метод pop не имеет параметров, но выдает в качестве результата последний элемент массива.

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

JavaScript push object - нонсенс или прогресс?

Язык браузера не уступает своим более «свободным» коллегам в отношении объектно-ориентированного программирования, то есть так же дает возможность создавать объекты. При этом ключевого слова, обозначающего что-то, имеющее отношение к ООП, не имеет.

Вообще говоря, то, что есть в JavaScript, до сих пор не позволил себе иметь ни один «свободный» от браузера язык программирования. Самое оригинальное - создание объекта здесь - дело рук программиста, начиная с имени объекта.

Методы JavaScript pop&push при использовании объектов предоставляют программисту возможность создать многофункциональный объект в прямом значении этого слова.

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

Следующий push разместит сверху объект страницы, которую выбрал посетитель. Откат pop вернет его обратно. Движение дальше - очередной push, и так будет сформирован диалог текущего посетителя. Это может как пригодиться разработчику в смысле опыта и статистики, так и обеспечить навигацию в текущем сеансе работы сайта.

Стек, массив и организация данных

Существует много задач, когда результат требует многовариантного выбора. Если для реализации выбрать комплект операторов if или case, получится большой, длинный и ветвистый «куст» условий.

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

При помощи стека практически во всех случаях можно поступить проще.

Есть задача: нужно выбрать исполнителя из сотни доступных. Каждый исполнитель может делать что-то из трех позиций (от одной до трех в любом сочетании):

• t - делать техническое обслуживание;
• s - может полностью выполнять ремонтные работы;
• i - имеет право делать гарантийный ремонт.

Чтобы быстро выбрать исполнителя для заказа с нужным видом (видами работ), можно сделать три операции JavaScript push и слить массив в одну строку.

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

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

Вы постоянно добавляете в уме все новые и новые возможности.

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

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

И наконец, в один прекрасный день вы решили: “Сделаем это!”. И вот вы уже пытаетесь разобраться как реализовать бизнес-логику своего приложения, ту киллер-фичу, которая будет двигать продукт вперед. У вас есть идея как это сделать, и вы знаете, что способны на это.

И вот вы говорите: “Готово! Работает!” У вас есть успешный прототип! Осталось только упаковать его в веб приложение.

“Окей, сделаем сайт,” говорите вы.

А только потом вы понимаете, что для этого нужно выбрать язык программирования; нужно выбрать (современную) платформу; нужно выбрать какие-то (современные) фреймворки; нужно настроить (и купить) хранилище, базы данных и хостинг; нужно обеспечить интерфейс для администрирования; нужно обеспечить контроль доступа и систему управления контентом. Вы хотите быть бережливым (lean) и гибким (agile). Вы хотите использовать технологии, которые помогут вам быть успешным как в краткосрочной, так и в долгосрочной перспективе. А выбрать их далеко не всегда так просто.

Перед вами десятки и десятки архитектурных решений, которые необходимо принять. И вы не хотите ошибиться: требуются технологии, которые позволят вести быструю разработку, поддерживают постоянные итерации, максимальную эффективность, скорость, устойчивость и многое другое. Вы хотите быть бережливым (lean) и гибким (agile). Вы хотите использовать технологии, которые помогут вам быть успешным как в краткосрочной, так и в долгосрочной перспективе. А выбрать их далеко не всегда так просто.

“Я перегружен”, говорите вы и чувствуете себя перегруженным. Энергия уже не та, что была в начале. Вы пытаетесь собраться с мыслями, но работы слишком много.

Прототип медленно блекнет и умирает.

Предложение

После того, как я забросил кучу идей по похожим причинам, я решил спроектировать решение для этой проблемы. Я назвал этот проект ‘Init ’ (или init.js).

Основная идея – использовать один проект для старта любого проекта, дать возможность разработчику или техническому руководителю принять все основные решения за раз и получить подходящий начальный шаблон, основанный на них. Я знаю, многие скажут “Нельзя применить одно решение ко всем проблемам” (haters gonna hate). И они, возможно, правы. Но мы можем постараться создать подходящее в целом решение, и, на мой взгляд, Init с этой задачей справился.

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

Компоненты

Компонентное представление – одна из ключевых характеристик любой системы, так как она позволяет повторно использовать компоненты программного обеспечения в нескольких проектах, что является основной целью Init. Но компонентное представление содержит в себе побочный эффект – заменяемость, которая станет нашим основным союзником в борьбе с различными проблемами, решение которых “почти” одинаково.

Простота разработки

Какая-то проблема где-нибудь имеет решение, лучше всего реализованное на Brainf*ck . будет практически невозможной для написания, не говоря уже о чтении. Это будет стоить вам времени и громадных усилий. В целом, вы должны использовать языки и платформы, которые упрощают, а не усложняют разработку для вас (и тех, кто будет делать ее позже).

Сообщество

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

Я покажу как принимал решения при создании Init, не забывая про эти цели.

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

Но эти идеи не были новыми, почему же они стали так популярны с приходом Node.js? Простое неблокирующее программирование достигается несколькими способами. Пожалуй, самый простой это использовать обратные вызовы (callbacks) и цикл событий –- event loop . В большинстве языков это непростая задача: если обратные вызовы это довольно распространенная функция, то цикл событий – нет, и в какой-то момент вы оказываетесь в схватке с внешними библиотеками (например: Python, с Tornado). Но в JavaScript обратные вызовы это часть языка, как и цикл событий, и каждый программист, который хотя бы пробовал JavaScript, знаком с ними (или как минимум использовал их, даже если не до конца понимал что такое event loop).

Внезапно, любой стартап на Земле может повторно использовать разработчиков (читай: ресурсы) и на клиентской и на серверной стороне, решая кадровую проблему , “Нам нужен гуру Питона”.

Да, альтернативы JavaScript’у рождаются каждый день, например, CoffeeScript , TypeScript и миллионы языков, которые компилируются в JavaScript . Эти альтернативы могут быть полезными на этапах разработки (), но им не удастся заменить JavaScript в долгосрочной перспективе по двум причинам: их сообщества никогда не станут больше, и их лучшие возможности будут реализованы в ECMA Script (читай: JavaScript). JavaScript это не язык ассемблера, это высокоуровневый язык программирования с исходных кодом, который вы можете понять, так что вы должны понять его.

К сожалению, вынужден признаться, что у меня очень мало опыта с Angular.js, так что я исключу его из этой дискуссии. Итак, Ember.js и Backbone.js представляют собой два разных пути для решения одной проблемы.

Минимален, прост и предлагает вам необходимый минимальный набор для написания простого SPA. Ember.js же - это полноценный и профессиональный фреймворк для создания одностраничных приложений. В нем больше возможностей, но и кривая обучаемости круче.

В зависимости от размера приложения, решение может быть таким же простым, как анализ отношения “используемые функции / доступные функции”. Оно даст вам хорошую подсказку.

В случае с Init, я хотел покрыть большинство сценариев, поэтому выбрал Backbone.js для простого создания SPA, с Backbone.Marionette.View для компонентизации. В такой схеме каждый компонент - это простое приложение, а конечный продукт может быть настолько комплексным насколько я захочу.

Стилизация – это тоже большая задача, но мы в очередной раз можем рассчитывать на фреймворки. Для CSS нет ничего лучше