Circular queue

Circular queue

1. Data Structure P. M. Patil

2. 1 2 3 Q 1 2 3 Q 20 Disadvantage of Simple Queue 40 1 2 3 Q F R -1 1 2 3 Q Insert(10) 10 F R 1 2 3 Q Insert(20) R 10 20 F 1 2 3 Q Insert(30) R F 10 20 30 Insert(40) R F 10 20 30 40 Delete() R F 20 30

3. Disadvantage of Simple Queue Insert (50) Now we can not insert a value in Simple Queue because it is OVERFLOW since R==Size-1 1 2 3 Q R F 40 20 30

4. Circular Queue In CQ we reset the Rear pointer Operations of CQ Insert Delete

5. Algorithm for Insert CQ Procedure CQINSER ( F,R,CQ,Size ) This procedure will insert an element into CQ which is a circular queue.F and R are the pointers to the front and rear of the queue respectively. Initially F and R are set to -1. Item is a temporary variable used. 1.[Reset rear pointer] If R=Size -1 then R<- 0 Else R<- R+1 2. [Check for overflow] if F=R then Write(‘Overflow’) End If 3. [Insert element in CQ] Read(Item) CQ[R]<- Item Write(‘Item is inserted in CQ’) 4. [Set front properly] If F=-1 then F<- 0 Else

6. 1 2 3 CQ 1 2 3 CQ 20 Advantage of Circular Queue 40 1 2 3 CQ F R -1 1 2 3 CQ Insert(10) 10 F R 1 2 3 CQ Insert(20) R 10 20 F 1 2 3 CQ Insert(30) R F 10 20 30 Insert(40) R F 10 20 30 40 Delete() R F 20 30

7. Advantage of Circular Queue Insert (50) Now we can insert a value in Circular Queue because R pointer is reset to 0 R=0; Memory is not wasted in circular queue. 1 2 3 Q R F 50 20 30 40

8. Algorithm for Delete CQ Procedure CQDELETE ( F,R,CQ,Size ) This procedure will delete an element from the CQ which is a circular queue. F and R are the pointers to the front and rear of the queue respectively. Initially F and R are set to -1. Item is a temporary variable used. 1.[Check CQ underflow] If F = -1 then Write(‘CQ is underflow’) Endif 2. [delete element] Item =CQ[F] Write(‘Item is deleted’) End If 3. [Reset R and F] if F=R then F -1 R=-1 4. [Increment F] If F= size-1 then F<- 0 Else F<-F+1