C PROGRAM

Assignment 3 deals with stacks and queues. You must implement these structures using linked lists, as described in class. Be sure to adhere to the concepts of abstract data types as much as possible Program Summary You're to create a program that implements both a stack and a queue, and processes commands as follows: s- set mode to "stack mode" and (always) print the current contents of the stack on one line, separated by spaces, with the top of the stack at the left (don't show the sentinel) . q-set mode to "queue mode" and (always) print the current contents of the queue on one line, separated by spaces, with the head of the queue on the left (don't show the sentinel). * Any legal integer - push onto the stack (stack mode) or insert at the tail of the queue (queue mode) . p either pop the top of the stack (stack mode) or remove the item at the head of the queue (queue mode) and print it. Q - exit the program (be sure to free all memory!) anything else should give a help message Details Implement the stack using a linked list, implement the queue using a second linked list (so you'll have two sentinel nodes, each pointing to a different linked list). You should use these lists as described in class (summarized below) For the stack, push new elements by adding a node immediately after the sentinel, and pop from the same location. For the queue, the head is the node immediately after the sentinel, and the tail is at the far end of the list. This means you remove elements by accessing the node immediately after the sentinel, and you add new elements by adding them to the end of the list. It's important that you do this efficiently! Therefore, you should augment your node structure to include a pointer ("tailptr" to the end of the list. You'll only need to use this field in the sentinel node, to keep track of the end of the list. This saves you from having to find the end by working forward from the beginning. Again, don't travel down the list to find the end; use the tailptr field in the sentinel This means that when you add a new node (inserting at the tail) you'll need to adjust the value of tailptr in the sentinel (when you remove from the head, there's no need to adjust the tail) Notes You shouldn't run out of memory in the tests I'll conduct (assuming your code is well-written). If the user tries to remove an item from an empty structure (stack underflow, or removing from an empty queue), give an appropriate error message but continue accepting commands, and do not corrupt your structures! Moving between stack mode and queue mode should not affect the contents of these data structures