CptS 122 –
Data Structures
Lab
4: Data Structures and Dynamic Stacks in C
Assigned: Week of
Due: At the end of the
lab session
I. Learner
Objectives:
At the conclusion
of this programming assignment, participants should be able to:
- Design,
implement and test a dynamic stack in C
- Compare
and contrast dynamic linked lists and dynamic stacks
- Summarize
the advantages of applying a stack within certain applications
- Describe
the operations applied to a stack including
1.
push (
)
2. pop ( )
3. top ( )
or peek ( )
II.
Prerequisites:
Before starting
this programming assignment, participants should be able to:
- Analyze
a basic set of requirements for a problem
- Compose
a small C language program
- Create
test cases for a program
- Apply
and implement structs
in C
- Apply
and implement pointers in C
- Apply
and implement dynamic memory in C
- Design
and implement a dynamic singly linked list
This lab, along with
your TA, will help you navigate through designing,
implementing, and testing a dynamic stack. Recall, a stack data
structure is a
restricted linked list, where only the top node in the stack may be
accessed at
any given time. A stack is referred to as a last-in, first-out (LIFO)
structure
as a result of this constraint. Furthermore, the operation of a stack
must
adhere to this restriction. A push ( ) operation adds a node to the top
of the stack,
a pop ( ) operation removes a node from the top of the stack, and a top
( ) or
peek ( ) operation returns the data in the node at the top of the
stack. We
will visualize a stack in the following way:
Labs are held in a
“closed” environment such that you may ask your TA
questions. Please use your TAs knowledge to your advantage. You are
required to
move at the pace set forth by your TA. Please help other students in
need when
you are finished with a task. You may work in pairs if you wish.
However, I
encourage you to compose your own solution to each problem. Have a
great time!
Labs are a vital part to your education in CptS
122
so work diligently.
Tasks:
1. For the following
problem define a stackNode struct with data of type double.
Implement the following
operations for your stack data structure:
1. isEmpty() – a predicate
function which checks to see if the stack is empty; returns true if the
stack
is empty
2. push() – inserts a node
to the top of the stack; the node is allocated dynamically
3. pop() – deletes a node
from the top of the stack
4. top() or peek() – returns the
data in the node at the top of the stack
2. Test your application. In the same project, create one more header file testStack.h and source file testStack.c (for a total of at least five files). The testStack.h file should contain function prototypes for test functions you will use on your stack functions. The testStack.c source file should contain the implementations for these test functions. You will have at least one test function per application function. For example, you will have an application function called pop() (or a function very similar) that is used to remove the top node from the stack. In this task, you will need to create a test function called testPop() that passes in various data directly into pop() to see if it works correctly.
3. Work on exercise 12.12 (Infix-to-Postfix Converter) form your Deitel & Deitel C How to Program textbook. This
exercise provides you with the algorithm required to perform the correct
conversions of an infix-to-postfix expression.
IV. Submitting Labs:
- You
are
not required to submit your lab solutions. However, you should keep
them in a
folder that you may continue to access throughout the semester. You
should not
store your solutions to the local C: drive on the Sloan 353 machines.
These
files are erased on a daily basis.
V. Grading Guidelines:
- This lab is worth 100 points. Your lab grade is assigned based on completeness and effort. To receive full credit for the lab you must show up on time and continue to work on the problems and complete all the problems until the TA has dismissed you.