CS 201 - 9/2/14
Last Time Dynamic Memory Allocation
-----------------
An array is a storage structure
This class needs us to create Data Structures
Data Structures contain:
1. A storage structure to hold data
2. A set of operations to be performed on the data
List Data Structure
1. What storage structure is used???
- perhaps an array
2. What operations should we define???
- tranverse (look at all items)
- search
- retrieval
- add an item to the list
- remove an item from the list
- clear the list
- is the list empty?
When trying to determine which Data Structure is best,
we first should determine which operations are needed.
Once we know the operations, choosing one storage
structure over another storage structure could result
in a faster running program.
Data Structure #2 - Stack
Operations:
- insert (push)
- remove (pop)
- get last item inserted (top)
- is Empty
- make empty
The stack follows a LIFO storage of data.
- when the pop and top operations are combined
we will call this "tpop" which is short for
"top and pop".
Stack calculators (HP tried to make these popular
in the early 80's) use a stack data structure for
arithmetic calculations.
Stack calculators work well with expressions written
in postfix notation.
7 8 +
Most expression based calculators use a stack data
structure to evealuate infix expressions.
What is the C code for a Stack Data Structure?
- first attempt will use an array for the storage
structure.
C syntactic element of the struct
- allows us to combine multiple data items
of varying type into one storage structure
A stack will need data for
- the array itself
- the maximum number of values the array can hold
- the current position for the top of the stack
/* actual C code */
typedef struct StackStruct Stack;
struct StackStruct
{
int arr[10];
int max;
int top;
};
---------------
int main ()
{
Stack st1;
Stack st2;
/* initialize the stack variable instance */
/* inline init of st1 */
int i;
st1.max = 10;
st1.top = 0;
for (i = 0 ; i < st1.max ; i++)
st1.arr[i] = -999;
/* function initial call */
stackInit ( st2);