Circular Queue
There are two major drawback of a linear queue. They are....
Queue full signal: Even if the queue is having empty space.
Time consuming: Linear time to be spent in shifting the elements to the
beginning of the queue.
For example consider the queue below...
After deleting two elements from the queue...
In above situation, even though there is space available in the queue but you can not use of them to insert new element because 'REAR' is still at last position. ( REAR == MAX - 1 holds true ).
To resolve this problem, we have two solutions...
1 : Shift the elements to
the left so that the empty space can be occupied and utilized efficiently. But
this can be very time-consuming, especially when the queue is quite large.
2 : Use a circular queue. In the circular queue, the
last position is connected back to the first position to make a circle.
What is Circular Queue?
A Circular Queue can be defined as follows...
Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.
Initially REAR = 0 and FRONT = 0 and COUNT = 0
MAX - is maximum number of elemets hold by circular queue
C_QUEUE [ MAX ] - is an array which contain the elemets
Algorithm to insert an element in a Circular Queue
Step 1: IF COUNT == MAX
Write " Circular Queue is full !!! Insertion is not possible !!! "
Go to step EXIT
[ End of IF ]
Step 2: ELSE
C_QUEUE[ REAR ] = ELEMENT
REAR = ( REAR + 1 ) % MAX
COUNT ++
Write "Element is Successfully Inserted !!! "
[ End of ELSE ]
Step 3: EXIT
Algorithm to delet an element from a Circular Queue
Step 1: IF COUNT == 0
Write " Circular Queue is Empty !!! Deletion is not possible !!! "
Go to step EXIT
[ End of IF ]
Step 2: ELSE
Write " Element C_QUEUE[ FRONT ] is Successfully Deleted !!! "
FRONT = ( FRONT + 1 ) % MAX
COUNT --
[ End of ELSE ]
Step 3: EXIT
Algorithm to display the elements of a Circular Queue
Step 1: IF COUNT == 0
Write " Circular Queue is Empty !!! "
Go to step EXIT
[ End of IF ]
Step 2: ELSE
for( I = FRONT ; COUNT != 0 ; COUNT-- )
{
Display " C_QUEUE[ I ] "
I = ( I + 1 ) % MAX
}
[ End of ELSE ]
Step 3: EXIT
Program to implement Circular Queue using Array
0 Comment to "circular queue in data structure "
Post a Comment