DS - реализация очереди в JS

Каждый, кто занимается программированием, наверное, слышал о Queue, Stack и т. Д. Хотя бы раз в жизни, верно? Некоторые из вас, возможно, уже знакомы с этими концепциями, а некоторые нет. Иногда для некоторой структуры данных понять концепцию - это одно, а реализовать ее на практике (то есть на определенном языке) - совсем другое дело.

Сегодня я расскажу о очереди и о том, как легко - и эффективно реализовать ее в JavaScript.

Так что же такое очередь?

Говоря простым языком, очередь

Ага, именно так, как вы видите. На языке структур данных Очередь - это динамический набор, в котором:

• Элемент вставляется (ENQUEUE) в конец очереди (хвост).
• Элемент удаляется / удаляется (DEQUEUE) из начала очереди (заголовок).

И операция удаления основана на FIFO (First-In, First-Out) - как и в реальной очереди, человек, оставшийся дольше всех (он же первый прибыл в очередь) должен идти первым.

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

• EnQueue
• DeQueue

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

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

Хорошо, это должно дать вам четкое представление об очереди. Теперь перейдем к тому, как эффективно реализовать это в JS.

Анализ

Самый простой способ реализовать очередь в JS - это сохранить массив в качестве хранилища, и каждый вызов DeQueue () мы будем использовать array.shift () , чтобы удалить и вернуть первый элемент. Вот так просто и понятно. Однако это оказывается неэффективным и на 100% правильным, особенно в больших очередях, потому что:

• shift () занимает O (n) времени выполнения (n - размер очереди). В то время как наше целевое время работы для DeQueue () должно быть O (1).
• Большинство операций в Array Prototype в JS имеют время выполнения O (n).
• Массив - это индексированная коллекция, в которой последовательно хранятся все данные, размещенные в памяти. В случае большой очереди каждое изменение потребует перемещения большого фрагмента памяти, чтобы массив был доступен с использованием индексов.

Итак, теперь возникает вопрос: как это сделать лучше, чем использовать массив? Мой ответ - использовать вместо этого Object. В конце концов, все в JS считается Object :)!

Реализация кода

1. Настройте базовую структуру очереди

function Queue(){
    var storage = {}, //Object represents storage
        head = 0, //index of top
        tail= 0;  //index of bottom of queue
....
}   

2. Реализация логики EnQueue ()

enQueue: function(item){
     storage[tail] = item;
      tail++; //prepare tail index for next element
    }

3. Реализация логики DeQueue ()

deQueue: function(){
     var size = tail - head; //Check if Queue is empty
      
      if (size <= 0) return undefined;
      
      var item = storage[head];
      delete storage[head]; //Remove the top from Queue
      
      head++; //Move saved top index to next top.
      
      //Reset the counter if needed
      if (head === tail){
        head = 0;
        tail = 0;
      }
      return item;
}

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

Полный код реализации Демо можно найти здесь

Сложность

Как видите, доступ к свойству Object занимает время O (1), следовательно, EnQueue () и DeQueue () каждый займет O (1) постоянное время работы. Следовательно, размер очереди не повлияет на производительность ее методов.

Резюме

Таким образом, в отличие от стека, который следует логике LIFO (последний вошел - первым ушел), Queue - это эффективный динамический набор, который следует логике FIFO. Имеет 2 основных метода:

• EnQueue (item) - добавить новый элемент в очередь в хвосте.
• DeQueue () - удалить самый старый элемент из заголовка очереди.

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

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

А как насчет реализации очереди с использованием стека? :)

Если вам понравился этот пост и вы хотите узнать больше, ознакомьтесь с моими статьями.

Если вы хотите иногда меня догнать, подпишитесь на меня в Twitter | Facebook или просто посетите мой сайт-портфолио.