For this assignment, you will write a multi-file C program to create and use a d
ID: 3872264 • Letter: F
Question
For this assignment, you will write a multi-file C program to create and use a dynamic (array based) queue of 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
#include<stdio.h>
#include<stdlib.h>
#include<float.h>
typedef struct
{
int front, rear;
int capacity;
float *arr;
}Queue;
void enqueue(Queue *, float);
float dequeue(Queue *);
void initialize(Queue *);
#endif
queue.c
#ifndef _QUEUE_C_
#define _QUEUE_C_
#include<stdio.h>
#include<stdlib.h>
#include<float.h>
#include"queue.h"
void enqueue(Queue *q, float item)
{
if(q->rear != q->capacity - 1)
{
q->arr[q->rear = q->rear + 1] = item;
return;
}
float *b = NULL;
b = (float *)malloc(2 * q->capacity * sizeof(float));
if(b == NULL)
{
fprintf(stderr, "%s", " Dynamic memory allocation failed ");
exit(-1);
}
int i, j = 0;
for(i = q->front + 1; i <= q->rear; i = (i + 1))
{
//printf("%f", q->arr[i]);
b[++j] = q->arr[i];
}
b[++j] = item;
free(q->arr), q->arr = NULL;
q->front = -1, q->rear = j, q->capacity *= 2;
q->arr = b;
return;
}
void initialize(Queue *q)
{
q->front = -1, q->rear = -1;
q->capacity = 1;
q->arr = NULL;
q->arr = (float *)malloc(q->capacity * sizeof(float));
if(q->arr == NULL)
{
fprintf(stderr, "%s", " Dynamic memory allocation failed ");
exit(-2);
}
}
float dequeue(Queue *q)
{
if(q->front == q->rear)
{
fprintf(stderr, "%s", " Queue Empty ");
return FLT_MIN;
}
q->front = (q->front + 1);
float p = q->arr[q->front];
if(q->capacity == 1)
{
//printf(" %f deleted from queue ", p);
return p;
}
int i, j = 0;
for(i = (q->front + 1); i <= q->rear; i = (i + 1))
j++;
if(j >= (q->capacity / 2))
{
//printf(" %f deleted from queue ", p);
return p;
}
float *b = NULL;
b = (float *)malloc((q->capacity / 2) * sizeof(float));
if(b == NULL)
{
fprintf(stderr, "%s", " Dynamic memory allocation failed ");
exit(-1);
}
i, j = 0;
for(i = (q->front + 1); i <= q->rear; i = (i + 1))
{
b[++j] = q->arr[i];
}
free(q->arr), q->arr = NULL;
q->front = -1, q->rear = j, q->capacity /= 2;
q->arr = b;
//printf(" %f deleted from queue ", p);
return p;
}
#endif
main.c
#include<stdio.h>
#include<stdlib.h>
#include"queue.h"
int main()
{
int choice = 3;
float item;
Queue q;
initialize(&q);
do
{
printf(" 1. Enqueue 2. Dequeue 3. Exit Choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
{
printf(" Item : "), scanf("%f", &item);
enqueue(&q, item);
}
break;
case 2:
dequeue(&q);
break;
case 3: break;
default: printf(" Invalid choice ");
}
}while(choice != 3);
return 0;
}
makefile
queue: main.c queue.c
cc -o queue main.c queue.c
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.