Структуры данных 101: Очереди

1656566890 struktury dannyh 101 ocheredi

от Кевина Терни

8uES-J2v2jbsRf2ZxS0ctJM8E2256VdOuZng
кредит: группа систем атт

Начиная с очереди

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

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

Итак, у нас есть отличия в порядке обработки – почему? Нам нужен другой метод обработки данных, сохраняющий порядок. К примеру, предположим, что у нас есть поток данных в узле. Когда он поступает, нам нужно что-то сделать с ним, а затем записать его в файл для чтения позже. Для простоты, предположим, что нам нужно писать каждую букву с прописной буквы. Что произойдет, если мы использовали LIFO или структуру данных стека?

YqhoftqFVXVQ0XQ22oh6Ds0IQgObVjsd1eNQ

Основная причина – очереди честно обрабатывают данные и сохраняют порядок сбора. Это также происходит, когда мы перебираем элементы с помощью циклов for или while, forEach() или map(). Каждый элемент массива обрабатывается в том порядке, в котором он был вставлен, от индекса 0 до index.length – 1.

В очередях элементы обрабатываются в порядке вставки.

Реализация

Простая реализация с использованием массивов состоит в том, что метод shift() удаляет из начала и unshift() для добавления переднего.

Как и моя публикация о Stacks, мы опишем API для очереди. Затем мы начнем с реализации с помощью псевдоклассического метода и базового объекта.

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

aQcmAeS9hN4ormkWg3L00rJZEfk3mmJdx6Pk

Чтобы отслеживать наши вещи мы используем голову для передней части очереди и хвост для задней. Разница между ними дает размер очереди.

Наш механизм хранения выглядит следующим образом:

// _underscores indicate "private variables" to other engineers
const Queue = function(capacity) {  this.storage = {};  this.capacity = capacity || Infinity;  this._head = 0;  this._tail = 0}
let q = new Queue();q; // Queue { storage: {}, capacity: Infinity, _head: 0, _tail: 0 }

Поставить в очередь:

Queue.prototype.enqueue = function(value) {  if (this.count() < capacity) {    this.storage[this._tail++] = value;    return this.count();  }  return "Max capacity reached, please remove a value before enqueuing"}

Чтобы вывести из очереди:

Queue.prototype.dequeue = function() {    if (this.count() === 0) {      return "Nothing in the queue";    }    else {      let element = this.storage[this._head];      delete this.storage[this._head];      if (this._head < this._tail) {        this._head++;      }      return element;    }}

Остальные API:

Queue.prototype.peek = function() {  return this.storage[this._head]}
Queue.prototype.contains = function(value) {  for (let i = this._head; i < this._tail; i++) {    if (this.storage[i] === value) {      return true;    }  }  return false;}
Queue.prototype.until = function(value) {  for (let i = this._head; i < this._tail; i++) {    if (this.storage[i] === value){      return i - this._head + 1;    }  }  return null;}
Queue.prototype.count = function() {  return this._tail - this._head;}
let q = new Queue();q.enqueue('ww');q.enqueue('aa');q; // Queue {capacity: Infinity, storage: { 0: 'ww', 1: 'aa' }, _head: 0, _tail: 2 }q.enqueue('bb');q.peek(); // 'ww'q.dequeue(); // 'ww'q; //Queue {capacity: Infinity, storage: { 1: 'aa', 2: 'bb' }, _head: 1, _tail: 3 }q.contains('bb'); // trueq; //Queue {capacity: Infinity,storage: { 1: 'aa', 2: 'bb' }, _head: 1, _tail: 3 }q.until('bb'); // 2q.count(); // 2

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

Цикл событий и очереди

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

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

Время выполнения – время, в течение которого выполняется программа.

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

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

Ядро системы – это центральная часть операционной системы. Он управляет операциями компьютера, памяти и оборудования, в частности ЦБ. Чтобы быть более эффективным, цикл событий разгружает определенные операции в ядро.

Теперь к циклу событий.

JavaScript является однопоточным языком. Это означает, что поток выполнения идет в порядке, и он выполняет одно дело за раз. Node.js создан на основе движка Chrome V8 и использует постоянно вращающийся цикл, ожидающий входных соединений.

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

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

Временная сложность

Операции с очередью очень эффективны. Enqueue, Dequeue, Peek и Count быстрее всего работают в постоянном времени. Contains и Until занимает больше времени, поскольку размер нашего входа увеличивается, работая в линейное время O(N);

Очередь O(1)
Отключить O(1)
Посмотреть О(1)
Граф O(1)
Содержит O(N)
К O(N)

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *