我正在制作一个音乐流媒体应用程序。其中一个功能是播放队列，很像 Spotify 的，其中歌曲将自动从您开始的艺术家、专辑或播放列表中播放，或者播放您已排队的歌曲（如果有的话）。
我正在考虑为此需要什么数据结构。我目前正在权衡使用优先队列的选项，其中排队的歌曲优先于非排队的歌曲；或两个正常队列，一个自动队列和一个排队歌曲队列。我也愿意接受任何更好的解决方案。
我应该选择什么数据结构？
问问题
3483 次
1 回答
4
很可能是两个队列。
对于优先级队列（至少一个堆），操作需要 O(log n)，而两个队列需要 O(1)。并不是说它会有很大的不同，除非你有一个超级性能关键的应用程序并且有足够的项目来实际产生明显的差异（并且堆可能会带来足够的开销来使其变慢n）。
两个队列也应该使实现更简单，更易于理解，这应该是这里的决定因素。
但是，您不能只排一个队列 - 为选定的歌曲吗？如果队列为空，则可以随机生成下一个，假设您不想显示接下来将要播放的几首不在队列中的歌曲。
一个随机的音符——你可能想要跟踪已经播放的歌曲，以尽量减少生成歌曲的方式，从而消除同一歌曲播放频率过高的可能性——为此，你可能会使用哈希表。
于 2014-03-23T20:56:58.167 回答