Circular Queue

In this page

Limitation of Linear Queue

Look at the following queue.

You cannot insert a new value now, because the queue is completely full. Consider the following case: two consecutive deletions are made.

Even though there is enough space to hold a new element, the overflow condition still occurs since the condition rear = MAX – 1 is still valid. This non-usable empty space is a major drawback of a linear queue. A solution to this problem is to make the queue circular.

A circular queue is a special type of queue where the last element is connected back to the first element thus forming a circle. In the circular queue, the first index comes right after the last index.

We start insertion from the beginning of the queue if we reach the end of the queue.

Circular Queue Operations

Every queue includes two pointers, FRONT and REAR, which indicate the position where deletion and insertion can be performed. Initially, values of FRONT and REAR is set to -1.

The circular queue is full if any of the following condition is met,

FRONT = 0 and REAR = Max – 1
FRONT = REAR + 1

Enqueue Operation

Inserting a new element in the position pointed by REAR is called the enqueue operation.

Print overflow and exit if the queue is full.
For adding first element make FRONT = 0.
Increment REAR by 1.
Insert new element in the position pointed by REAR.

Algorithm: Enqueue

Step 1: IF FRONT = and Rear = MAX-1
            Write OVERFLOW
            Goto step 4
        [End OF IF]
Step 2: IF FRONT=-1 and REAR=-1
            SET FRONT = REAR = 0
        ELSE IF REAR = MAX-1 and FRONT != 0
            SET REAR = 0
        ELSE
            SET REAR = REAR + 1
        [END OF IF]
Step 3: SET QUEUE[REAR] = ITEM
Step 4: EXIT

Dequeue Operation

Deleting an element in the position pointed by FRONT is called the dequeue operation. We must check if the queue is empty before deletion.

Print underflow and exit if the queue is empty.
Return the value pointed by FRONT.
Increment FRONT by 1 circularly.
Set FRONT = REAR = -1 for the last element.

Algorithm: Dequeue

Step 1: IF FRONT = -1
            Write UNDERFLOW
            Goto Step 4
        [END of IF]
Step 2: SET VAL = QUEUE[FRONT]
Step 3: IF FRONT = REAR
            SET FRONT = REAR = -1
        ELSE
            IF FRONT = MAX -1
                SET FRONT = 0
            ELSE
                SET FRONT = FRONT + 1
            [END of IF]
        [END OF IF]
Step 4: EXIT

Enqueue and dequeue operations on a circular queue is illustrated below.