Какую структуру данных я должен использовать для очереди воспроизведения музыки?

Question

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

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

Какую структуру данных я должен выбрать?

Answer 1

Скорее всего две очереди.

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

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

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

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