Data Structure - [Circular Queue Operations]

♠ Posted by Unknown in , at 10:52

CIRCULAR QUEUE with operations


Let we have an array Q that contains n elements in which Q[1] comes after Q[n] in the array. When this technique is used to construct a queue then the queue is called circular queue. In other word we can say that a queue is called circular when the last element comes just before the first element. 

There is  types of pointer called front and rear is used to assume the front side and rear side of the circular queue. In a circular queue when rear  = n, if we insert an element then this element is assigned to Q[1]. That is instead of increasing rear to n+1, we reset rear to 1. Similarly if front = n and an element of the queue is removed, we reset front to 1 instead of  n + 1. Suppose queue contains only one element that is front=rear not equals to NULL and suppose that the element is removed then the front and rear pointer are now assigned NULL to indicate that the queue is empty.

OPERATIONS AND ALGORITHMS OF CIRCULAR QUEUE:

1. Insert Operation:

                                    Step 1: [Check for the Overflow]
                                          If front = 1 and rear = n
                                          Output “Overflow” and return
                                    Step 2: [Insert element in the queue.]
                                          Else if front = 0
                                          front = 1
                                          rear = 1
                                          Q [rear] = value
                                    Step 3: [Check if the rear at the end of the queue]
                                          Else if rear = n
                                          rear = 1
                                          Q [rear] = value
                                    Step 4: [insert the element]
                                          Else
                                          Rear = rear + 1
                                          Q [rear] = value
                                    Step 5: return

2. Delete Operation:

                                    Step 1:             [Check for underflow]
                                          If front = 0
                                          Output “Underflow” and return
                                    Step 2: [Remove the element]
                                          Value = Q [front]
                                    Step 3: [Check whether the queue is empty or not]
                                          If front = rear
                                          front = 0
                                          rear = 0
                                    Step 4: [Check the front pointer position]
                                          Else if front = n
                                          front = 1
                                          Else
                                          front = front + 1
                                    Step 5: [Return the removed element]
                                          Return [value]

Example:

/*USE OF CIRCULAR QUEUE USING ARRAY.*/

#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
 int ans;
 clrscr();
 do
 {
  printf("1. Enter the New Element.\n");
  printf("2. Remove the Element.\n");
  printf("3. Exit...\n");
  printf("Enter your choice :");
  scanf("%d",&ans);
  switch(ans)
  {
            case 1:
                        insert();
                        break;
            case 2:
                        rem();
                        break;
            case 3:
                        break;
            default:
                        printf("You have entered wronge choice....");
  }
  }while(ans != 3);
 getch();
 return;
}

insert()
{
 int newitem;

 if(rear >= SIZE)
            rear = 1;
 else
            rear++;

 if(rear == front)
 {
  printf("Your QUEUE is FULL.\n");
  rear--;
  if(rear==0)
            rear=SIZE;
  return;
 }

 else
 {
  printf("Enter New Element :");
  scanf("%d",&newitem);
  arr[rear]=newitem;
  if(front==0)
            front=1;
 }
 getch();
 return;
}
rem()
{
 int remitem;
 if(front < 1)
 {
  printf("Your QUEUE is EMPTY...\n");
  return;
 }

 if(front>SIZE)
            front=1;

  remitem = arr[front];
  printf("The Removed Item is : %d.\n",remitem);
  if(front==rear)
  {
   front=0;
   rear=0;
   return;
  }
  else
            front++;
 getch();
 return;
}



0 comments:

Post a Comment