PowerPoint Presentation : Circular Queue 1 Queue Q[1] Q[0] Q[3] Q[2] Q[4] e-learning
PowerPoint Presentation : Various Events in a Queue are : Insert or PUSH an item inside the list Delete or POP an item already in the list 2 Queue e-learning
PowerPoint Presentation : List is made by : Array of limited Size Linking item to item using Dynamic Allocation Technique or Link-List 3 Queue e-learning
PowerPoint Presentation : Here in this example we follow the Array type technique only Q[1] Q[0] Q[3] Q[2] Q[4] 4 Queue e-learning
PowerPoint Presentation : 5 int Rear The place where new item is INSERTED int Front The place from where item is OUTPUTED < data-type > item The item (of given data-type ) to be INSERTED or OUTPUTED < data-type > ar [ ] The array declaration of fixed < size > of the same data type as declared for the of item Queue To develop a Queue in array the VARIABLES needed are : e-learning
PowerPoint Presentation : 6 int Front = -1; int Rear =-1; const int size = 5; char ch ; char Q[size]; //< initialize > //< initialize > Rear =-1 Front = -1 Q[1] Q[0] Q[3] Q[2] Q[4] Queue For the example shown values to a variable taken are e-learning
PowerPoint Presentation : 7 Events Occurring for the Queue are : PUSH(item) or Insert the item at Rear POP(item) or Output and Delete the item at Front Queue e-learning
PowerPoint Presentation : 8 For Pushing an item in the Queue Check the availability of the space before pushing the item of Rear, if (( Rear == Size-1 ) || ( Rear > Front )) When any of these two condition is TRUE Insertion will stop then. Q[1] Q[0] Q[3] Q[2] Q[4] Q[1] Q[0] Q[3] Q[2] Q[4] Rear Front Rear Front Queue e-learning
PowerPoint Presentation : Q[1] Q[0] Q[3] Q[2] Q[4] 9 Rear = 0 Front = -1 Event _01: PUSH() Queue e-learning
PowerPoint Presentation : Q[1] Q[0] Q[3] Q[2] Q[4] 10 Front = -1 Rear = 1 Event _02: PUSH() Queue e-learning
PowerPoint Presentation : Q[1] Q[0] Q[3] Q[2] Q[4] 11 Front = -1 Rear = 2 Event _03: PUSH() Queue e-learning
PowerPoint Presentation : Q[1] Q[0] Q[3] Q[2] Q[4] 12 Front = -1 Rear = 3 Event _04: PUSH() Queue e-learning
PowerPoint Presentation : Q[1] Q[0] Q[3] Q[2] Q[4] 13 Front = 0 Rear = 3 Event_05 : POP() Queue e-learning
PowerPoint Presentation : Q[1] Q[0] Q[3] Q[2] Q[4] 14 Front = 0 Rear = 3 Event _06: PUSH() Queue e-learning
PowerPoint Presentation : Q[1] Q[0] Q[3] Q[2] Q[4] 15 Event _07: PUSH() OVER-FLOW Front = 0 Rear = 3 Even when Q[0] is EMPTY Queue e-learning
PowerPoint Presentation : 16 To Solve this Circular Queue key technique is used Circular Queue e-learning
PowerPoint Presentation : 17 int Fr = -1; int Rr =-1; const int size = 5; char ch ; char Q[size]; For the example shown values to a variable taken are Fr = -1 //< initialize > //< initialize > Rr =-1 e-learning
PowerPoint Presentation : 18 For the example shown 1. Rear and Front ( Rr and Fr) move clock-wise 2. The Increment will be done using mod (%) operator Rr =-1 Remainder = Dividend % Divisor Dividend Divisor Remainder Quotient Fr = -1 e-learning
PowerPoint Presentation : 19 Event _01: PUSH() Fr =0 Rr =0 e-learning
PowerPoint Presentation : 20 Fr = -1 Event _02: PUSH() Rr =1 Fr =0 e-learning
PowerPoint Presentation : 21 Fr = -1 Event _03: PUSH() Rr =2 Fr =0 e-learning
PowerPoint Presentation : 22 Event _04: PUSH() Rr =3 Fr =0 e-learning
PowerPoint Presentation : 23 Event_05 : POP() Rr =3 Fr =1 e-learning
PowerPoint Presentation : 24 Event _06: PUSH() Fr =1 Rr =4 e-learning
PowerPoint Presentation : 25 Event _07: PUSH() Rr =0 Fr =1 Since, Rr =(Rr+1) % size Rr = 4+1 %5 Rr = 5%5 Rr =0 (Rr+1)%5 != Fr So permission granted to insert e-learning
PowerPoint Presentation : 26 Event _07: PUSH() Fr =1 Since, Rr =(Rr+1) % size Rr =0+1%5 Rr = 1%5 Rr =1 (Rr+1)%5 == Fr So permission is NOT granted to insert i.e OVER-FLOW Rr =0 e-learning
PowerPoint Presentation : 27 if (( Rear == Size-1 ) || ( Rear > Front )) Circular Queue e-learning Checking before Pushing an item in a Line Queue
PowerPoint Presentation : 28 Checking before Pushing an item in a Circular Queue if (Rear +1) % size == Front ) ( Circular Queue e-learning If (Rear>-1) { . . }