Circular Queue

Views:
 
Category: Education
     
 

Presentation Description

What is Queue in Data Structure ? How and Why the concept of circular queue arrive ? How it functions? Small Program in C++

Comments

Presentation Transcript

Circular Queue: 

Circular Queue

Queue: 

Queue also called as First-In-First-Out It means “Among the various Items, the item that was pushed inside the BOX earliest of all will come of the box in the first time after getting processed. Ticket A B C D E

Queue: 

Queue The Place of Entrance is called REAR (R) The Place of coming out is called FRONT (F) 1. PUSH (A) 2. PUSH (B) 3. PUSH (C) 4 . POP() R F R F R F R F A A A B B B C C A

PowerPoint Presentation: 

5. PUSH (D) 6. PUSH (E) 7. POP ( ) 8. PUSH (F ) R F B C D R E B C D F E C E D B R F C D E R F Not Permitted BUT Still these are EMPTY Spaces Queue

PowerPoint Presentation: 

Circular Queue To Solve this problem - in the presence of empty places the queue list gives “ NO EMPTY PLACE ” type message . The Queue type Circular Queue is used.

PowerPoint Presentation: 

Circular Queue 5. PUSH (D) 6. PUSH (E) 7. POP ( ) 8. PUSH (F ) R F B C D R E B C D F E C E D B R F C D E R F F In Circular Queue after the last record place, the R comes to first record

PowerPoint Presentation: 

0 1 2 3 4 C D E F R F Circular Queue Here , Size of this Circular Queue is 5 The item are PUSHED at the place : (R+1) mod 5 In C++, the operator used is ‘%’ (R+1) % 5

PowerPoint Presentation: 

Circular Queue The value of Rear ( R ) and ( F ) is Initialized at -1 int R = -1, F = -1; Before PUSHING any Check If ( (R+1) % 5 ==F) cout<<“ Not Space is Vacant” Before POPPING any Check If ( (R== -1) && (F== -1)) cout<<“ No Item Inside” 0 1 2 3 4 C D E F R F

PowerPoint Presentation: 

Circular Queue Functions in C++, variables used are void Push (char item, int &R) { if ((R+1) % size == F) cout<< “No Space Inside”; else { R = (R+1) % size; Cir_Queue[R] = item; } } Global Variable const int size = 5; Local Variables int R = -1, F= -1; int Cir_Queue [size]; 0 1 2 3 4 C D E F R F

PowerPoint Presentation: 

Circular Queue Functions in C++ void POP (int &F, int &R) { if ((F == -1) && (R==-1)) cout<<“Queue is empty”; else {cout<< Cir_Queue[F]; if (R ==F) { R = -1; F= -1; } else F = (F+1 ) % size; } } 0 1 2 3 4 C D E F R F

PowerPoint Presentation: 

Circular Queue Functions in C++ void Display () { if( (R==-1) && (F ==-1)) cout<<“Queue is empty”; else { int temp = F; do { cout<<Cir_Queue[temp] <<“ “; temp = (temp+1) % size; } while (temp != R); cout<< Cir_Queue; // when temp==R } } 0 1 2 3 4 C D E F R F