Project: SLL2: Singly-Linked Stacks

We will be extending our sll1 project in sll2 with the addition of singly-linked list-based stacks.

For this project, you'll update your sll1 project to gain access to the new upgrade-sll2 option in the Makefile:

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$ 

lab46:~/src/data/sll1$ make update
...

lab46:~/src/data/sll1$ make upgrade-sll2
...

lab46:~/src/data/sll1$ cd ../sll2
lab46:~/src/data/sll2$ 

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)

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.

• 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.

• 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)

• 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

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.

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$