Project: Stack Variations

Part A: Code Analysis

Examine each of the four implementation approaches in the accompanying reading. For each approach, identify:

what information is stored by a push (e.g., a string, a copy of a string, a pointer to the original string, a pointer to a copy of the string)
what information is returned by a pop (e.g., a pointer from the stack, a pointer to a string stored on the stack, a pointer to a copy of the string designated on the stack)

In each case, briefly justify your conclusions based on the code.

Part B: Experimentation

The program stack-project.c creates a single stack myStack and then uses the standard stack operations in the following sequence:

initial three strings with variables a, b, c (the initialization is up to you, but the three strings should have different values)
push a, b, and c onto the stack
pop the stack three times to get strings stored as variables d, e, and f
print the strings referenced by a, b, c, d, e, f
change strings a and e to a text not previously used (use strcpy from the string library)
print the strings referenced by a, b, c, d, e, f
define two new strings g and h, initialized to previously unused values
push g and h onto the stack
change string g to a new value (use strcpy or access a specific character with a subscript—str[2] = 'q')
print the strings referenced by a, b, c, d, e, f, g, h

Review the output obtained with each of the four stack implementation approaches. Explain the results obtained (e.g., what variables remain the same, what changes and how/why).

Part C: Functional Stacks

The reading on stacks compared two stack interfaces: one that relies entirely on pointers and one that does not. You will explore the implications of this distinction in this part of the project.

Copy stack-lab-2.c to a file called stack-lab-2-func.c and change the declarations and implementations of all functions except initialize, push and pop to take simply a stringStack as a parameter, rather than a pointer. You will also need to update the implementations of push and pop to reflect these changes.
Next we will want to examine the ramifications of these changes.
- Copy program stack-project-compare.c. Inspect, compile, and run the program to be sure you understand what it does.
- The small stacks and strings are not likely to yield any insights. In both stack-lab-2.c and your stack-lab-2-func.c, change MaxStack to 1000 and StringLength to 256.
- Recompile your program and use the Bash shell's time command to determine how long it takes to run the program with the original interface. For example,
```
time ./stack-project-compare
```
```
real    0m0.036s
user    0m0.018s
sys     0m0.015s
```
  To dissipate disk or network effects, you will likely want to run the command a few times until the numbers are approximately consistent. Make note of the user time, which indicates the amount of time the operating system spent running your code or library code (e.g., strcpy), rather than waiting for other programs or running priviledged instructions.
- Now change stack-project-compare.c to include your stack-lab-2-func.c and update the necessary stack function calls to use the alternative interface, rather than pointers.
- Recompile the program and time how long it takes to run the program with the functional interface. To dissipate disk or network effects, you will likely want to run the command a few times until the numbers are approximately consistent. Make a note of the new user time.
- To help you gain some perspective, add the following lines to the end of main in stack-project-compare.c
```
  /* compare argument sizes */
  printf("Stack argument size:         %ld\n", getArgSize(myStack));
  printf("Stack pointer argument size: %ld\n", getPointerArgSize(&myStack));
```
What differences in performance do you notice between the original pointer-based and your updated, more functional stack interface? Explain what causes these differences.

Part D: A Stack of Pictures

Suppose you wanted to use a stack to store successive pictures taken by a Scribbler 2 robot. For each of the four pointer-based approaches identified for strings, explain whether the approach for strings could be easily modified for pictures. If a similar approach is possible, outline what adjustments would be needed. If the approach is not easily adapted to pictures, briefly explain why.
In reviewing various approaches for implementing an array-based stack of pictures, how would you proceed? Explain either your choice to adapt one of the approaches discussed for strings or to use a different approach.

Grading

In addition to the general grading guidelines for evaluation, the project is worth 25 points.

[8 points] (Part A) Discussion of the four stack implementations
[4 points] (Part B) Discussion of experimental output
[8 points] (Part C) Functional stack implementation and comparison

[4 points] (C.1) Implements functional stack elements
[2 point] (C.3) Reports comparative performance times
[2 points] (C.3) Explains comparative performance times

[5 points] (Part D) Discussion of array-based stacks for pictures

[3 points] (D.1) Explains adaptation of stacks to pictures
[2 points] (D.2) Justifies stacks choice for pictures