What determines if what message is higher priority? And can messages be even higher priority than that so you have varying degrees of priority?
Assume you have regular priority and high priority, you could enqueue high priority messages to the front of the queue.
Or you could have a second queue that gets only high priority messages. You dequeue from there first with a 0 timeout value. If that times out, then you dequeue the next message in the regular priority queue. But you'll want to have that timeout quickly also so your consumer loop can recheck the high priority queue.
But any system where messages can get jumbled around can get messy fast. What happens if a high priority messages makes some messages in the regular queue obsolete? How do you plan to handle that?