Stacks

Goals:

The main goal of this lab is to gain facility with two common methods of implementing the data organization type called stacks.

Part A: Stacks with Arrays

Background

The reading describes a stack as an object that can store data and that has the following operations:

Initialize: Sets topPosition to -1 to indicate an empty stack.
Empty: Empty returns true or false, depending upon whether the stack contains any items or not.
Full (optional): Full returns true or false, depending upon whether the stack contains as much data as it can hold.
Push: Push adds the specified item to the top of the stack.
Pop: If the stack is not empty, Pop removes the top item from the stack, and this item is returned.
If the stack is empty, nothing is returned, and an error is reported.
Top: If the stack is not empty, the top item is returned, but the contents of the stack are not changed.
If the stack is empty, nothing is returned, and an error is reported.

Within C, there is no way to combine underlying data structures (e.g., arrays) and operations within a single structure. (Such a combined ADT can be done in C++ or Java, but we leave those languages for other courses!) Instead, we will define variables for each stack needed. For each operation, we will pass the relevant variables as parameters, so we can use the same functions for multiple stacks. This approach requires that the data items for the stack have the same type (e.g., a stack of doubles or a stack of strings).

For this section of the lab, we will focus on arrays of strings, which leads to the following declarations for stacks of fruits, vegetables, and pastries:

#define MAX_STACK_SIZE 50
/* Size of all stack arrays */

typedef struct {
  int topPosition;
  char * stackArray[MAX_STACK_SIZE];
} stringStack;      /* Type for a stack of strings */

With this framework, the isFull and push operations might be defined as follows:

bool
isFull (const stringStack * stack)
{
  /* determine whether there are no available positions in a stackArray */
  return (stack->topPosition == (MAX_STACK_SIZE-1));
} // isFull

bool
push (stringStack * stack, char * item) {
/* post-conditions:  item string is added to stack and returns true
                     or else stack is unmodified and returns false 
                     (when stack is full).
*/
  /* return false if stack full */
  if (isFull(stack))
    return false;
  
  /* add item to stack */
  (stack->topPosition) ++;
  stack->stackArray[stack->topPosition] = item;
  return true;
} // push

Exercises

Create a directory for this lab in your directory for this class, and move to the lab directory. For example:
```
mkdir stacks && cd stacks
```
Copy declarations of the array-based stack ADT from the reading on stacks to a header file called arrayStack.h.
- Remember to cite the origin of your code.
- Add an #ifndef include "guard" to avoid repeated declarations.
Consider the following stack functions:
- void initialize (stringStack * stack) (sets topPosition of stack to -1)
- bool isEmpty (const stringStack * stack)
- char * pop (stringStack * stack) (asserts the stack is not empty; removes and returns the top string from the stack)
- char * top (const stringStack * stack) (asserts the stack is not empty; returns the top string on the stack without modifying the stack)
1. Why is stringStack * stack used as the parameter for initialize and pop, while the parameter for isEmpty and top is const stringStack *?
2. Complete the implementation of a stack of strings by implementing these four stack operations in a file called arrayStack.c (Don't forget to include your header.)
Perhaps using the Makefile from the previous reading on program management as an example, create a Makefile with a rule for compiling an object file (.o) of your array-based stack. Be sure to include all the relevant file dependencies.
After writing functions, it is important to test your code to ensure that it works as you expected and accounts for unusual cases.
1. Create a test driver program called testArrayStack.c with a main function that declares and then initializes three stacks within a main program for fruit, vegetables, and pastry.
2. Add two more rules to your Makefile: one to compile an object file for your driver, and another to link the two object files. Test that make properly compiles and links all three targets.
3. Complete tests of your code by executing the following instructions:
  - Push "apple" and "orange" onto the fruit stack.
  - Push "doughnut" onto the pastry stack.
  - Check if the three stacks are empty.
  - Push "corn", "beans", "squash", and "broccoli" onto the vegetable stack.
  - Print the top of each stack.
  - Pop one item off the pastry stack and print it.
  - Print the top of each stack.
    
    Hint: the pastry stack is empty. Be careful!
  - Pop three items off the vegetable stack and print.
  - Pop up to three items off the fruit stack and print.
    
    Hint: how many items are on the fruit stack initially?
  - Push "cake" onto the pastry stack.
  - Check whether any of the three stacks is empty.
Add the following procedures to the your header and implement the corresponding library code.
- int size (const stringStack * stack) (returns the number of items currently on the stack)
- void print (const stringStack * stack) (prints all of the current elements on the stack)
- char * get (const stringStack * stack, int n) (returns the string at the nth position from the top of the stack)
- char* getFirst (const stringStack * stack) (scans all items on a stack and returns the one that comes first in alphabetical order)
Add code to your driver program that tests the functionality of these new functions.

Part B: Stacks with Linked Lists

In Part A, you used a set of function prototypes for an array-based stack. The section of the reading regarding linked lists discusses these functions in the context of linked lists using a different declaration for the stringStack type:

#define MAX_STRING_LENGTH 50

typedef struct node {
  char string[MAX_STRING_LENGTH];
  struct node * next;
} stackNode;
        
typedef struct {
  unsigned int size;
  stackNode * top;
} stringStack;

Copy the header and library file you wrote for the earlier section on stacks with arrays, calling them listStack.h and listStack.c. Modify them so that the stacks are implemented by linked lists. In doing so, you will need to
- Update the symbol used in the include guard to reflect the new file name,
- replace the typedefs as above,
- change the bodies of the six core prototype functions, and
- add a new rule and target to your Makefile to compile the new file to an object.
Copy your previous test driver to testListStack.c and change your #include to the list-based stack header.
- The declaration of the stack variables for the three stacks (fruits, vegetables, and pastries) should change their type, and you still need to initialize them. However, you should not have to change any of the code used for testing.
- As before, add two more Makefile targets (one to compile, one to link). Build and run your new program. The output of should be identical in all respects to the output of the program from the previous section.
As with the previous section on stacks with arrays, expand the code for the list-based ADT implementation to include these functions:
- a size function, which will return the number of items currently on the stack,
- a print function, which will print all of the current elements on the stack (each of the elements on a separate line, without modifying the stack), and
- a get function, which takes one additional parameter (an index) and returns the item at that position from the top in the current stack.
- a printReverse function, which prints all items on a stack, from the bottom of the stack to the top. (Thus, the top item will be printed last.)
  
  Hint: Consider printReverse as a husk procedure that calls a recursive kernel procedure to move along the stack's list and do the printing. Think carefully about the order of printing a node's contents and the recursive call print the rest of the stack.

Submitting

Your stacks lab submission should include the following completed files:

arrayStack.c
testArrayStack.c
arrayStack.h
listStack.c
testListStack.c
listStack.h
Makefile
references.txt
tests.txt showing complete compilation and running of both implementations and their test program

testListStack

testArrayStack

tests.txt