Scribd
Upload
82 views

Circular Queue and Priority Queue

A circular queue is a linear data structure that uses FIFO principles with the last position connected to the first to form a circle. It allows for insertion from the rear and deletion from the front. Common operations include getting the front/rear items, enqueuing by inserting at the rear if not full, and dequeuing by deleting from the front if not empty. A priority queue associates a priority with each item and dequeues higher priority items first, serving same priority items in order. Common operations are insertion, getting highest priority item, and deleting highest priority item. It can be implemented with arrays by adding to the end and searching linearly or with linked lists by maintaining descending priority order and removing the head in O(1) time

Uploaded by

PARTH SUNIL CHAVAN 20BCI0055
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
82 views

Circular Queue and Priority Queue

A circular queue is a linear data structure that uses FIFO principles with the last position connected to the first to form a circle. It allows for insertion from the rear and deletion from the front. Common operations include getting the front/rear items, enqueuing by inserting at the rear if not full, and dequeuing by deleting from the front if not empty. A priority queue associates a priority with each item and dequeues higher priority items first, serving same priority items in order. Common operations are insertion, getting highest priority item, and deleting highest priority item. It can be implemented with arrays by adding to the end and searching linearly or with linked lists by maintaining descending priority order and removing the head in O(1) time

Uploaded by

PARTH SUNIL CHAVAN 20BCI0055
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 13

CIRCULAR QUEUE

 Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First
Out) principle.
 The last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.
CHARACTERISTICS OF A CIRCULAR QUEUE

 Based on FIFO
 Has two ends front and rear
 Insertion from rear
 Deletion from front
OPERATIONS ON CIRCULAR QUEUE:

 Front: Get the front item from queue.


 Rear: Get the last item from queue.
 enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new
element is always inserted at Rear position.
 Steps:Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
 If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set
rear=0 and insert element.
 deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is
always deleted from front position.
 Steps:Check whether queue is Empty means check (front==-1).
 If it is empty then display Queue is empty. If queue is not empty then step 3
 Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and
return the element.
PRIORITY QUEUE
 Every item has a priority associated with it.
 An element with high priority is dequeued before an element with low priority.
 If two elements have the same priority, they are served according to their order in the queue.
A TYPICAL PRIORITY QUEUE SUPPORTS FOLLOWING OPERATIONS.

insert(item, priority): Inserts an item with given priority.


getHighestPriority(): Returns the highest priority item.
deleteHighestPriority(): Removes the highest priority item.
 insert() operation can be implemented by adding an item at end of array in O(1) time.
 getHighestPriority() operation can be implemented by linearly searching the highest priority item in array. This
operation takes O(n) time.
 deleteHighestPriority() operation can be implemented by first linearly searching an item, then removing the item
by moving all subsequent items one position back.
LINKED LIST IMPLEMENTATION OF A PRIORITY QUEUE

 The list is so created so that the highest priority element is always at the head of the list.
 The list is arranged in descending order of elements based on their priority. This allow us to remove the highest
priority element in O(1) time.
 To insert an element we must traverse the list and find the proper position to insert the node so that the overall
order of the priority queue is maintained.
 This makes the push() operation takes O(N) time.

You might also like