Page 172 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 10: Queues

queue is holding 100 elements. In case, some of the elements at the front are deleted, the element Notes
at the last position in the queue continues to be at the same position and there is no efficient way
to find out that the queue is not full. In this way, space utilization in the case of linear queues is
not efficient. This problem is arising due to the representation of the queue.
The alternative representation is to depict the queue as circular. In case, we are representing the
queue using arrays, then, a queue with n elements starts from index 0 and ends at n – 1.
So, clearly, the first element in the queue will be at index 0 and the last element will be at n – 1
when all the positions between index 0 and n – 1 (both inclusive) are filled. Under such
circumstances, front will point to 0 and rear will point to n – 1. However, when a new element
is to be added and if the rear is pointing to n – 1, then, it needs to be checked if the position at
index 0 is free. If yes, then the element can be added to that position and rear can be adjusted
accordingly. In this way, the utilization of space is increased in the case of a circular queue.
In a circular queue, front will point to one position less to the first element anti-clock wise.
So, if the first element is at position 4 in the array, then the front will point to position 3. When
the circular queue is created, then both front and rear point to index 1.

!
Caution The circular queue is empty in case both front and rear point to the same index.
Figure 10.7 depicts a circular queue.

Figure 10.7: A Circular Queue (Front = 0, Rear = 4)

Algorithm for Addition of an element to the circular queue:
Step-1: If “rear” of the queue is pointing to the last position then go to step-2 or else Step-3
Step-2: make the “rear” value as 0

Step-3: increment the “rear” value by one
Step-4: (a) if the “front” points where “rear” is pointing and the queue holds a not

LOVELY PROFESSIONAL UNIVERSITY 165