Why can’t a Priority Queue wrap around like an ordinary Queue?
A priority queue is a special type of queue in which each element is assigned a priority value. And elements are served based on their priority. This means that elements with higher priority are served first. However, if elements with the same priority occur, they will be served in the order in which they were queued. A priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree. Among these data structures, the heap data structure provides an efficient implementation of priority queues.
Queue Implementation with Array and Wrap Around:
A queue can be implemented using an array:
- adding and removing takes O(1) time
- size is limited
- need to monitor where the start and end of the queue is in the field
- the queue can eventually “wrap around” the end of the field – it’s not a problem, but just a special case that should be dealt with
What is Wrap Around?
In a circular queue, To solve the problem of not being able to insert an item even if the queue is not full, the front and back arrows of the queue wrap around the beginning of the field as shown in the figure. This is called a ring queue or ring buffer. Note that after the back arrow is wrapped, it is now below the front arrow, i.e. the reverse of the original arrangement.
Why can’t a priority queue wrap around like an ordinary queue?
- The most common implementation of a priority queue is a binary heap, which would not benefit from wrapping.
- You could create a priority queue that is implemented in a ring buffer, but performance would suffer.
- It is important to note that a priority queue is an abstract data structure. It defines the operations but not the implementation. You can implement a priority queue as a binary heap, sorted array, unsorted array, binary tree, skipped list, linked list, etc.
- There are many different ways to implement a priority queue.
- A binary heap, on the other hand, is a specific implementation of the priority queue abstract data type.
- Regarding stack vs queue, actually, stacks and queues are just specializations of the priority queues.
- If you think of time as a priority, then what we call a queue (a FIFO data structure) is actually a priority queue in which the oldest item has the highest priority.
- A stack (LIFO data structure) is a priority queue in which the newest item has the highest priority.