Queue Implementation In Array in C

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

---

OutPUt :