Page 522 - Computer science 868 Class 12
P. 522
76 case 5:
77 ob.display();
78 break;
79 default:
80 System.out.println(" Exit");
81 }
82 }while(ch>=1 && ch<=5);
83 }
84 }
13.2.5 Circular Queue
Circular queue is a special type of queue where the front and rear ends are connected to form a circular structure.
Circular queue follows the queue principle of FIFO that is First In First Out.
Like Queue, an element is inserted from the front end and deleted from rear end. But as a circular structure does not
have a definite front and rear, the drawback of unutilised front space is taken care of in a circular queue.
Like a linear queue, two operations can be performed on a circular queue. They are as follows:
1. Enqueue: Inserting an element in a circular queue is done from the rear end. But the rear pointer changes by rear
= (rear+1) % sizeOfCircularQueue.
2. Dequeue: Deleting an element from a circular queue is done from the front end. But the front index pointer changes
by front = (front+1) % sizeOfCircularQueue.
Generally, in Circular Queue one cell is kept vacant as a demarcation between front and rear.
Let us see diagrammatically how a circular queue works. Let us assume that the following the circular queue can store
maximum 4 elements.
rear=3
front=0
3 0 rear=0 3 17 Insert 17 3 17 0 Insert 23 3 17 Insert 29 3 17 Insert 35
front=0
front=0
front=0
front=0
2 2 0 2 1 2 29 0 2 29 0 rear=0
1 1 rear=2 23 23 1 23 1 Queue=full
rear=1
front=3 Delete Delete
3 Delete 3 Delete 3 0 rear=0 3 0 Queue empty
2 0 rear=0 2 0 rear=0 2 2
29 1 29 1
23 1 1
front=1 front=2
The algorithm to insert an element in a circular queue is given below.
void enqueue(int qu[] , int max , int val)
Step 1: Start.
Step 2: Initialise front and rear to 0
Step 3: If (rear +1)% max =front then display “Queue Overflow”, go to Step 8
Step 4: Assign qu[rear]= val
Step 5: Assign rear=(rear+1)%max
520520 Touchpad Computer Science-XII

