Question

Please complete the following functions in "queue.c" using C. This must use the dynamic array provided in "dynarray.c"

--------------------------------------------------------------------------------------------

//queue.c

#include <stdlib.h>

#include "queue.h"
#include "dynarray.h"

/*
* This is the structure that will be used to represent a queue. This
* structure specifically contains a single field representing a dynamic array
* that should be used as the underlying data storage for the queue.
*
* You should not modify this structure.
*/
struct queue {
struct dynarray* array;
};

/*
* This function should allocate and initialize a new, empty queue and return
* a pointer to it.
*/
struct queue* queue_create() {
return NULL;
}

/*
* This function should free the memory associated with a queue. While this
* function should up all memory used in the queue itself, it should not free
* any memory allocated to the pointer values stored in the queue. This is the
* responsibility of the caller.
*
* Params:
* queue - the queue to be destroyed. May not be NULL.
*/
void queue_free(struct queue* queue) {
return;
}

/*
* This function should indicate whether a given queue is currently empty.
* Specifically, it should return 1 if the specified queue is empty (i.e.
* contains no elements) and 0 otherwise.
*
* Params:
* queue - the queue whose emptiness is being questioned. May not be NULL.
*/
int queue_isempty(struct queue* queue) {
return 1;
}

/*
* This function should enqueue a new value into a given queue. The value to
* be enqueued is specified as a void pointer. This function must have O(1)
* average runtime complexity.
*
* Params:
* queue - the queue into which a value is to be enqueued. May not be NULL.
* val - the value to be enqueued. Note that this parameter has type void*,
* which means that a pointer of any type can be passed.
*/
void queue_enqueue(struct queue* queue, void* val) {
return;
}

/*
* This function should return the value stored at the front of a given queue
* *without* removing that value. This function must have O(1) average runtime
* complexity.
*
* Params:
* queue - the queue from which to query the front value. May not be NULL.
*/
void* queue_front(struct queue* queue) {
return NULL;
}

/*
* This function should dequeue a value from a given queue and return the
* dequeued value. This function must have O(1) average runtime complexity.
*
* Params:
* queue - the queue from which a value is to be dequeued. May not be NULL.
*
* Return:
* This function should return the value that was dequeued.
*/
void* queue_dequeue(struct queue* queue) {
return NULL;
}

------------------------------------------------

// dynarray.c

#include <stdlib.h>
#include <assert.h>

#include "dynarray.h"

/*
* This structure is used to represent a single dynamic array.
*/
struct dynarray {
void** data;
int size;
int capacity;
};

#define DYNARRAY_INIT_CAPACITY 4

/*
* This function allocates and initializes a new, empty dynamic array and
* returns a pointer to it.
*/
struct dynarray* dynarray_create() {
struct dynarray* da = malloc(sizeof(struct dynarray));
assert(da);

da->data = malloc(DYNARRAY_INIT_CAPACITY * sizeof(void*));
assert(da->data);
da->size = 0;
da->capacity = DYNARRAY_INIT_CAPACITY;

return da;
}

/*
* This function frees the memory associated with a dynamic array. Freeing
* any memory associated with values stored in the array is the responsibility
* of the caller.
*
* Params:
* da - the dynamic array to be destroyed. May not be NULL.
*/
void dynarray_free(struct dynarray* da) {
assert(da);
free(da->data);
free(da);
}

/*
* This function returns the size of a given dynamic array (i.e. the number of
* elements stored in it, not the capacity).
*/
int dynarray_size(struct dynarray* da) {
assert(da);
return da->size;
}

/*
* Auxilliary function to perform a resize on a dynamic array's underlying
* storage array.
*/
void _dynarray_resize(struct dynarray* da, int new_capacity) {
assert(new_capacity > da->size);

/*
* Allocate space for the new array.
*/
void** new_data = malloc(new_capacity * sizeof(void*));
assert(new_data);

/*
* Copy data from the old array to the new one.
*/
for (int i = 0; i < da->size; i++) {
new_data[i] = da->data[i];
}

/*
* Put the new array into the dynarray struct.
*/
free(da->data);
da->data = new_data;
da->capacity = new_capacity;
}

/*
* This function inserts a new value to a given dynamic array. The new element
* is always inserted at the *end* of the array.
*
* Params:
* da - the dynamic array into which to insert an element. May not be NULL.
* val - the value to be inserted. Note that this parameter has type void*,
* which means that a pointer of any type can be passed.
*/
void dynarray_insert(struct dynarray* da, void* val) {
assert(da);

/*
* Make sure we have enough space for the new element. Resize if needed.
*/
if (da->size == da->capacity) {
_dynarray_resize(da, 2 * da->capacity);
}

/*
* Put the new element at the end of the array.
*/
da->data[da->size] = val;
da->size++;
}

/*
* This function removes an element at a specified index from a dynamic array.
* All existing elements following the specified index are moved forward to
* fill in the gap left by the removed element.
*
* Params:
* da - the dynamic array from which to remove an element. May not be NULL.
* idx - the index of the element to be removed. The value of `idx` must be
* between 0 (inclusive) and n (exclusive), where n is the number of
* elements stored in the array.
*/
void dynarray_remove(struct dynarray* da, int idx) {
assert(da);
assert(idx < da->size && idx >= 0);

/*
* Move all elements behind the one being removed forward one index,
* overwriting the element to be removed in the process.
*/
for (int i = idx; i < da->size - 1; i++) {
da->data[i] = da->data[i+1];
}

da->size--;
}

/*
* This function returns the value of an existing element in a dynamic array.
*
* Params:
* da - the dynamic array from which to get a value. May not be NULL.
* idx - the index of the element whose value should be returned. The value
* of `idx` must be between 0 (inclusive) and n (exclusive), where n is the
* number of elements stored in the array.
*/
void* dynarray_get(struct dynarray* da, int idx) {
assert(da);
assert(idx < da->size && idx >= 0);

return da->data[idx];
}

/*
* This function updates (i.e. overwrites) the value of an existing element in
* a dynamic array.
*
* Params:
* da - the dynamic array in which to set a value. May not be NULL.
* idx - the index of the element whose value should be updated. The value
* of `idx` must be between 0 (inclusive) and n (exclusive), where n is the
* number of elements stored in the array.
* val - the new value to be set. Note that this parameter has type void*,
* which means that a pointer of any type can be passed.
*/
void dynarray_set(struct dynarray* da, int idx, void* val) {
assert(da);
assert(idx < da->size && idx >= 0);

da->data[idx] = val;
}

Answer 1

Step 1. Please find the program below, copy and save the file in the same location as dynarray.h The statement #include "queue.h" should be remove from the program

Step 2. The file dynarray.c should be renamed to dynarray.h and the statement #include "dynarray.h" should be removed from the program dynarray.h

#include <stdlib.h>
#include "dynarray.h"

/*
* This is the structure that will be used to represent a queue. This
* structure specifically contains a single field representing a dynamic array
* that should be used as the underlying data storage for the queue.
*
* You should not modify this structure.
*/
struct queue {
   struct dynarray *array;
};

/*
* This function should allocate and initialize a new, empty queue and return
* a pointer to it.
*/
struct queue* queue_create() {
   return dynarray_create();
}

/*
* This function should free the memory associated with a queue. While this
* function should up all memory used in the queue itself, it should not free
* any memory allocated to the pointer values stored in the queue. This is the
* responsibility of the caller.
*
* Params:
* queue - the queue to be destroyed. May not be NULL.
*/
void queue_free(struct queue *queue) {
   dynarray_free(queue->array);
   return;
}

/*
* This function should indicate whether a given queue is currently empty.
* Specifically, it should return 1 if the specified queue is empty (i.e.
* contains no elements) and 0 otherwise.
*
* Params:
* queue - the queue whose emptiness is being questioned. May not be NULL.
*/
int queue_isempty(struct queue *queue) {
   return dynarray_size == 0;
}

/*
* This function should enqueue a new value into a given queue. The value to
* be enqueued is specified as a void pointer. This function must have O(1)
* average runtime complexity.
*
* Params:
* queue - the queue into which a value is to be enqueued. May not be NULL.
* val - the value to be enqueued. Note that this parameter has type void*,
* which means that a pointer of any type can be passed.
*/
void queue_enqueue(struct queue *queue, void *val) {
   dynarray_insert(queue->array, val);
   return;
}

/*
* This function should return the value stored at the front of a given queue
* *without* removing that value. This function must have O(1) average runtime
* complexity.
*
* Params:
* queue - the queue from which to query the front value. May not be NULL.
*/
void* queue_front(struct queue *queue) {
   return dynarray_get(queue->array, 0);
}

/*
* This function should dequeue a value from a given queue and return the
* dequeued value. This function must have O(1) average runtime complexity.
*
* Params:
* queue - the queue from which a value is to be dequeued. May not be NULL.
*
* Return:
* This function should return the value that was dequeued.
*/
void* queue_dequeue(struct queue *queue) {
   dynarray_remove(queue->array);
   return NULL;
}

Please find the program screenshot below, please follow the line numbers in the program:

Please provide a feedback by clicking on the feedback button