CS 241
Program 04
Due: Thursday, October 25th
Main topics: Arrays Pointers
Memory allocation
Program Speci cation:
A stack is a container that can be de ned in terms of an array where all adds are preformed at the end
of the sequence of existing values, and all removes are also preformed at end of the sequence of existing
values. An empty stack is one that has no existing values in the array at all. We use the notion of top of
the stack to keep track of (at which index) a new value in the sequence is to be added. Hence, an empty
stack is one in which top is equal to 0 and a full stack is one in which top is equal to the array’s physical
size - capacity.
The di erence with a dynamic stack is that adds never fail. If the stack is full when you attempt to
add a new item, you create a new array with twice the capacity of the current array, copy all the existing
items to the new array and then the new item, free the memory of the old array, set the stack pointer to
the new array and adjust the top indicator as always. Similarly, if after a remove from the stack, the stack
is less than half full, then you shrink the array in half.
For this assignment, you will write a C program to create and use an array based dynamic stack
Requirements:
You must write a C program which satis es the following:
Your program must dynamically allocate the memory for a dynamic stack - using the appropriate
function listed below.
Your program must dynamically free this memory before termination.
Your C program must declare and de ne functions to:
{ Create an empty stack (of float values) with a capacity of 1
{ Test to see if the stack is empty
{ Test to see if a stack is less than half full
{ Test to see if the stack is full
{ Push (add) an item (a oat value) onto the stack
{ Pop (remove) an item (a oat value) from the stack - if not already empty
Your C program must de ne a main function to fully test all of the above funcionality.
Notes:
1. A stack is really three separate data items:
(a) a float pointer to the array
(b) an int top index indicator
(c) an int capacity (physical size of the array) - note this must be a variable this time - since it
will change over time
2. The e ective size of the stack (number of items in the stack) can be deduced from the top index
indicator.
Sample run(s):
Submission:
1. Use your web browser to open:
https://uwm.courses.wisconsin.edu/
2. Login to D2L
3. Under 2182 - Spring 2018 you should see CEAS-Computer Science and under that
C Prog: Embedded Systems
4. Click on Intro Computer Programming
5. Click on Dropbox in the lower top menu bar
6. Click on Program 04 in the Programming Assignments folder of the the current window
7. Click the Add a File button in the left center of the current window
8. Click the Upload button in the right top of the Submit a File pop-up window
9. Use the File Upload pop-up window to nd the C source code le you wish to submit: e.g.
Program04.c
10. Click on this le name in the right panel of the File Upload pop-up window
11. Click the Open button in the File Upload pop-up window
12. Click the Add button in the bottom right top of the Submit a File pop-up window
13. Click the Submit button in the top / bottom right right of the current window