Circular Queue

A circular queue is a special type of queue that follows the FIFO (First-In, First-Out) principle, but unlike a simple queue, its last position is connected back to the first position.

This creates a circular structure, allowing efficient reuse of memory spaces that become empty after deletion.

Concept of Circular Queue

In a simple (linear) queue, once the rear reaches the end of the array, no more insertions are possible even if there are empty spaces at the front.

A circular queue solves this problem by allowing the rear pointer to wrap around to the beginning using the modulo (%) operation.

Key Components

• Front → Points to the first element (used for deletion)
• Rear → Points to the last element (used for insertion)
• Size (Capacity) → Maximum number of elements

Special Conditions:

• Empty Condition
  Queue is empty when:
  → front == -1
• Full Condition
  Queue is full when:
  → (rear + 1) % size == front

Advantages of Circular Queue

• Efficient Memory Utilization
  Reuses empty spaces created after dequeue operations
• No Space Wastage
  Unlike linear queue, unused slots are reused
• Continuous Processing
  Suitable for systems requiring cyclic data handling

Disadvantages of Circular Queue

• More Complex Logic
  Requires careful handling of circular indexing
• Fixed Size Limitation
  Usually implemented using arrays with fixed capacity

Operations of Circular Queue

1. Enqueue Operation (Insertion)

Adds an element at the rear of the queue.

Algorithm:

if ( (rear + 1) % size == front ) then
    print "Queue is full"
else if ( front == -1 ) then
    front ← rear ← 0
    queue[rear] ← value
else
    rear ← (rear + 1) % size
    queue[rear] ← value
end if

Explanation:

• Check if queue is full
• If first element → initialize front and rear
• Otherwise → move rear circularly and insert element

Example:

• Queue size = 5
• Insert: 10, 20, 30
• Queue: [10, 20, 30, _, _]

2. Dequeue Operation (Deletion)

Removes an element from the front.

Algorithm:

if ( front == -1 ) then
    print "Queue is empty"
else if ( front == rear ) then
    print queue[front]
    front ← rear ← -1
else
    print queue[front]
    front ← (front + 1) % size
end if

Explanation:

• If empty → no deletion
• If single element → reset queue
• Otherwise → move front circularly

Example:

• Queue: [10, 20, 30]
• Remove → 10 removed → [20, 30]

3. Peek Operation

Returns the front element without removing it.

Algorithm:

if ( front == -1 ) then
    print "Queue is empty"
else
    print queue[front]
end if

4. Display Operation

Displays all elements from front to rear.

Algorithm:

if ( front == -1 ) then
    print "Queue is empty"
else
    i ← front
    while true do
        print queue[i]
        if i == rear then
            break
        i ← (i + 1) % size
    end while
end if

Explanation:

• Traverse from front
• Wrap around using modulo
• Stop when rear is reached

5. isEmpty Operation

Checks if queue is empty.

if ( front == -1 ) then
    return TRUE
else
    return FALSE
end if

6. isFull Operation

Checks if queue is full.

if ( (rear + 1) % size == front ) then
    return TRUE
else
    return FALSE
end if

Time and Space Complexity

Time Complexity

Space Complexity

• O(n) → fixed-size array
• Only two extra variables (front, rear) → O(1)

Circular Queue Implementation in C

#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

// Check if queue is full
int isFull() {
    return ((rear + 1) % SIZE == front);
}

// Check if queue is empty
int isEmpty() {
    return front == -1;
}

// Enqueue operation
void enqueue(int value) {
    if (isFull()) {
        printf("Queue is full!\n");
        return;
    }
    if (isEmpty()) {
        front = rear = 0;
    } else {
        rear = (rear + 1) % SIZE;
    }
    queue[rear] = value;
    printf("Inserted %d\n", value);
}

// Dequeue operation
void dequeue() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Removed %d\n", queue[front]);

    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % SIZE;
    }
}

// Peek operation
void peek() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Front element: %d\n", queue[front]);
}

// Display operation
void display() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }

    printf("Queue elements: ");
    int i = front;

    while (1) {
        printf("%d ", queue[i]);
        if (i == rear)
            break;
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

// Main function
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    display();

    dequeue();
    dequeue();
    display();

    enqueue(50);
    enqueue(60);
    display();

    enqueue(70); // Full condition
    display();

    peek();

    return 0;
}

Conclusion

A circular queue is an optimized version of a simple queue that:

• Eliminates memory wastage
• Uses circular indexing
• Maintains efficient O(1) operations

It is widely used in systems that require continuous and cyclic data processing.