Question

In: Computer Science

Implement a queue - C programming, please read the instruction carefully and implement queue.c using dynamic...

Implement a queue - C programming, please read the instruction carefully and implement queue.c using dynamic array structure given dynarray.h and dynarray.c below

The second ADT you'll implement for this assignment is a queue.

For this assignment, the interface for the queue (i.e. the structures and the prototypes of functions a user of the queue interacts with) is already defined for you in the file queue.h. Your first task in this assignment is to implement definitions for the functions that comprise this interface in queue.c.

Note that you may not modify the interface definition with which you are provided. Specifically, do not modify any of the already-defined queue function prototypes. We will use a set of tests to verify your implementation, and if you change the queue interface, it will break these tests, thereby (negatively) affecting your grade. Beyond the already-defined interface, though, feel free to add any additional functions or structures your queue implementation needs.

The queue functions you'll need to implement are outlined briefly below. All of these functions use a type called struct queue, which is defined in queue.c and represents the queue itself. For more details, including information on function parameters and expected return values, see the documentation provided in queue.c.

queue_create() - This function should allocate, initialize, and return a pointer to a new queue structure.
queue_free() - This function should free the memory held within a queue structure created by queue_create(). Note that this function only needs to free the memory held by the queue itself. It does not need to free the individual elements stored in the queue. This is the responsibility of the calling function.
queue_isempty() - This function should return 1 if the queue is empty and 0 otherwise.
queue_enqueue() - This function should insert a new element at the back of the queue. This operation must have O(1) average runtime complexity.
queue_front() - This function should return the value stored at the front of the queue without removing it. This operation must have O(1) average runtime complexity.
queue_dequeue() - This function should dequeue a value from the queue and return the dequeued value. This operation must have O(1) average runtime complexity.

Importantly, the queue you build MUST use a dynamic array as its underlying data storage. You are provided with a dynamic array implementation in dynarray.h and dynarray.c that you may use for this purpose. Feel free to modify this dynamic array implementation as needed to implement your queue, with the constraint that you may only interact with the dynamic array implementation via its interface functions. In particular, you may not directly access or modify the fields of the dynamic array structure (struct dynarray). In other words, you may not change the fact that dynarray.h only contains a forward declaration of struct dynarray, and you may not redefine the dynamic array structure in queue.h or queue.c.

Also, note that, as with the data structures you implemented in assignment 1, values in the queue will be stored as void pointers.

dynnaray.h

/*
* This file contains the definition of the interface for a dynamic array.
* You can find descriptions of the dynamic array functions, including their
* parameters and their return values, in dynarray.c.
*/

#ifndef __DYNARRAY_H
#define __DYNARRAY_H

/*
* Structure used to represent a dynamic array. You may not change the fact
* that only a forward declaration of the dynamic array structure is included
* here. In other words, you can't define the fields of the struct here.
*/
struct dynarray;

/*
* Dynamic array interface function prototypes. Refer to dynarray.c for
* documentation about each of these functions.
*/
struct dynarray* dynarray_create();
void dynarray_free(struct dynarray* da);
int dynarray_size(struct dynarray* da);
void dynarray_insert(struct dynarray* da, void* val);
void dynarray_remove(struct dynarray* da, int idx);
void* dynarray_get(struct dynarray* da, int idx);
void dynarray_set(struct dynarray* da, int idx, void* val);

#endif

dynarray.c

/*
* This file contains a simple implementation of a dynamic array. See the
* documentation below for more information on the individual functions in
* this implementation.
*/

#include
#include

#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;
}

queue.h

/*
* This file contains the definition of the interface for the queue you'll
* implement. You can find descriptions of the queue functions, including
* their parameters and their return values, in queue.c. You should not
* modify anything in this file.
*/

#ifndef __QUEUE_H
#define __QUEUE_H

/*
* Structure used to represent a queue.
*/
struct queue;

/*
* Queue interface function prototypes. Refer to queue.c for documentation
* about each of these functions.
*/
struct queue* queue_create();
void queue_free(struct queue* queue);
int queue_isempty(struct queue* queue);
void queue_enqueue(struct queue* queue, void* val);
void* queue_front(struct queue* queue);
void* queue_dequeue(struct queue* queue);

#endif

queue.c

#include

#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;
}

Expert Solution

// dynarray.h

/*
* This file contains the definition of the interface for a dynamic array.
* You can find descriptions of the dynamic array functions, including their
* parameters and their return values, in dynarray.c.
*/

#ifndef __DYNARRAY_H
#define __DYNARRAY_H

/*
* Structure used to represent a dynamic array. You may not change the fact
* that only a forward declaration of the dynamic array structure is included
* here. In other words, you can't define the fields of the struct here.
*/
struct dynarray;

/*
* Dynamic array interface function prototypes. Refer to dynarray.c for
* documentation about each of these functions.
*/
struct dynarray* dynarray_create();
void dynarray_free(struct dynarray* da);
int dynarray_size(struct dynarray* da);
void dynarray_insert(struct dynarray* da, void* val);
void dynarray_remove(struct dynarray* da, int idx);
void* dynarray_get(struct dynarray* da, int idx);
void dynarray_set(struct dynarray* da, int idx, void* val);

#endif

// end of dynarray.h

// dynarray.c

/*
* This file contains a simple implementation of a dynamic array. See the
* documentation below for more information on the individual functions in
* this implementation.
*/

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