given codes in comments

Feel free to add any additional functions you might need to queue.c and stack.c. In addition, you may modify the dynamic array implementation provided in dynarray.h and dynarray.c or the linked list implementation provided in list.h and list.c as needed to help implement the queue and stack. Part 1. Implement a stack In this assignment, you'll implement two new ADTs on top of the data structures you implemented in the previous assignment. The first ADT you'll implement for this assignment is a stack. For this assignment, the interface for the stack is already defined for you in the file stack.h. Your first task in this assignment is to implement definitions for the functions that comprise this interface in stack.c. The stack functions you'll need to implement are outlined briefly below. All of these functions use a type called struct stack, which is defined in stack.c and represents the stack itself. For more details, including information on function parameters and expected return values, see the documentation provided in stack.c. stack_create () This function should allocate, initialize, and return a pointer to a new stack structure. stack_free () This function should free the memory held within a stack structure created by stack_create(). Note that this function only needs to free 1 the memory held by the stack itself. It does not need to free the individual elements stored in the stack. This is the responsibility of the calling function. . stack_isempty() This function should return 1 if the stack is empty and 0 otherwise. . stack_push() - This function should insert a new element on top of the stack. This operation must have 0(1) average runtime complexity. . stack_top () - This function should return the value stored at the top of the stack without removing it. This operation must have O(1) average runtime complexity. stack_pop () - This function should pop a value from the stack and return the popped value. This operation must have O(1) average runtime complexity. Importantly, the stack you build MUST use a linked list as its underlying data storage. You are provided with a linked list implementation in list.h and list.c that you may use for this purpose. Feel free to modify this linked list implementation as needed to implement your stack, with the constraint that your stack may only interact with the linked list implementation via its interface functions. In particular, you may not directly access or modify the fields of the linked list structure (struct list) from your stack. In other words, you may not change the fact that list.h only contains a forward declaration of struct list, and you may not redefine the list structure in stack.h or stack.c. Also, note that, as with the data structures you implemented in assignment 1, values in the stack will be stored as void pointers. Part 2. Implement a queue The second ADT you'll implement for this assignment is a queue. For this assignment, the interface for the queue is already defined for you in the file queue.h. Your second task in this assignment is to implement definitions for the functions that comprise this interface in queue.c. 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 0(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 your queue 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) from your queue. 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. Part 3. Application: testing for palindromes Finally, in palindrome.c, you should implement an application that uses both your stack and your queue to test for palindromes. A palindrome is a string that reads the same backward as forward, e.g. "ABCBA" or "Madam, I'm Adam". Your application will read strings from the user, and for each string the user inputs, it should print a message indicating to the user whether or not the string is a palindrome. There's already some code in palindrome.c to get you started. Here are some things you should bear in mind as you're implementing your application: Your palindrome testing procedure must use BOTH your stack and your queue. In other words, for each string the user enters, you must print a single message indicating whether or not that string is a palindrome, and the procedure to compute that message must use both a stack and a queue. To understand how you might do this, think carefully about the ordering each data structure imposes on the elements put into it. (This is another question like you might be asked during a job interview.) . When testing whether a string is a palindrome, you should ignore all non-letter characters, such as numbers, spaces, punctuation, etc. The C function isalpha) might be helpful here. Don't forget to include if you want to use isalpha(). . When testing whether a string is a palindrome, you should also ignore the case of letters. In other words, uppercase letters and lowercase letters should be considered equivalent. For example, you should consider 'a' and 'A' as equal. The C function tolower() might be helpful here. Again, don't forget to include if you want to use tolower(). . Remember, the stack and queue data structures you implement will store data as void pointers, so you'll need to figure out how to store characters from the input string as void pointers in these data structures. Make sure your application doesn't have any memory leaks! Extra credit: use two stacks to implement a queue For up to 10 points of extra credit, you can implement a data structure that uses two instances of your stack data structure to implement a queue. In other words, you should implement a queue that uses two stacks to form the underlying container in which data is stored (instead of, for example, a dynamic array or a linked list). For example, when the user calls enqueue () on your queue-from-stacks data structure, it will add the newly-enqueued element into one of the two stacks, as appropriate, and when the user calls dequeue (), your queue-from-stacks will remove the appropriate element from one of the two stacks. To the user of your queue-from-stacks, it will behave just like a normal queue. (This is yet another "job interview" kind of problem!) *Hint: to implement a queue using two stacks, it might help to think of one stack as an "inbox" and one stack as an "outbox". The interface of your queue-from-stacks is defined in queue_from_stacks.h, and you must complete each of the functions implementing the queue-from-stacks in queue_from_stacks.c. Each of the functions in queue_from_stacks.c has a function header comment that describes more precisely how it should behave. To be able to earn this extra credit, your stack implementation above must be working correctly, and importantly, you may only use the functions from your stack implementation prototyped in stack.h to interface with your two stacks. You may not access the underlying stack data directly. Also, make sure your queue-from-stacks implementation does not have any memory leaks! Note that there are no runtime complexity requirements for the queue-from-stacks operations. In other words, you can still earn the full extra credit even if your enqueue and/or dequeue operation is O(n). To test your queue-from-stacks implementation, a testing application test_queue_from_stacks.c is provided. This application will be compiled automatically using the provided makefile. You can run it like so: ./test_queue_from_stacks. Testing your work In addition to the skeleton code provided here, you are also provided with some application code in test_stack.c and test_queue.c to help verify that your stack and queue implementations, respectively, are behaving the way you want them to. In particular, the testing code calls the functions from stack.c and queue.c, passing them appropriate arguments, and then prints the results. You can use the provided Makefile to compile all of the code in the project together, and then you can run the testing code as follows: make ./test_stack ./test_queue Example output of these two testing programs using correct implementations of the stack and queue is provided in the example_output/ directory. In order to verify that your memory freeing functions work correctly, it will be helpful to run the testing applications through valgrind