Advantage, Working, Operations of Circular Queue

What is the advantage of circular queue over ordinary queue? Write a C program to simulate the working of circular queue of integers using array. Provide the following operations: Insert, Delete, Display

Circular Queue

• “The queue which wrap around the end of the array is called Circular Queue.” The array positions are arranged in a circle as shown in figure.
• In this convention the variable front is changed. front variable points one position counterclockwise from the location of the front element in the queue. The convention for rear is unchanged.

Implementation of Circular Queue Operations

• When the array is viewed as a circle, each array position has a next and a previous position.
• The position next to MAX-QUEUE-SIZE -1 is 0, and the position that precedes 0 is MAX – QUEUE-SIZE -1.
• When the queue rear is at MAX_QUEUE_SIZE-1, the next element is inserted at position0.
• In circular queue, the variables front and rear are moved from their current position to the next position in clockwise direction.

This may be done using code

if (rear = = MAX_QUEUE_SIZE-1)
  rear = 0;
else 
  rear++;

Addition & Deletion in Circular Queue

• To add an element, increment rear one position clockwise and insert at the new position. Here the MAX_QUEUE_SIZE is 8 and if all 8 elements are added into queue and that can be represented in below figure (a).
• To delete an element, increment front one position clockwise. The element A is deleted from queue and if we perform 6 deletions from the queue of Figure (b) in this fashion, then queue becomes empty and that front=rear.
• If the element I is added into the queue as in figure (c), then rear needs to increment by 1 and the value of rear is 8. Since queue is circular, the next position should be 0 instead of 8.

This can be done by using the modulus operator, which computes remainders.

(rear +1) % MAX_QUEUE_SIZE

Advantages of Circular Queue

• Doesn’t use dynamic memory → No memory leaks
• Conserves memory as we only store up to our capacity (opposed to a queue which could continue to grow if input outpaces output.)
• Simple Implementation → easy to trust and test
• Never has to reorganize / copy data around
• All operations occur in constant time O(1)

Write a C program to simulate the working of circular queue of integers using array. Provide the following operations: Insert, Delete, Display

#include<stdio.h>

# define MAX 5
int cqueue_arr[MAX];
int front = -1;
int rear = -1;
void insert(int item) {
  if ((front == 0 && rear == MAX - 1) || (front == rear + 1)) {
    printf("Queue Overflow \n\n");
    return;
  }
  if (front == -1) {
    front = 0;
    rear = 0;
  } else {
    if (rear == MAX - 1)
      rear = 0;
    else
      rear = rear + 1;
  }
  cqueue_arr[rear] = item;
}
void deletion() {
  if (front == -1) {
    printf("Queue Underflown\n\n");
    return;
  }
  printf("Element deleted from queue is : %d\n\n", cqueue_arr[front]);
  if (front == rear) {
    front = -1;
    rear = -1;
  } else {
    if (front == MAX - 1)
      front = 0;
    else
      front = front + 1;
  }
}
void display() {
  int front_pos = front, rear_pos = rear;
  if (front == -1) {
    printf("Queue is empty\n\n");
    return;
  }
  printf("Queue elements : \n");
  if (front_pos <= rear_pos)
    while (front_pos <= rear_pos) {
      printf("%d ", cqueue_arr[front_pos]);
      front_pos++;
    }
  else {
    while (front_pos <= MAX - 1) {
      printf("%d ", cqueue_arr[front_pos]);
      front_pos++;
    }
    front_pos = 0;
    while (front_pos <= rear_pos) {
      printf("%d ", cqueue_arr[front_pos]);
      front_pos++;
    }
  }
  printf("\n\n");
}
int main() {
  int choice, item;
  do {
    printf("1.Insert \n2.Delete \n3.Display \nEnter your Choice :: ");
    
    scanf("%d", &choice);
    switch (choice) {
    case 1:
      printf("Input the element for insertion in queue : ");
      scanf("%d", &item);
      insert(item);
      break;
    case 2:
      deletion();
      break;
    case 3:
      display();
      break;
    case 4:
      break;
    default:
      printf("Wrong choicen\n\n");
    }
  } while (choice != 4);
  return 0;
}