## Circular Queue

### 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.

### Circular Queue

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.

Subscribe
Notify of
1 Comment
Inline Feedbacks