Project: Stack Variations
This project will give you practice with stacks and with the difference between accessing the field of a variable passed to a function as a pointer to a
struct vs. as a copy of a
PreparationCopy the source files to your own working directory, perhaps as follows. These commands will copy the
stacksdirectory from johnsonba to your account, copying all of the files within the directory to a new directory..
cd ~/csc161/projects cp -i -R /home/johnsonba/public_html/CSC161/2019F/modules/pointers-stacks-queues/src/stacks ./
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 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. You are encouraged to draw diagrams for each approach.
For this part, you do not need to compile or run the code. Simply read through the code given in the reading for each of the 4 approaches. Note that these approaches may give different results and even give results that might be considered errors. This is by design. Explain what would happen and why.
Part B: Experimentation
You will compile 4 programs with one command:
make project. This will produce four executable programs, each corresponding to one of the 4 stack implementation approaches.
creates a single stack
myStack and then uses the
standard stack operations in the following sequence:
- initializes three strings with variables a, b, c
- pushes a, b, and c onto the stack
- pops the stack three times to get strings stored as variables d, e, and f
- prints the strings referenced by a, b, c, d, e, f
changes strings a and e to a text not previously used
strcpyfrom the string library)
- prints the strings referenced by a, b, c, d, e, f
- defines two new strings g and h, initialized to previously unused values
- pushes g and h onto the stack
changes string g to a new value (use
strcpyor access a specific character with a subscript—
str = 'q')
- prints 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). Write down this explanation as part B of the material you will hand in for grading.
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. You will create a new stack handling program in step 1. Then, you will run performance comparisons and analyze the results in Steps 2 and 3.
First we must adapt one of the stack implementations so that it
does not pass a pointer when the stack will not be changed by the function. To do so, we
will construct an entirely new and complete stack interface and
implementation as follows. In all your work, be sure to carefully
document the authors of the source code.
stack.hto a file called
stack-func.hand change the declarations of all functions except
popto take simply a
struct string_stackas a parameter, rather than a pointer to a
Copy the declarations and definition
stack-buffer.h(do not include the include guard) to your
stack.cto a file called
stack-func.cand change the implementations of the functions there to reflect the declarations from
stack.h. Note: you will need to change the function header declarations and modify how the fields of the stack are accessed within the function.
Copy the implementations
push, pop, top,and
stack-func.cfile and update the implementations to match the declarations of your
Add an entry to the
Makefileto compile the object file
stack-func.o. (Note that it is not yet linked into an executable. If you need a refresher on Makefiles, refer back to the Program Management reading.)
Next we will want to examine quantitatively the performance
ramifications of these changes to the interface. You will be first running the original pointer-based code and then the modified version.
stack-project-compare.c. Inspect, compile (see the
Makefile), and run the program to be sure you understand what it does.
The small stacks and strings are not likely to yield any
1024by providing these definitions during compilation:
make clean make stack-project-compare CPPFLAGS="-DMAX_STRING_LENGTH=256 -DMAX_STACK_SIZE=1024"
Use the Bash shell's
timecommand to determine how long it takes to run the program with the original interface. For example,
real 0m0.036s user 0m0.018s sys 0m0.015s
strcpy), rather than waiting for other programs or running priviledged instructions.
stack-project-compare-func.cand modify it to include your
stack-func.hfile and update the necessary stack function calls to use the alternative interface, rather than pointers. (Note: I had to add assert.h and string.h to the #include preprocessor directives and remove references to stack.h and stack-buffer.h while cleaning up files before compiling. You will get some warnings about size_t vs. int types, but so long as they are warnings and not errors, you should be fine. )
Makefileshould have a new target (
stack-project-compare-func) near the bottom of the file that compiles
stack-project-compare-func.cand links it with
stack-func.o. (Make sure you clean the old object files first and then rebuild with the larger string length and stack size definitions!)
- Compile 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
/* compare argument sizes */ printf("Stack argument size: %ld\n", sizeof(*pStack)); printf("Stack pointer argument size: %ld\n", sizeof(struct stack *));
- Copy program
- What differences in performance do you notice between the original pointer-based and your updated, more functional stack interface? In particular, what is the ratio of the user times? Explain the likely cause of these differences.
Files to Submit
You should submit the following files both printed and emailed to the grader account:
- stack-func.c and stack-func.h
- Modified stack-project-compare.c
- Commentary file
- Answers to questions as laid out below.
- Transcript including compile and test run with data from stack-func.c with MAX_STACK_SIZE=MAX_STRING_LENGTH=1024.
The project is worth 20 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 points] (C.2) Reports comparative performance times
- [2 points] (C.3) Explains comparative performance times