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);