Circular queue

Definition

A circular queue is a queue in which the last position is connected to the first position, and the insertion and deletion operations are performed in a circular manner using modulo arithmetic to reuse freed spaces efficiently.

In simpler words, it is a queue where:

• elements are inserted at the rear,
• elements are removed from the front,
• and when the rear reaches the end of the array, it can move back to the beginning if there is space available.

This makes circular queues more efficient than linear queues when using arrays.

Main Content

1. Circular Queue Structure

• A circular queue is usually implemented using an array of fixed size, along with two pointers or indices:
• front: points to the first element
• rear: points to the last element
• The circular behavior is achieved using the formula:

index = (index + 1) % size

This modulo operation makes the index return to 0 after reaching the last position.

• Example: If the queue size is 5 and the rear is at index 4, then the next position becomes:

(4 + 1) % 5 = 0

So insertion can continue from the beginning if space is available.

2. Circular Queue Conditions

• A circular queue has two important states:
• Overflow / Full condition: the queue cannot accept more elements.
• Underflow / Empty condition: the queue has no elements to delete.
• A common full condition in array-based circular queue is:

(rear + 1) % size == front

This means the next rear position is the same as the front, so the queue is full.

• A common empty condition is:
• front == -1 initially, or
• front > rear in some implementations, depending on how the logic is written.
• These conditions are important because they prevent invalid insertions and deletions.

3. Operations in Circular Queue

• The main operations are:
• Enqueue: insert an element at the rear
• Dequeue: remove an element from the front
• Peek / Front: view the front element without removing it
• IsEmpty / IsFull: check whether the queue is empty or full
• During enqueue, the rear moves forward circularly.
• During dequeue, the front moves forward circularly.
• The queue remains efficient because deleted positions are reused, unlike a simple linear queue where unused spaces may remain wasted.

Example Representation

Suppose the queue size is 5.

After inserting 10, 20, 30:

front -> [10, 20, 30, _, _] <- rear

After deleting 10 and 20:

front -> [_, _, 30, _, _] <- rear

Now inserting 40 and 50:

front -> [_, _, 30, 40, 50] <- rear

Now if 30 is deleted and 60 is inserted, 60 can wrap around to the empty slot at the beginning:

front -> [60, _, _, 40, 50] <- rear

This is the main advantage of the circular design.

Working / Process

1. Initialize the queue

• Set front and rear to indicate that the queue is empty, commonly -1.
• Create an array of fixed size to store the elements.

2. Insert elements using enqueue

• Check whether the queue is full.
• If it is not full, move rear forward using modulo arithmetic.
• If this is the first insertion, set both front and rear to 0.
• Place the new element at the rear position.

3. Remove elements using dequeue

• Check whether the queue is empty.
• Remove the element from the front.
• If the queue becomes empty after deletion, reset both front and rear to -1.
• Otherwise, move front forward using modulo arithmetic.

4. Wrap around when needed

• If the rear reaches the last index, the next insertion may go to index 0 if there is free space.
• This circular movement ensures maximum use of all available array positions.

5. Check queue state

• Use IsEmpty to know whether deletion is possible.
• Use IsFull to know whether insertion is possible.
• These checks are essential to avoid errors and maintain correct behavior.

Simple Process Example

For queue size 4:

• Start: front = -1, rear = -1
• Enqueue 5: front = 0, rear = 0
• Enqueue 10: rear = 1
• Enqueue 15: rear = 2
• Dequeue: remove 5, front = 1
• Enqueue 20: rear = 3
• Dequeue: remove 10, front = 2
• Enqueue 25: rear = (3 + 1) % 4 = 0

Now the rear wraps to the beginning, showing circular behavior.

Advantages / Applications

Efficient memory utilization

• : free spaces created by deletions are reused, so no array space is wasted.

Faster and practical queue management

• : insertion and deletion remain efficient with simple index movement.

Useful in real-world systems

• : circular queues are used in CPU scheduling, printer spooling, buffering, traffic systems, and streaming applications.

Summary

• A circular queue is a FIFO queue that reuses array space by wrapping around.
• It uses front and rear indices with modulo arithmetic for efficient movement.
• It helps avoid the space wastage problem of a simple linear queue.

Important terms to remember: FIFO, front, rear, enqueue, dequeue, full condition, empty condition, modulo arithmetic