Структуры данных JavaScript - Стеки, Очереди и дескрипторы №2

The FIFO stack или Queue (Очередь)

Близким родственником стека LIFO является стек FIFO - Первый вход, Первый выход, также известный как Очередь, потому что он имитирует поведение очереди в реальном мире. То есть вы сохраняете элемент в конце очереди и извлекаете его из передней части.

И снова объект Array предоставляет методы, которые позволяют нам напрямую создавать очередь. Метод unshift добавляет элемент в переднюю часть массива. Чтобы создать очередь, мы должны удалить элементы из конца массива, и это мы можем сделать снова, используя метод pop.

То есть, чтобы рассматривать массив как очередь, все, что нам нужно сделать, это

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

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

Если вы попробуете это сделать, вы увидите данные, полученные в порядке "A", "B" и "C". То есть очередь или стек FIFO не изменяют порядок данных, в котором элементы извлекаются в том порядке, в котором они были сохранены.

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

Если вы хотите создать объект очереди, вы можете следовать основной идее, используемой для стека LIFO:

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());

предупреждение(Q. удаление очереди());

предупреждение(Q. удаление очереди());

Методы enqueue и dequeue не являются стандартными именами, но они часто используются. Еще один спор заключается в том, присоединяетесь ли вы к началу или началу очереди, к хвосту или концу очереди. Все зависит от того, как вы думаете об этом, и пока вы получаете базовое действие FIFO, все это работает.

Как и в случае со стеком, пытающимся удалить что-то из пустой очереди, возвращается неопределенное. Вы также можете поставить в очередь сложные объекты и дополнить очередь дополнительными методами, чтобы вернуть количество элементов в очереди и даже n-й элемент в очереди.

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

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

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

The Deque

Наиболее сложной из структур данных стека является очередь deque или двойная очередь.

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

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

И снова у объекта массива есть дополнительный метод, который вы можете использовать для реализации deque. Метод сдвига завершает набор методов мутатора "постановки в очередь" и удаляет элемент и из передней или начальной части массива.

Так что теперь у нас есть

· pop и push - удалить или добавить в конец массива

и

· shift и unshift - удалить или добавить в начало массива.

Создание объекта Deque теперь очень просто:

function Deque()
{
this.stac=new Array();
this.popback=function(){
return this.stac.pop();
}
this.pushback=function(item){
this.stac.push(item);
}
this.popfront=function(){
return this.stac.shift();
}
this.pushfront=function(item){
this.stac.unshift(item);
}
}

Реальных стандартных ярлыков для манипулирования декой не существует. Имена методов, используемые в этом примере, наиболее близки к C++, в котором использовались push_back, push_front и т. Д. для дека. Чтобы использовать его, вы просто вызываете нужные вам методы в соответствии с тем, где вы хотите добавлять или удалять элементы.

Например, что показывает следующий код:

var deque=new Deque();

deque.pushfront("A");
deque.pushfront("B");
deque.pushback("C");

alert(deque.popfront());
alert(deque.popback());

ответ - "В", за которым следует "С".

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

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

Перевод статьи с сайта: I Programmer

Статья написана - Ян Эллиот является автором Just JavaScript: Идиоматический подход; Асинхронность JavaScript; Just jQuery: Основной пользовательский интерфейс и Just jQuery: События, Асинхронность и Ajax , которые являются частью библиотеки I Programmer, опубликованной издательством I/O Press.