Okay so clearly insert at start and at end should be supported.
And I also like the idea of a persisting queue.

No shuffle would mean you would have to listen always in the order you insert.

What about repeat should played songs reappear?

What if you want to play the previous song? Is that even needed?

What about if you just want to play a playlist in shuffle mode (which I usually do) should that be a different concept from the queue?

It seems some of you have a rather clear idea how it should look like so it would be cool if you would just write down how you would use and interact with your optimal queue, not specific to my questions.