For this assignment you will be writing a C program that creates and uses an implementation of a deque. Your will use a double$-$linked list for your deque, and your deque will be able to store any data type. You must create your own implementation, and not use the ADT version in the text.

Important: This project will also have specific build requirements using make and Makefile, and testing requirements using an input script, and producing an output file. You will have to submit these additional files as part of your submission.

All assignment submissions will be validated using the class VM$.$

Deque Implementation Requirements

A deque is a data structure that supports efficient insertion and deletion from both ends of a list, and may be implemented using a variety of different data structures. Each list element is typically called a node.$$

For this project, your deque must conform to the following requirements.

Use the following node structure.

typedef struct Node

$\{$

$$ void $*$data;

$$ struct Node $*$next;

$$ struct Node $*$prev;

$\}$ Node;

Use the following deque structure.

typedef struct Deque

$\{$

$$ Node $*$front;

$$ Node $*$back;

$$ int count;

$\}$ Deque;

Include the following type to declare the requirements for the deque print function pointer.

typedef void $(*$printData$)($void $*)$;

Implement the following deque prototypes.

Node $*$newNode$($void $*$data$,$ size$\_$t dataSize$)$;

Deque $*$createDeque$()$;

void insertFront$($Deque $*$deque$,$ void $*$data$,$ size$\_$t dataSize$)$;

void insertBack$($Deque $*$deque$,$ void $*$data$,$ size$\_$t dataSize$)$;

void removeFront$($Deque $*$deque$,$ void $*$data$,$ size$\_$t dataSize$)$;

void removeBack$($Deque $*$deque$,$ void $*$data$,$ size$\_$t dataSize$)$;

void freeDeque$($Deque $*$deque$)$;

void printDeque$($Deque $*$deque$,$ printData print$)$;

Add const to the function parameters where appropriate $-$ your final function signatures$/$fingerprints will include the const keyword.

Use dynamic memory to create each deque. If the memory allocation for the deque was unsuccessful, output Error allocating memory for deque. to stderr$$and exit the program using exit$($EXIT$\_$FAILURE$).($tip: fprintf$)$

Use dynamic memory to create each deque node. If the memory allocation for the node was unsuccessful,$$output Error allocating memory for node. to stderr$$and exit the program using exit$($EXIT$\_$FAILURE$).($tip: fprintf$)$

Use dynamic memory to allocate space for the data for each node. You will need to use memcpy to duplicate the data to be stored in each node, using the dataSize parameter for the data malloc size. If the memory allocation for the node was unsuccessful, output Error allocating memory for node data. to stderr$$and exit the program using exit$($EXIT$\_$FAILURE$).($tip: fprintf$)$

Maintain a count of the number of nodes in a deque.

Implement printDeque to accept a pointer to a function that is able to print the data type of the deque. The printDeque function is responsible to iterate through the deque nodes.

Implement freeDeque to deallocate memory for each node data, each node, and the deque.

Both remove functions, removeFront and removeBack, use the data function parameter to "return" the node data. These functions should also use a maximum string length constant $($e$.$g$.$ MAX$\_$STR$\_$LEN$)$ as a parameter when removing string data types.