Homework 6
Implementing a stack as a linked list
(This is the new version of the assignment, posted
at 5:30pm on Thursday, December 9)
Due: Tuesday, December 14 at 5pm
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 should implement the stack operations push,
pop, and isEmpty in terms of the linked list operations
defined in linktool.h
and linktool.c
(from Lab 6). You should demonstrate that
your implementations work by defining a menu-driven test program that
allows the user to push, pop, print, and 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 files from Lab 6 into your directory
(
linktool.h, linktool.c
, and linktest.c
).
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
.
- Using
linktest.c
as a starting point, create a menu-driven
program called hw6.c
that allows the user to push, pop,
print the contents of, and test a stack to see if it is empty.
Compile hw6.c
.
- Define your makefile for your 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
Submit your files using the following
turnin command:
/cs/bin/turnin submit cs2301 PROJECT6 makefile stack.h stack.c hw6.c
Programs submitted after 5pm on December 14 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.
Here is the Homework 6 gradesheet.