Friday, 25 July 2014

Queue Implementation In Array in C

Queue:

queue data structure

A queue is a linear list of element in which
è Deletion can take place at one end that is Front .

è Insertion take place at one end that is Rear ..

That's why Also known as FILO :-first in last out



Property of Queue:

è  Front == NULL (or -1) =>> shows Empty queue
è  Since deletion take place at front so after deletion                  front=front+1
è Similarly on insertion rear=rear+1
è  If rear =N then on insertion rear=1
èIf front=N then on deletion front =1
è  Front=0 and rear =N shows queue is full and no further insertion possible
è If front ==rear !=NULL then queue contain only one element



Algorithm to Insertion in Queue :

Insertion in queue always take place at rear

1:- if front==0 and rear=N or front=rear+1  then    
       Print  overflow and exit .
2:- if Front==NULL
                      set front=0 and rear=0
      else if rear==N
                      set rear=0
      else
                    rear=rear+1
3:- set queue[rear]=item
4:- exit

Algorithm to Deletion from Queue :

Deletion from queue always take place at front .

1:- if front==NULL
               then print underflow condition and exit
2:- set item=queue[front]
3:- if front==rear //i.e only one element in queue
           set front=NULL and rear=NULL
     else if front=N (N=max index of array )
             set front=N
     else
             front=front+1
4:- Exit

Queue implementation in C array :

  1. //Queue Implemented in array
  2. // C-Program
  3. #include<stdio.h>
  4. #include<malloc.h>
  5. #include<stdlib.h>
  6. void insert(int *ar,int *front,int *rear,int N){
  7.             int n;
  8.             printf("Enter number to insert :");
  9.                 scanf("%d",&n);
  10.                
  11.                 if((*front==0 && *rear== N) || *front==*rear+1){
  12.                         printf("overflow condition -> queue is full");
  13.                 }
  14.                 else if(*front==-1){
  15.                         *front=0;
  16.                         *rear=0;
  17.                         *(ar+(*rear))=n;
  18.                 }
  19.                 else if(*rear==&& *front !=0){
  20.                         *rear=0;
  21.                         *(ar+(*rear))=n;
  22.                 }
  23.                 else{
  24.                         *rear=*rear+1;
  25.                         *(ar+(*rear))=n;
  26.                 }
  27. }
  28. int del(int *ar,int *front,int *rear,int N){
  29.         int x;
  30.            if(*front == -1 ){   //queue is empty
  31.                 printf("\nUnderflow cond! -> No element in queue to delete");
  32.            }
  33.            else if(*front==*rear){ //only one element in queue
  34.                     x=*(ar+(*front));
  35.                     *front=-1;
  36.                     *rear=-1;
  37.            }
  38.            else if(*front ==N){
  39.                 x=*(ar+(*front));
  40.                 *front=0;
  41.            }
  42.            else{
  43.                 x=*(ar+(*front));
  44.                 *front=*front+1;
  45.            }
  46.            return x;
  47.            
  48. }
  49. void display(int *ar,int f,int r,int N){
  50.         printf("\n");
  51.         if(f<=r){
  52.                 while(f<=r){
  53.                         printf(" %d ",*(ar+f));
  54.                         f=f+1;
  55.                 }
  56.         }
  57.         else{
  58.                 while(f<=N){
  59.                         printf(" %d ",*(ar+f));
  60.                         f=f+1;
  61.                 }
  62.                 f=0;
  63.                 while(f<=r){
  64.                         printf(" %d ",*(ar+f));
  65.                         f=f+1;
  66.                 }
  67.         }
  68.         printf("\n");
  69. }
  70. main(){
  71.         int maxsi,front=-1,rear=-1;
  72.         int ch,x;
  73.         int *ar;
  74.         printf("Enter Max size of Queue : ");
  75.         scanf("%d",&maxsi);   // max number of element you wanna put in queue
  76.        
  77.         ar=(int*)malloc(sizeof(int)*maxsi); //create array of size maxsi
  78.        
  79.         while(1){
  80.                 printf(" 1 : Insert \n 2 : Delete \n 3 : Exit\n  Enter your choice :");
  81.                 scanf("%d",&ch);
  82.                 switch(ch){
  83.                         case 1:
  84.                                
  85.                                 insert(ar,&front,&rear,maxsi-1);
  86.                                 display(ar,front,rear,maxsi-1);
  87.                                 break;
  88.                         case 2:
  89.                                 x=del(ar,&front,&rear,maxsi-1);
  90.                                 printf("\n%d is deleted from queue",x);
  91.                                 display(ar,front,rear,maxsi-1);
  92.                                 break;
  93.                         case 3:
  94.                                 exit(0);
  95.                                 break;
  96.                         default:
  97.                                 printf("Wrong choice try again ??");
  98.                                 break;
  99.             }
  100.     }
  101. }

OutPUt :


queue implementation in array - C program

No comments:

Post a comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets