Assignment 2 Stacks and Linked Lists In this assignment you are given code for a Stack. However, this code has been impl
Posted: Sun Jul 10, 2022 11:26 am
Assignment 2 Stacks and Linked Lists In this assignment you aregiven code for a Stack. However, this code has been implementedusing Arrays. You will need to rewrite the code (from scratch)implementing the Stack using Linked Lists instead of Arrays.
Use the Arrays implementation code provided as a guide for yourLinked List implementation. The demo/driver code should not betouched/changed (with the exception of uncommenting/commenting out2 lines, as described below). It should work for either the LinkedList or Array implementation (this is called “encapsulation” incomputer science and is a fundamental principle of coding andsoftware engineering, essentially stating that a program/functionshould not need to know how another program/function works only howto call that function, what data to provide it, and what data itwill return). You will need to re-code the “stackArray.c” and“stackArray.h” files:
● Create 2 new files called “stackLinkedList.h” and“stackLinkedList.c”.
● Create a “make” file that will run the necessary compilercommands to compile stackDemo.c with your stackLinkedList.h andstackLinkedList.c.
● All of the function declarations and the boolean enumdefinition in stackArray.h must NOT be changed. Simply copy andpaste them into your new stackLinkedList.h file. The only exceptionto this could be the “isFull” function (theoretically, the list hasno “full” limit; concretely, it is limited by the amount of memoryon the computer running the algorithm), so you may choose to notimplement/define that function if you wish.
● Include a modified Stack definition and add a Node definitionin stackLinkedList.h. The data held by the node is the same as thedata held by the array in stackArray.h.
● Code/Implement each function declaration fromstackLinkedList.h in stackLinkedList.c using the newly definedStack and Node. REMEMBER: there are different cases and checks youwill need to handle: ○ If you malloc ANYTHING you must check thatthe pointer returned to you from the malloc is not NULL; if it isNULL then you will need to print an error message and then returnfrom the function.
○ Yourinsert/delete (i.e., push/pop) implementation must be O(1) time.There are 2 main approaches to do this, you may use either.
○ Theremay be cases where you need to check that the list is empty beforeperforming certain actions.
○ Whenyou free a struct, make sure you free anything malloc-ed INSIDE thestruct first, then the struct itself. Run valgrind to be sure youhave no memory leaks.
● Uncomment “#include "stackLinkedList.h" ” from stackDemo.c andthen comment out “#include "stackArray.h" ”. ● Compile and runstackDemo.c (using your make file), verify output, and then zip thefiles and turn it in on blackboard. Notes/Hints:
● In order to run the stackDemo program you will need to have“stackDemo.c”, “stackArray.c”, and “stackArray.h” in the samefolder and then (from that folder) run:
○ gcc -cstackArray.c
○ gcc -cstackDemo.c
○ gccstackDemo.o stackDemo.o -o stackDemo
○./stackDemo The commands will be the same for the stackLinkedListimplementation (just put into a make file and with the“stackLinkedList” names instead of the “stackArray” names).
● You may look at Lecture 3 for a make file template if you areunsure how to implement one.
● Drawing pictures of the actions and going through some examplestates of the Linked List is often extremely helpful if you getstuck or are confused.
(stackDemo.c)
(stackArray.c)
(stackArray.h)
Use the Arrays implementation code provided as a guide for yourLinked List implementation. The demo/driver code should not betouched/changed (with the exception of uncommenting/commenting out2 lines, as described below). It should work for either the LinkedList or Array implementation (this is called “encapsulation” incomputer science and is a fundamental principle of coding andsoftware engineering, essentially stating that a program/functionshould not need to know how another program/function works only howto call that function, what data to provide it, and what data itwill return). You will need to re-code the “stackArray.c” and“stackArray.h” files:
● Create 2 new files called “stackLinkedList.h” and“stackLinkedList.c”.
● Create a “make” file that will run the necessary compilercommands to compile stackDemo.c with your stackLinkedList.h andstackLinkedList.c.
● All of the function declarations and the boolean enumdefinition in stackArray.h must NOT be changed. Simply copy andpaste them into your new stackLinkedList.h file. The only exceptionto this could be the “isFull” function (theoretically, the list hasno “full” limit; concretely, it is limited by the amount of memoryon the computer running the algorithm), so you may choose to notimplement/define that function if you wish.
● Include a modified Stack definition and add a Node definitionin stackLinkedList.h. The data held by the node is the same as thedata held by the array in stackArray.h.
● Code/Implement each function declaration fromstackLinkedList.h in stackLinkedList.c using the newly definedStack and Node. REMEMBER: there are different cases and checks youwill need to handle: ○ If you malloc ANYTHING you must check thatthe pointer returned to you from the malloc is not NULL; if it isNULL then you will need to print an error message and then returnfrom the function.
○ Yourinsert/delete (i.e., push/pop) implementation must be O(1) time.There are 2 main approaches to do this, you may use either.
○ Theremay be cases where you need to check that the list is empty beforeperforming certain actions.
○ Whenyou free a struct, make sure you free anything malloc-ed INSIDE thestruct first, then the struct itself. Run valgrind to be sure youhave no memory leaks.
● Uncomment “#include "stackLinkedList.h" ” from stackDemo.c andthen comment out “#include "stackArray.h" ”. ● Compile and runstackDemo.c (using your make file), verify output, and then zip thefiles and turn it in on blackboard. Notes/Hints:
● In order to run the stackDemo program you will need to have“stackDemo.c”, “stackArray.c”, and “stackArray.h” in the samefolder and then (from that folder) run:
○ gcc -cstackArray.c
○ gcc -cstackDemo.c
○ gccstackDemo.o stackDemo.o -o stackDemo
○./stackDemo The commands will be the same for the stackLinkedListimplementation (just put into a make file and with the“stackLinkedList” names instead of the “stackArray” names).
● You may look at Lecture 3 for a make file template if you areunsure how to implement one.
● Drawing pictures of the actions and going through some examplestates of the Linked List is often extremely helpful if you getstuck or are confused.
(stackDemo.c)
(stackArray.c)
(stackArray.h)