Есть ли готовая очередь для JS?

Question

[Владимир]

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

PS: Написать свою могу без проблем, но привык для таких базовых вещей больше полагаться на библиотеки, а то мало ли я где накосячу :).

Comments

[DevMan]

очередь для чего?
у этого термина есть много значений.

[Сергей Соколов]

Каковы критерии? Чем конкретно плох родной массив? Что там на github'е по звёздам?

[Владимир]

DevMan, просто очередь как тип данных. Хотя бы обычную, без приоритетов.

[DevMan]

Владимир, очередь как тип данных? очинтересно!

[Владимир]

Сергей Соколов, я же писал, родной массив хорош как стек, где у него сложность добавления и выборки O(1), но если использовать его как очередь (FIFO), то нужно использовать shift, а у него сложность O(n). У нормальной реализации очередей (через двунаправленный список) сложность put/get должна быть O(1).

[Владимир]

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

[DevMan]

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

прост уточнение, никаких холиваров.

[SagePtr]

Владимир, не обязательно делать shift, можно просто хранить индекс головы очереди, а при изъятии элемента из очереди удалять его из массива (через delete a[i]) и сдвигать индекс головы на единицу. В JS в массивах не обязательно с нуля нумеровать элементы, если из начала их поудалять - сборщик мусора это заметит и освободит память. Если, конечно, на удаляемые элементы ничто больше не ссылается и их можно безопасно выкинуть.

[Владимир]

SagePtr, интересно, спасибо. Не знал такого, привык к статическим массивам.