Homework 6
Implementing a stack as a linked list
Due: Tuesday, December 12 at 11:59pm
Outcomes
After successfully completing this assignment, you will
be able to...
- Implement a data structure using several levels of abstraction
- Construct a makefile for a program with multiple dependencies
- Demonstrate an understanding of linked list and stack operations
Before Starting
Read Chapter 12 (12.1 - 12.5)
The Assignment
For this assignment, you are provided with a library of linked list operations defined in the files linktool.h and linktool.c.
You should use the linked list operations defined in this library to implement the stack operations push,
pop, and isEmpty. You should demonstrate that
your implementations work by defining a short test program that
allows the user to push and pop items on a stack, and to test to see if a stack is empty.
I suggest you follow these steps:
- Create a directory to hold your hw6 files, and make that directory
your current one. Copy the Homework 6 files into your directory
with this Unix command:
cp /cs/cs2301/hw/hw6/* .
Compile linktool.c.
- Create two new files,
stack.h and stack.c.
stack.h should contain the pre- and post-conditions, and the
prototypes, for the three stack operations push, pop, and isEmpty.
stack.c should contain the function definitions for the
three stack operations. Your functions should be defined in terms of
linked list operations as much as possible (in other words, make calls
to the functions defined in linktool.h and linktool.c
instead of duplicating that code in your stack function definitions).
Compile stack.c.
-
Create a short test program
called
hw6.c that calls each of the stack operations (push, pop,
and isEmpty). Your test program should show that the stack behaves
properly (for example, if you push several items on the stack, then pop and print
each item, the items should be printed in the reverse order from which they
were pushed).
Compile hw6.c.
- Now is probably a good time to define your makefile for this program.
It's usually helpful to draw a dependency diagram first. Create your
makefile and use it to create your executable file.
- Test your program, and turn it in once you get it to run correctly.
Include files
- stdio.h
- stdlib.h provides malloc, free
You will also need to include header files that you define for this project.
Deliverables
You should turn in your stack files, your test program, and your makefile.
Submit your files using the following
turnin command:
/cs/bin/turnin submit cs2301 hw6 makefile stack.h stack.c hw6.c
Programs submitted after 11:59pm on December 12 will be tagged as late, and
will
be subject to the late homework policy.
Grading
This assignment will be graded on the following areas: documentation
(including pre- and post-conditions for any functions),
correctness of the makefile,
use of linked list functions in the stack implementations, and correctness.
Programs must compile successfully in order to receive points for correctness.