This assignment is comprised of 3 parts:
Part 1: Linked List Deque and Bag implementation
First, complete the linked list implementation of the deque (as in Worksheet 19) and bag ADTs (Worksheet 22
due in week 4). To do this, implement all functions with the // FIXME... comments in linkedList.c .
Grading (30 pts):
init 2 pts
addLinkBefore 3 pts
removeLink 3 pts
linkedListAddFront 2 pts
linkedListAddBack 2 pts
linkedListFront 2 pts
linkedListBack 2 pts
linkedListRemoveFront 2 pts
linkedListRemoveBack 2 pts
linkedListIsEmpty 2 pts
linkedListPrint 2 pts
linkedListContains 3 pts
linkedListRemove 3 pts
Part 2: Circularly Linked List Deque implementation
In this part, you will implement the Deque ADT with a CircularlyDoublyLinked List with a Sentinel. As you know, the sentinel is a special link, does not contain a meaningful value, and should not be removed. Using a sentinel makes some linked list operations easier and cleaner in implementation. This list is circular, meaning the end points back to the beginning, thus one sentinel suffices. Implement all functions with the
// FIXME... comments in circularList.c .
Grading (30 pts):
init 1 pts
createLink 1 pts
addLinkAfter 2 pts
removeLink 2 pts
circularListAddBack 2 pts
circularListAddFront 2 pts
circularListFront 2 pts
circularListBack 2 pts
circularListRemoveFront 2 pts
circularListRemoveBack 2 pts
circularListDestroy 2 pts
circularListIsEmpty 2 pts
circularListPrint 2 pts
circularListReverse 6 pts ( Importantly, you must perform the list reversal in place and may not allocate any new memory in this function)
Part 3: Linked List Stack implementation using two Queues
In this part, you will use two instances of Queue ADT to implement a Stack ADT. You will use only one C file (stack_from_queue.c) containing all the functions to design the entire interface. Also, make sure your stack- from-queues implementation does not have any memory leaks!
Grading (40 pts) :
listQueueInit -- 2 pts
listQueueCreate -- 2 pts listQueueIsEmpty -- 2 pts listQueueAddBack -- 5 pts
listQueueRemoveFront -- 5 pts listQueueFront -- 3 pts listStackInit -- 2 pts
listStackFromQueuesCreate -- 2 pts liststackIsEmpty -- 2 pts listSwapStackQueues -- 2 pts
listStackPush -- 5 pts
listStackPop -- 5 pts
listStackTop -- 3 pts
What to turn in:
You will turn in the following three(3) files to both TEACH and Canvas -
linkedList.c your linked list deque and bag implementation.
circularList.c your circularly linked list deque implementation.
stack_from_queue.c your linked list stack implementation.
Use the provided makefiles/header files to compile your code on flip. Also, you must test your compiling on flip.engr.oregonstate.edu. Zero credit if we cannot compile your programs. Finally, please don’t submit in zipped format to TEACH.
