8: Circular and Priority Queue

Circular and Priority Queue
Circular Queue
The trouble of linear queue is that pretty soon the rear of the queue is at the end of the array (the highest index). Even if there are empty cells at the beginning of the array, because you ve removed them, you still can t insert a new item because Rear can t go any further.
• To avoid the problem of not being able to insert more items into the queue even when it s not full, the Front and Rear arrows wrap around to the beginning of the array. The results a circular queue (sometimes called a ring buffer). Insert enough items to bring the Rear arrow to the top of the array (index 9). Remove some items from the front of the array.
Now to insert another item. You ll see the Rear arrow wrap around from index 9 to index 0; the new item will be inserted there. This situation is shown in below Figure.
A circular queue is a Queue but a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independant, which means that you don t have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion.
Priority Queues
Like an ordinary queue, a priority queue has a front and a rear, and items are removed from the front. However, in a priority queue,
" Items are ordered by key value so that the item with the lowest key (or in some implementations the highest key) is always at the front.
" Items are inserted in the proper position to maintain the order.
A priority queue is best understood in comparison with a stack and a queue.