Mumbai University > COMPS > Sem 3 > Data Structures

Marks: 10 M

Year: May 2014, Dec 2013, May 2015

• A circular queue is implemented in the same way as the linear queue. Except for the fact that the first index comes right after the last index.
• Consider the queue below

• As in the current situation, the queue is currently completely full as the as now empty space is left at the BACK of the queue.

• Now if we delete to values successively from the queue, as the queue follows FIFO policy, the locations 0 and 1 would be left empty.

• Over here new value cannot be added to the queue even if two spaces are left empty in the queue as the new FRONT value is 2 and BACK=9. The overflow condition still stands valid because of the condition BACK=MAX-1. This is one of the major drawbacks of linear queue.

• To overcome this we have the concept of having Circular queues. In circular queue, the first index comes right after the last index.

  #include<stdio.h>
  #include<conio.h>
  void insert_element()
  {
  int num;
  printf("\n enter the number to be inserted in the queue");
  scanf("%d", &num);
  if (front == 0 && back == MAX - 1)
      printf ("overflow");
  else if (front == -1 && back == -1)
  {
      front = back = 0;
      queue[back] = num;
  }
  else if (back == MAX - 1 && front != 0)
  {
      back = 0;
      queue[back] = num;
  }
  else
  {
      back++;
  
  queue [back] = num;
  }
  }
  int delete_element()
  {
  int val;
  if (front == -1 && back == -1)
  {
      printf("underflow");
      return -1;
  }
  val = queue[front];
  if (front == back)
      front = back - 1;
  else
  {
      if (front == MAX - 1)
          front = 0;
      else
          front++;
  }
  printf("the value deleted is %d",val);
  }
  void display_queue
  {
  int i;
  printf("\n");
  if (front == -1 && back == -1)
      printf("queue is empty");
  else
  {
      if (front < back)
      {
          for (i = front;i < back;i++)
              printf("\t %d", queue[i]);
      }
      else
      {
          for (i = front;i < MAX;i++)
              printf("\t %d", queue[i]);
          for (i = 0;i <= back;i++)
              printf("\t %d", queue[i]);
      }
  }
  }
  int main()
  {
  int choice;
  do{
  printf("\n 1. insert element");
  printf("\n 2. delete element");
  printf("\n 3. display queue");
  switch(choice)
  {
      case 1:
      insert_element();
      breakl
      case 2:
      delete_element();
      break;
      case 3:
      display_queue();
      break;
  }
  return 0;
  }