Search code examples
data-structuresstackqueuepriority-queueabstract-data-type

Why can't a priority queue wrap around like an ordinary queue?


I know that in order to improve efficiency, Queues use the wrap around method, to avoid to move everything down all the time that we delete an element.

However, I do not understand why Priority Queues can't wrap around like ordinary Queues. In my point of view, Priority Queues have more similar behaviour to Stack than to a Queue, how is it possible?


Solution

  • The most common priority queue implementation is a binary heap, which would not benefit from wrapping around. You could create a priority queue that's implemented in a circular buffer, but performance would suffer.

    It's important to remember than priority queue is an abstract data structure. It defines the operations, but not the implementation. You can implement priority queue as a binary heap, a sorted array, an unsorted array, a binary tree, a skip list, a linked list, etc. There are many different ways to implement a priority queue.

    Binary heap, on the other hand, is a specific implementation of the priority queue abstract data type.

    As for stack vs queue: in actuality, stacks and queues are just specializations of the priority queue. If you consider time as the priority, then what we call a queue (a FIFO data structure), is actually a priority queue in which the oldest item is the highest priority. A stack (a LIFO data structure) is a priority queue in which the newest item is the highest priority.