Circular Queue

As mentioned earlier, a circular queue is a linear data structure that operates on the FIFO (First-In, First-Out) principle, but with a crucial difference the last position in the queue is conceptually connected back to the first position.

This creates a circular arrangement and design efficiently utilizes the memory by reusing the empty spaces created when elements are dequeued from the front.

Key Concepts

• Front: A pointer (or index) that points to the front element of the queue. When an element is dequeued, the front pointer is moved to the next position.
• Rear: A pointer (or index) that points to the rear (last) element of the queue. When an element is enqueued, the rear pointer is moved to the next available position.
• Size (or Capacity): The maximum number of elements the circular queue can hold.
• Empty State: The queue is empty when the front and rear pointers are at the same position.
• Full State: The queue is full when there is no more space to insert an element. The condition for a full queue needs careful handling to avoid confusion with the empty state. A common approach is to leave one empty space in the array.

Advantages of Circular Queue

• Efficient Memory Utilization: It avoids the wastage of space that occurs in a simple queue implemented with an array. In a simple queue, even if the front of the array has empty slots after dequeue operations, you cannot insert new elements once the rear reaches the end.
• Continuous Flow: Useful in scenarios where data needs to be processed in a continuous loop or where a fixed-size buffer is required for incoming and outgoing data.

Disadvantages of Circular Queue

• Slightly More Complex Implementation: Managing the circular nature of the indices requires careful use of the modulo operator.
• Fixed Size: Typically implemented with a fixed size array, so you need to know the maximum capacity beforehand. Dynamic resizing can be implemented but adds complexity.

Operations of Circular Queue

1. Enqueue (Insert)

This operation adds an element to the rear of the queue.

Algorithm

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

• Check if the queue is full → no space to insert.
• If it’s the first element, set both front and rear to 0.
• If not, advance rear by one position (wrapping around using (rear + 1) % size).
• Place the new value at queue[rear].

2. Dequeue (Remove)

This operation removes an element from the front of the queue.

Algorithm

Dequeue(queue, size, front, rear)
if ( front == -1 ) then
   print "Queue is empty"
else if ( front == rear ) then
   print "Removed element:", queue[front]
   front ← -1
   rear ← -1
else
   print "Removed element:", queue[front]
   front ← (front + 1) mod size
end if

• Check if the queue is empty → nothing to remove.
• If there’s only one element (front == rear), remove it and reset front and rear to -1.
• If not, remove the element at front and advance front by one (wrapping using (front + 1) % size).

3. Peek (Front Element)

This operation returns the element at the front without removing it.

Algorithm

Peek(queue, size, front, rear)
if ( front == -1 ) then
   print "Queue is empty"
else
   print "Front element:", queue[front]
end if

• Check if the queue is empty.
• If not, return queue[front].

4. Display (Show All Elements)

This operation prints all elements currently in the queue.

Algorithm

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

• Check if the queue is empty.
• If not, start at front and move forward (wrapping with % size) until you reach rear.
• Print each element along the way.

5. isEmpty Operation

Checks if the queue has no elements.

Algorithm

isEmpty(front)
if ( front == -1 ) then
   return True
else
   return False
end if

• If front == -1 → queue is empty.
• In our design, when the queue is reset (after last removal), both front and rear are set to -1.

isFull Operation

Checks if the queue has no space left to insert a new element.

isFull(front, rear, size)
if ( (rear + 1) mod size == front ) then
   return True
else
   return False
end if

• If (rear + 1) % size == front → queue is full.
• The next rear position circles back to front, meaning all available spots are filled.

Time and Space Complexity of Circular Queue

Time Complexity

Let’s look at each operation:

All major queue operations except display() run in constant time O(1).

The display() operation can take up to O(n) time, where n is the number of stored elements.

Space Complexity

The total space used is O(SIZE) fixed, because the array size is determined at compile time and does not grow dynamically. There’s no extra space used per operation.

Circular Queue Implementation in C Programming

#include <stdio.h>
#define SIZE 5

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

int isFull() {
    return ( (rear + 1) % SIZE ) == front;
}

int isEmpty() {
    return front == -1;
}

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);
}

void dequeue() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Removed %d\n", queue[front]);
    if (front == rear) {
        front = rear = -1;  // Queue becomes empty
    } else {
        front = (front + 1) % SIZE;
    }
}

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

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");
}

int main() {
    // Test operations
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    display();

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

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

    enqueue(70);  // Should show "Queue is full"
    display();

    peek();
    return 0;
}