Topics to be covered:
- Definition of the circular queue
- The circular queue of processes
- Operations on circular queues with algorithms
- Performance
Definition
The arrangement of elements in the queue by making the queue spill over the elements from the last position of the array to the 0th element makes it a circular queue wherein as soon as Rear or Front exceeds N − 1, it is set to 0.
Now, there is no end of the queue. The Rear and Front will move around in the queue in the circle and no locations shall be left vacant.
The advantage of a circular queue over a linear queue is the better optimization of memory and space.
Circular Queue Operation
- Addition ( enqueue)
- Deletion ( dequeue)
Addition ( enqueue) operation in circular queue
- Adding item C to the queue.
- The Rear is pointing to location N−1.
- After incrementing Rear (i.e., Rear = Rear + 1 = N − 1 + 1 = N), we find that it is pointing to a location equal to N, which does not exist.
- Therefore, Rear is set to location 0, the beginning of the array, and the item ‘C’ is stored at this location pointed by Rear.
- This arrangement ensures that there will be no space left unutilized in the queue. For instance, let us add one by one the items ‘I’, ‘R’, ‘C’, ‘U’, ‘L’, ‘A’, and ‘R’ to the queue.
- The locations left of the Front are now being filled, removing the drawback of linear queues.
- A stage will come after more additions, when Rear becomes equal to Front (Rear = Front), indicating that the queue is full.
Algorithm for Addition(enqueue)
algorithm addQ()
{
Step
1. if ( ((Rear+1)%N)==Front )
then { prompt (Queue Full); exit }
2. Rear = (Rear + 1)%N;
3. cirQ [Rear] = item;
4. stop
}where
- cirQ[N] is an array that represents a queue of size N locations.
- Variable called Front keeps track of the front of the queue.
- A variable called Rear keeps track of the rear end of the queue.
- A variable called item is used to store the item to be added or deleted from the queue.
Deletion ( dequeue ) operation in the circular queue
- Deleting an element from the queue.
- The Front is pointing to location N−1.
- After incrementing Front (i.e., Front = Front + 1 = N − 1 + 1 = N). We find that it is pointing to a location equal to N, which does not exist.
- Therefore, Front is set to location 0, the beginning of the array, and the item ‘C’ is deleted from this location pointed by Front.
- A stage will come after more deletions, when Front becomes equal to Rear (Front = Rear), indicating that the queue is empty.
- The conflict for events—queue ‘full’ and ‘empty’—the condition to be tested is (Rear = Front) and can be resolved by the following decisions:
- The queue empty condition remains the same, i.e., ‘Front == Rear’.
- In case of queue full, the condition ‘Rear + 1 == Front’ would be tested.
- In this arrangement, one location, being pointed by Front, shall remain vacant.
- The following formulae would be used for automatic movement of the variables ‘Front’ and ‘Rear’ within the circular queue:
- Rear = ( Rear +1 ) mod N
- Front = ( Front + 1 ) mod N
- where N is the size of the queue.
Algorithm for Deletion(dequeue)
Algorithm delQ()
{
Steps:
1. if ( Front == Rear)
then prompt ( Queue Empty );
else
Front = ( Front + 1 ) % N;
Item = Queue [Front];
return Item;
2. stop
}
where
- cirQ[N] is an array that represents a queue of size N locations
- Variable called Front keeps track of the front of the queue.
- A variable called Rear keeps track of the rear end of the queue.
- A variable called item is used to store the item to be added or deleted from the queue.
Performance
- Space complexity is O(n).
- The time complexity for each operation is O(1).
Circular Queue
- Circular queue can be implemented by one-dimensional array.
- The last location of the array is immediately followed by the 0th location to view it as a circle.
- The Queue full condition: (Rear + 1) % N == Front.
- The queue empty condition: Front == Rear.
- However, at least one location remains vacant all the time.
You can try the practical on that on virtual labs.
