Implementation of Circular Queue using 1-d array:
The Circular QUEUE can be represented graphically as consecutive blocks when it is implemented using one-dimensional circular array. N the maximum number of elements can be added into the QUEUE is called as size of QUEUE. To represent a QUEUE an array of size N can be used:
In the above representation the size of QUEUE is 8. FORNT and REAR index variables can be used to do the DELETE and ADD operations respectively. Initially when the QUEUE is empty FORNT and REAR are assigned with a value 0, because of Lower Bound 1 of the array. When both are equal to 0, then the
QUEUE is said to be empty.
When first element is added into QUEUE, REAR and FRONT are both incremented by 1 and the element to be added is placed at REAR index of QUEUE, QUEUE is the name of the array i.e. FORNT<--1, REAR<--1 and QUEUE [REAR]<--ITEM. ITEM is the element to be added to QUEUE. In the further addition operations, the REAR is incremented by 1 and the ITEM is copied at REAR index. When the REAR=N, then REAR is set equal to 1 and addition is done at REAR index. When the REAR is equal to N and FRONT=1 OR FORNT=REAR+1, QUEUE is said to be full. If any addition is done when the QUEUE is full, ‘overflow’ occurs.
When the element is to be deleted from the QUEUE, the element stored in the QUEUE with FRONT index is deleted by copying it in ITEM and the incrementing FRONT by 1. When FRONT=N then FORNT is set equal to 1. When FRONT is equal to 0, the QUEUE is empty. When the QUEUE is empty and if the deletion operation is done ‘underflow’, occurs.
Example: Consider a QUEUE of size 8. It is initially represented as follows:
In order to implement the Circular QUEUE using one-dimensional array, an array of size N is used with name QUEUE and FRONT and REAR as the indices to represent the deletion end and addition end respectively. Following algorithms are used for the purpose.