JHPrimitive operationsArray ImplementationA solution: Circular ArrayEnqueue 20Enqueue 15Enqueue 6Enqueue 11QUEUESA queue is simply a waiting line that grows by adding elements to its end and shrinks byremoving elements from the front. Compared to stack, it reflects the more commonlyused maxim in real-world, namely, “first come, first served”. Waiting lines insupermarkets, banks, food counters are common examples.A formal definition of queue would be a list from which items may be deleted at one end(front) and into which items may be inserted at the other end (rear). It is also referred toas a first-in-first-out (FIFO) data structure.Queues have many applications 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 its value.isEmpty(q) : Check to see if the queue is empty.isFull(q) : checks to see if there is space to insert more items in the queue.1front rearExampleConsider the following sequence of operations being performed on a queue “q” which stores single characters:enqueue(q, ‘A’);enqueue(q, ‘B’);enqueue(q, ‘C’);x = dequeue(q);enqueue(q, ‘D’);enqueue(q, ‘E’);x = dequeue(q);enqueue(q, ‘H’);x = dequeue(q);enqueue(q, ‘J’);The contents of the queue “q” after these operations would be 2frontrearD E H JArray ImplementationThe array to implement the queue would need two variables (indices) called front and rear to point to the first and the last elements of the queue. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 145 3 8 11 9 4Initially:q->rear = -1;q->front = -1; For each enqueue operation rear is incremented by one, and for each dequeue operation , front is incremented by one.While the enqueue and dequeue operations are easy to implement, there is a bigdisadvantage in this set up. The size of the array needs to be huge, as the number of slotswould go on increasing as long as there are items to be added to the list (irrespective ofhow many items are deleted, as these two are independent operations.)Problems with this representation:Although there is space in the following queue, we may not be able to add a new item. Anattempt will cause an overflow.0 12 3 4C D E3rearfrontfront rearIt is possible to have an empty queue yet no new item can be inserted.( when front moves to the point of rear, and the last item is deleted.)0 12 3 4EA solution: Circular ArrayThe solution to the above problem would be to wrap-around the array. This makes efficient use of the slots. It is also referred to as a circular array. This enables us toutilize the unavailable slots, provided the indices front and rear are handled carefully. Here again front refers to the index of the element to be next removed from the queue, and rear refers to the index of the element just added to the queue.4rearfrontequivalently: 5frontrear10 size-1Size - 2front rearTo illustrate the use of circular array, let us take an example of a Queue with 7 slots, i.e. size is 7. The indices front and rear can take on values from 0 to (size –1) corresponding to elements present in the queue. Initially there are no elements, so let us keep both front and rear equal to – 1 .Now we let us study the effect of following operations and see how front and rear indices are changed.Enqueue 20Since rear = – 1, element 20 will be stored in slot 0. 0 1 2 3 4 5 620Now there is a single element in the queue in slot 0. 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 = 0. The indices have the following values:Front0rear0Enqueue 1520 15Note this operation does not affect the index front, which remains at 0. There are two elements in the queue, so the last element added moves value of index rear to 1.Front0rear1 Enqueue 6 Enqueue 11Check if there is still space in the queue. If rear is not yet equal to size – 1 , slots are still available in the queue. So increment rear and put the new element there. This will take rear to 3.20 15 6 11Front0Rear3At this point we ask the Queue to remove an element. x =Dequeue6It is going to remove the element being pointed by front, which is 20. This means the element at front is now 15 located at position 1.15 6 11Front1Rear3Now we perform Enqueue 9Enqueue 7x =Dequeuex =DequeueThis will cause 15 and 6 be removed from the queue, and the index front to move to 3, as 11 is the element currently in front.11 9 7Front3Rear5Enqueue 8This will apparently show that there is no more space in the queue after the last slot is filled up.11 9 7 8Front3Rear6Enqueue 4What will happen now? There are no slots after 8, but part of the queue is still empty. So the new element can be put in the first position, which gives us the rule “ if rear = size – 1 , then put the element in slot 0 and assign rear = 0.”4 11 9 7 87Front3rear0Enqueue 6Enqueue 1The picture at this stage looks like this4 6 1 11 9 7 8Front3rear2Enqueue 3We cannot carry out this operation, as the Queue is physically full. We can see that ourselves. But how would a program find out that the area allocated to the queue is full? Observe how front and rear are related. You will always find that whenever front = rear + 1, it means the queue is full.Special cases of Dequeue Now just suppose at some point in time, this is how the queue looks like:8Front6rear6And we perform x=Dequeue The list is going to be empty after that. To indicate that the queue is now completely empty , we remove the last element and set front = rear = – 1Remember this is how we had initialized the queue.8There can be another situation, where again we are going to remove the element in last position of the array, but there are other elements in the queue. Consider this:3 5 8Front6rear1x=DequeueHere we simply wrap around the array and set front = 0. Thus , for Dequeue operation if front not equal to rear, and front = size – 1 Then we have to assign front = 0.For all other cases 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.9Implementation code:We are now in a