A circular queue uses the same conventions as
that of linear queue. Using Front will always point one position
counterclockwise from the first element in the queue. In order to add an
element, it will be necessary to move rear one position clockwise. Similarly, it
will be necessary to move front one position clockwise each time a deletion is
made. Nevertheless, the algorithms for create (), Isfull (), Isempty (), Front
() and Rear () are same as that of linear queue.
The enqueue Operation on a Circular Queue
There are three scenarios which need to be considered, assuming that the queue
is not full:
- If the queue is empty, then the value of the front and the rear variable will be -1 (i.e., the sentinel value), then both front and rear are set to 0.
- If the queue is not empty, then the value of the rear will be the index of the last element of the queue, then the rear variable is incremented.
- If the queue is not full and the value of the rear variable is equal to capacity -1 then rear is set to 0.
The algorithms for other
functions are:
Algorithm: Insertion
Input: (1) CQ, Circular Queue; (2) e, element to be
inserted; (3) SIZE, size of the Circular Queue;
(4) F, the
front pointer; (5) R, the rear pointer
Output: (1) CQ, updated; (2) F, updated; (3) R, updated
Method:
If (Isfull (CQ)) then
Print ('overflow')
Else
R=R mod SIZE + 1;
CQ[R] =e
If (Isempty (CQ))
F=1;
If end
If end
Algorithm ends
Algorithm: Deletion
Input: (1) CQ, Circular Queue; (2) SIZE, size of the CQ; (3)
F, the front pointer; (4) R, the rear pointer
Output: (1) CQ, updated; (2) F, updated; (3) R, updated; (4)
e, element if deleted;
Method:
If (Isempty (CQ)) then
Print ('Queue is empty')
Else
e = CQ[F]
If (F==R)
F=R=0;
Else
F=F mod SIZE +1;
If end
If end
Algorithm ends