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