Page 90 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 4: Queues

/* This function checks if the queue q is empty or not * / Notes
{
if(q.front == q.rear)
return(true)
else
return(false);
}
void initialize(queue q[])
/* This procedure initializes a queue q * /
{
q.front = 0;
q.rear = 0;
}
An important point to be noticed in the above implementation is that the queue has a tendency to
move to the right unless occasionally ‘front’ catches up with ‘rear’ and both are reset to 0 again (in
the delete procedure). As a result it is possible that a considerable portion of the elements array
is free but the queue full signal is on. To get rid of this problem, we may shift the elements array
towards left by 1 whenever a deletion is made. Such a shifting is time consuming since it has to
be done for each deletion operation.
A more efficient queue representation is obtained by regarding the array of elements of a queue to

be circular. For easier algebraic manipulation we consider the array subscript ranging from 0 .. n-1;
As before, rear will point to the element which is at the end of the queue. The front points to one
position anticlockwise to the beginning of the queue. Initially, front = rear = 1 and front = rear only
if the queue is empty. Every insertion implies that the rear of the queue increases by 1 except when
rear = n -1. In that case, the rear is made zero if the queue is not full yet.
Figure 4.2 shows a circular queue with 3 elements where n = 9 front=2 and rear=5.
Figure 4.2: A Circular Queue

rear
5

4 BB CC 6

AA
3 7

front 2

8
1
0

LOVELY PROFESSIONAL UNIVERSITY 85