Corning Community College CSCS2320 Data Structures ~~TOC~~ ======Project: SLL2: Singly-Linked Stacks====== =====Overview===== We will be extending our sll1 project in sll2 with the addition of singly-linked list-based stacks. =====Update and Upgrade===== For this project, you'll update your **sll1** project to gain access to the new **upgrade-sll2** option in the Makefile: ====Step 0. Change into project directory==== Change to wherever you copied your code (I'm assuming **~/src/data/sll1** in my example): lab46:~$ cd src/data/sll1 lab46:~/src/data/sll1$ ====Step 1. Update to latest release (preserves your code)==== lab46:~/src/data/sll1$ make update ... ====Step 2. Upgrade to sll2 project (copies over your code)==== lab46:~/src/data/sll1$ make upgrade-sll2 ... ====Step 3. Change into sll2 directory==== lab46:~/src/data/sll1$ cd ../sll2 lab46:~/src/data/sll2$ =====Layout===== This project codebase is largely identical to the sll1 codebase; it merely adds the new files for the stack functionality. Be sure to check for new files in the following directories: * inc - stack.h header * src/stack - source code for the stack operations * testing - stacktest.c file (may work) =====Stacks===== A stack is another data structure, which is very heavily and widely used throughout computing and our everyday lives. It works on a principle of "last-in, first-out" (LIFO)... for our purposes it will be a restricted access linked list (one where only the "top" node can be accessed). This restriction of access creates new possibilities for algorithms, enabling useful functionality. The basic stack operations are: **push()** and **pop()** which will call the necessary underlying list operations (likely **append()** and **getNode()**) while maintaining the **top** pointer (reflecting some pointer in the underlying list, perhaps **end**). The stack has a **size** variable, which unlike the list's **qty** (which keeps track of how many nodes are in the list at any given time), **size** mandates a maximum size a stack can be (if the **qty** has reached **size**, no new nodes should be added (i.e. **push()**ed)- this is what is known as a **stack overflow condition**)). For purposes of flexibility, a **size** of zero denotes an unbounded stack (it can grow indefinitely, just like a list). There is often a **peek()** operation also provided with many stack implementations. It is by no means necessary (the underlying functionality can be entirely accomplished, perhaps less efficiently, with just **pop()** and **push()**. It is included here for additional practice and potential usage. =====Errata===== ====03/20/2014==== * **Update 1**: testing/stacktest.c, when run, issues a rather nasty error (double free)... it looks like I forgot to check for a NULL case. Fix has been issued (hopefully will resolve it; if not, another fix forthcoming). * By request, I've changed the deadline of sll2 to sunday instead of friday. You're welcome. ====03/22/2014==== * **Update 2**: Minor tweaks to testing/stacktest.c; might make usage clearer. * Provides upgrade path to the new **dll1** project (your next potential code rewrite) ====03/23/2014==== * **Update 3**: Think I found the problem with **testing/stacktest.c** * Implemented another stack test program: **testing/palindrome2.c** * Apparently update 2 never copied over the Makefile, this one does =====Submission===== To successfully complete this project, the following criteria must be met: * All code must compile cleanly (no warnings or errors) * Code must be nicely and consistently indented (you may use the **indent** tool) * Code must be commented * Resulting libraries must be operational and functionally correct * stack functions must operate as described, conforming to provided function prototypes * code must make use of the other node/list functions as appropriate- do not reinvent the wheel * evaluations of libraries using various unit tests will be an assessment criteria * Track/version the source code in a repository * Submit a copy of your source code to me using the **submit** tool (or **make submit**). To submit this program to me using the base Makefile, run the following command at your lab46 prompt: lab46:~/src/data/sll2$ make submit ... Submitting data project "sll2": -> sll2-20140317-18.tar.gz(OK) SUCCESSFULLY SUBMITTED You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches. ====Saving your work==== To submit the project, you will need to create an archive and submit that using the submit tool: lab46:~/src/data/sll2$ make save ... make save now issues a pre-emptive make clean ... Archiving the project ... Compressing the archive ... Setting permissions ... lab46:~/src/data/sll2$ cd .. lab46:~/src/data$ ls sll2*gz sll2-20140317-18.tar.gz lab46:~/src/data$