A priority queue is a special case of a regular queue. The only difference is that elements added to it each have a certain priority, which is defined by the algorithm and depends on the needs. The idea is that elements with a higher priority are served first, then the elements with lower priorities. If two elements have the same priority, then the order they are served in is in accordance with their position in the queue, so there are at least two possible ways to implement such an arrangement.

One would be the implementation of a sorting algorithm, which would add new elements according to their priority. This merely converts deque into a sorted list.

The other would be combing a deque for elements with the highest priority and serving them first, which makes a deque not much different from a linked list. The only difference, probably, would be that elements may be added only to the top element or the tail element.