CEDPrimitive operationsA solution: Circular ArrayAdd 20Now we performDequeueTo add an element ‘num’ in the queueint DequeueQUEUES- A queue is a list from which items may be deletedat one end (front) and into which items may beinserted at the other end (rear)- Similar to checkout line in a grocery store - firstcome first served. - It is referred to as a first-in-first-out (FIFO) datastructure.- Queues have many applicationsSimulation of real world problems- customer line management in banks- checkout points in supermarkets- airline flight scheduling- flight handling at airports……..1front rear- in computer systems:- jobs in a single processor computer- print spooling- information packets in computer networks.- Primitive operationsenqueue (q, x): inserts item x at the rear of the queue qx = dequeue (q): removes the front element from q and returns itsvalue.isEmpty(q) : true if the queue is empty,otherwise false.Exampleenqueue(q, ‘A’);enqueue(q, ‘B’);enqueue(q, ‘C’);2x = dequeue(q);enqueue(q, ‘D’);enqueue(q, ‘E’);x= dequeue (q) -> x= ‘A’Array ImplementationA huge array and two variables (indices) front and rear to point the first and the last elements of the queue.0 1 2 3 4 5 6 7 8 9 10 11 12 13 143frontrearA B CfrontrearB C D E5 3 8 11 9 4Initially:q.rear = -1;q.front = 0; /* queue is empty when rear < front */- Addition and deletion are simple.- Good if the queue is often emptied.- Disadvantage: needs a huge array as the number ofslots would go on increasing as long as there areitems to be added to the list (irrespective of howmany items are deleted, as these two areindependent operations.)Ignoring overflow and underflow, insert and remove can be implemented as:4front rear/* number of elements in the queue = rear – front + 1 */enqueue(q, x):q.rear = q.rear +1;q.items[q.rear] = x;x = dequeue(q):x = q.items[q.front];q.front = q.front + 1;Problems with this representation:Although there is space we may not be able to add a new item. An attempt will cause an overflow.0 1 2 3 4C D E5rearfrontIt is possible to have an empty queue yet no new itemcan be inserted.( when front moves to the point of rear)A solution: Circular ArrayA good method to implement queues (efficient use of space) is to view the array as if it is a circular array. This enables us to utilize the unavailable slots provided front and rear are handled carefully. -6equivalently:Let us take an example of a Queue with 7 slots, i.e. size is 7. Initially there are no elements, so let us keep both front and rear equal to – 1 .7frontrear10 size-1Size - 2front rearNow we let us study the effect of following operations and see how front and rear values are changed.Add 20Since rear = – 1, element will be stored in slot 0. 0 1 2 3 4 5 620Now there is one element in the queue in the slot 0. So it is the first element, so front = 0, it is also the last element , so rear = 0. This means whenever front = – 1 and an element is added , we have to make front = 0Front0rear0 Add 15.20 15Now front remains at 0. There are two elements so the last element added causes value of rear to move to 1.Front0rear18Follow it with Add 6 and Add 11. This will take rear to 3. What does it imply? If rear is not yet equal to size – 1 , then increment rear and put the new element there.20 15 6 11Front0Rear3At this point we ask the Queue to remove an element (Dequeue). It is going to remove the element being pointed by front, viz. 20 in this case. This means the element at front is now 15 located at position 1.15 6 11Front1Rear39Now we perform Add 9Add 7DequeueThis will cause front to move to 3, as 11 is the element currently in front.11 9 7Front3Rear5Next we perform Add 8. This will apparently show that there is no more space in the queue after the last slot. 11 9 7 8Front3Rear6At this point suppose we want to add another element say 4. The new element can be accommodated only in the first position, 10which means if rear = size – 1 , then put the element in slot 0 and make rear = 0.4 11 9 7 8Front3rear0Next we do Add 6 , followed by Add 1. The picture at this stage looks like this4 6 1 11 9 7 8Front3rear2Now can we do Add 3?We cannot do so, as the Queue is physically full. We can see that ourselves. But how would a program find out that the area allocated tothe queue is full? Observe how front and rear are related. You will always see that if front = rear + 1, then it means the queue is full.11Suppose this was the picture at some stage8Front6rear6And we perform a Dequeue. The list is going to be empty after that. So we remove the element in the position of frontand make front = rear = – 1, to indicate that list is completely empty. On the other hand for the following situation if we Dequeue, when front is at 6 ( i.e. size – 1 ) and rear not equal to front, 3 5 8Front6rear112Then we have to make front = 0, else for all other cases on Dequeue we simply do front ++So when do we say that the Queue is empty? when front = – 1. When do we say that the Queue is full?There are two situations:1) front = 0 and rear = size – 1 OR2) front = rear + 1.We are now in a position to implement a Queue through thefollowing pseudo-code:Let total number of available slots : sizeInitializationrear = – 1 ; front = – 1 ;13To add an element ‘num’ in the queue enqueue ( int num){ if ( list not full) if ( rear == size – 1 || rear == –1 ) { a[ 0 ] = num; rear = 0; if ( front == – 1 ) front = 0; } else a[ ++ rear} = num; else printf( “ queue is full \n”); }To remove an item from the queue: int Dequeue{ if (list not empty){ tmp = a[ front] ; if ( front == rear) rear = – 1; front = – 1; else if (front == size – 1 ) front = 0; else 14front ++; return tmp; }list is full bool isFull( ) {return front == 0 && rear == size– 1 | | front == rear + 1; }list not empty bool isEmpty ( ) { return front == – 1 ;}15Application of Queues:Queues are frequently used in simulation studies for real world applications, such as customers queuing up at a bank,at Federal offices, at shopping malls or supermarkets, or trucks waiting for service at a weighing station on an interstate, parts on an assembly line waiting to be loaded on to some machine, messages waiting to get across a network, computer jobs (processes) waiting to be processedby the server, flights waiting to land or take off at an air strip, railway