For this assignment, you will write a multi-file C program to create and use a d

Question

For this assignment, you will write a multi-file C program to create and use a dynamic (array based) queueof float values.

A queue is a container that can be defined in terms of an array where all adds are preformed at the end of the sequence of existing values, and all removes are preformed at the start of the sequence of existing values. An empty queue is one that has no existing values in the array at all. We use the notion of a tail of the queue to keep track of (at which index) a new value in the sequence is to be added. Hence, an empty queue is one in which tail = 0 and a full queue is one in which tail = capacity - 1

The difference with a dynamic queue is that adds “never” fail. After an add (que), if the queue is full you create a new array with twice the capacity of the current array, copy all the existing items to the new array, free the memory of the “old” array, and set the queue pointer to the “new” array. Similarly, after a remove (deque) from (a non-empty queue), if the queue is less than half full, then you “shrink” the array in half.

Requirements:

You must write queue.h and queue.c which declares and defines functions to:

Create an empty queue with an initial capacity of one.

Add (que) an item to the queue

Test to see if the queue is full – at capacity

Grow the capacity of the queue to twice its current capacity

Test to see if the queue is empty

Remove / return (deque) an item from the queue

Test to see if the queue is less than half full

Shrink the capacity of the queue in half its current capacity

You must write main.c which tests your queue implementation completely

You must write an appropriate Makefile

Notes:

A queue is really three separate data items: a pointer to the array, a tail indicator, and a capacity.

The current size (number of items in the queue) can be deduced from the tail indicator

Explanation / Answer

queue.h

#ifndef _queue_H_
#define _queue_H_
int size;//to store size of the queue
int head;//to point the head of the queue
int tail;//to point the tail of the quue
float *queue;//to point the queue array...which stores floates..
void enqueue(float n);//adding to queue...
float dequeue();//returns float..which is removed from queue
void grow_queue();//method to grow the size of queue..by twice its current size...
int check_full();//checks whether queue if full or not;
int check_half();//check whether elements...are less than half of the size
int check_empty();//checks whether queue is empty or not...
void shrink_queue();//shrinks queue by half..
#endif

queue.c

#include<stdio.h>
#include<stdlib.h>
#include<C:UsersSuryaDocumentsqueue.h>//including header file..
int size=1;//setting initial capacity to 1
int head = -1;//
int tail = -1;//means queue is empty..
float a[1];//creating queue with size 1
float *queue =a;//pointing to queue..

int check_empty()//checks whether queue is empty or not...
{
   if(tail-head==0)
   {
       return 1;//queue is empty
       }
       return 0;;//means queue is not empty
  
}
int check_half()//check whether elements...are less than half of the size
{
   if(tail-head<size/2)
   {
       return 1;//if less than the half      
   }
   return 0;//if not less than half
}
int check_full()//checks whether queue if full or not;
{
   if(tail-head == size)
   {
       return 1;//queue is full  
   }  
   return 0;//queue is not full
}

void grow_queue()//method to grow the size of queue..by twice its current size...
{
  
   int n=size*2;
   float *b = (float *)malloc(n*sizeof(float));
   //float b[size*2];//new array with twice the current size..
   size = size*2;//increasing size
   int i= head;
   while(i<tail)//copying elements to new array
   {
       b[i]=*(queue+i);
       i++;
   }
   queue = b;
}

void shrink_queue()//shrinks queue by half..
{
   int n=size/2;
   float *b = (float *)malloc(n*sizeof(float));
   //float b[n];//new array with half the current size..
   size = size/2;//increasing size
   int i= head,j=0;
   while(i<tail)//copying elements to new array
   {
       b[j]=*(queue+i);
       j++;i++;
   }
   queue = b;
   //updating head and tail,,,
   head = 0;
   tail = j;
  
}
void enqueue(float n)//adding to queue...
{
   if(check_empty()==1)
   {
       head=0;
       tail =1;
       *(queue+head)=n;//adding element to queue
   }
   else if(check_full()==1)
   {
       printf("queue size is full Growing queue ");
       grow_queue();
       *(queue+tail)=n;   //adding element to queue
       tail++;//increasing tail
   }
   else
   {
       *(queue+tail)=n;   //adding element to queue
       tail++;//increasing tail  
   }
   printf("Element added to queue ");
}

float dequeue()//returns float..which is removed from queue
{
   float n;
   if(check_empty()==1)
   {
       return -1;//if queue is empty...
   }
   else
   {
       n=*(queue+tail-1);
       tail--;
      
       if(check_half()==1)//to shrink array
       {
           printf("Total elements are less than half Shrinking queue ");
           shrink_queue();
       }  
   }
   return n;
  
  
}

int main()//testing method..
{
  
   int c=0;
   float n;
   while(c!=3)
   {
      
       printf("1:Enqueue 2:Dequeue 3:Exit Enter ur choice:");
       scanf("%d",&c);
       if(c==1)
       {
           printf("Enter a float :");
           scanf("%f",&n);
           enqueue(n);
          
       }
       else if(c==2)
       {
           printf("Element dequeued :%f ",dequeue());
       }
       else if(c==3)
       {
           break;//breaking loop  
       }
       else
       {
           printf("Enter again:");  
       }
          
   }
  
   return 0;
}

output:

1:Enqueue
2:Dequeue
3:Exit
Enter ur choice:1
Enter a float :2
Element added to queue
1:Enqueue
2:Dequeue
3:Exit
Enter ur choice:1
Enter a float :3
queue size is full
Growing queue
Element added to queue
1:Enqueue
2:Dequeue
3:Exit
Enter ur choice:2
Element dequeued :3.000000
1:Enqueue
2:Dequeue
3:Exit
Enter ur choice:2
Total elements are less than half
Shrinking queue
Element dequeued :2.000000
1:Enqueue
2:Dequeue
3:Exit
Enter ur choice:3

Process exited normally.
Press any key to continue . . .

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.