Pages

Wednesday 5 February 2020

Circular Queue implementation using Array

CIRCULAR QUEUE
As in a circle after last element , first element occurs.
Here after (n-1)th element, 0th element occurs. Similarly we take assumptions that after last element of queue the 1st element will occur.
Eg:
(a)Initial queue


  5

 10

 15
      0       1          2       3
Front=1; rear=3;

(b) Deletion in queue



 10

 15
    0        1           2          3
Front=2; rear=3;

(c) Addition in queue

 20



 10

 15
  0           1            2       3
Front=2; rear=0;

(d) Addition in queue

 20

 25

 10

 15
  0             1        2            3
Front=2; rear=1;
[overflow condition]

(e) Deletion in queue

 20

 25


 15
  0             1        2           3
Front=3; rear=1;

(f) Deletion in queue

  20

  25


  0               1         2        3
Front=0; rear=1;

(g) Deletion in queue



  25


       0        1         2           3
Front=1; rear=1;

(h) Deletion in queue





   0         1         2         3
Front=-1; rear=-1;
[underflow condition]

ALGORITHM FOR ADDITION OPERATION IN CIRCULAR QUEUE: 

STEP-1: If ((front==0 && rear==n-1)||(front==rear+1))
             print queue overflow otherwise go to step-2.

STEP-2: If (front==-1) then front=0; rear=0 otherwise go to step-3.

STEP-3: If (rear==n-1) then rear=0

STEP-4: rear++;

STEP-5: read the item to be deleted.

STEP-6: cq(rear)=item

STEP-7: return rear.

DELETE OPERATION:

STEP-1: If (front==-1 && rear==-1) 
             print queue underflow and return front.

STEP-2: read the item to be deleted then cq[front]=’\0’.

STEP-3: If (front==rear) then front=-1,rear=-1.

STEP-4: If (front==n-1) then front=0 otherwise go to step-4.

STEP-5: front++ and return front.

DISPLAY OPERATION:

STEP-1:  If((front==-1 && rear==-1)||(front>rear)). 
              print queue is empty otherwise go to step-2.

STEP-2: print queue elements are from i=0 to n.

STEP-3: print position of front and rear.



/* circular queue implementation using array */
import java.util.Scanner;
class rkcirqueue
{
  static int[] a;
  static int i,n,item,front=-1,rear=-1,ch;
  static Scanner cq=new Scanner(System.in);
  public static void main(String[] args)
  {
   System.out.printf("\nEnter the length of the circular queue :\n");
   n=cq.nextInt();
   a=new int[n];
   while(true)
   {
    System.out.printf("\n    MENU \n\n");
    System.out.printf("  1.Add   \n");
    System.out.printf("  2.Delete   \n");
    System.out.printf("  3.Display   \n");
    System.out.printf("  4.Quit      \n");
System.out.printf("Enter u r choice: ");
    ch=cq.nextInt();
    switch(ch)
    {
       case 1:add();break;
       case 2:del();break;
       case 3:display();break;
       case 4:System.exit(1);break;
       default:
    System.out.printf("u have entered wrong choice");break;
    }
   System.out.printf("\n");
  }
}

static int add()
   {
    if((front==0 && rear==n-1)||(front==rear + 1))
     {
     System.out.printf("\n circular queue is overflow ");
     return rear;
     }
if(front==-1)
     {
       front=0;
       rear=0;
     }
     else
{
  if(rear==n-1)
            rear=0;
         else
            rear++;
}
  System.out.printf("\n enter item to be added on to the circular queue:");
      item=cq.nextInt();
      a[rear]=item;
      return rear;
   }
 
 static int del()
 {
    if(front==-1 && rear==-1)
     {
     System.out.printf("\n circular queue is underflow ");
     return rear;
     }
    System.out.printf("\n The deleted item = %d ",a[front]);
    a[front]='\0';
      if(front==rear)
      {
      front=-1;
      rear=-1;
      }
      else
      {
if(front==n-1)
           front=0;
        else
           front++;
      }
    return front;
 }

static int display()
   {
   if(front==-1 && rear==-1)
    {
    System.out.printf("\n circular queue is empty");
    return rear;
    }
    System.out.printf("\ncircular queue elements are:");
    for(i=0;i<=n-1;i++)
{
if(a[i]==0)
         System.out.printf("\t");
                 else
System.out.printf("\t%d",a[i]);
}
   System.out.printf("\n Position of Front=%d and Rear=%d",front,rear);
   return rear;
   }
}

No comments:

Post a Comment

Constructors & Destructors in c++

  Constructors :  A Constructor is a special member function, which is used to initialize the objects of its class. The Constructor is invok...