## Friday, 25 July 2014

### Queue:

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 :